Suppose you have a triangle with vertices $(1,0),(0,1), (0,0)$, and let $P$ be the number of all integer coordinates in the triangle. So $P=3$. Then the Minkowski sum $P+P$ is the set of points found by adding all possible pairs of integer coordinates in the triangle. So $P+P$ consists of points in the original triangle, as well as points $(2,0), (0,2), (1,1)$, and thus $P+P=6$. It was mentioned to me that the generating function for this sequence of sums is given by $$ p(x)=\frac{1}{(1-x)^3} $$ by I don't see why. What is the derivation of this? Thanks.
Generating function for Minkowski Sum
2 Answers
The third stage $P+P+P$ has the existing points plus (3,0), (2,1), (1,2), (0,3) to give a total of 10 points and it should be obvious that the $n^{\text{th}}$ stage adds $n+1$ additional points thus producing the (offset) triangle numbers at each stage. You should also be able to see that the starting place or $0^{\text{th}}$ stage is just $(0,0)$ to which you add $P$ to get the first stage, so has 1 point. So the sequence of numbers of points is $1,3,6,10,\ldots$. You want this as a generating function, so you want an expression for $$g(x) = 1 + 3x + 6x^2 + 10x^3 + \cdots + \frac{(n+1)(n+2)}{2} x^n + \cdots$$
Some of us can spot such things from familiarity but one way to derive it is to see that
$$ \int \int g(x) \, dx \, dx = A + Bx + x^2 /2 + x^3 /2 + x^4 /2 + x^5/2 + \cdots + x^{n+2} /2 + \cdots $$ This is essentially a simple geometric series with sum $A+Bx +\frac{x^2}{2(1-x)}$ and then reversing the double integration we find
$$g(x) = \frac{d}{dx} \frac{d}{dx} \left( A+Bx +\frac{x^2}{2(1-x)} \right) = \frac{1}{(1-x)^3}$$
-
0Thanks Henry, I like your derivation. Maybe I'm misunderstanding the Minkowski sum, but for the fourth stage, I would expect to get the points $(4,0), (3,1), (2,2), (1,3), (4,0)$. What's to stop me from getting points like $(3,2)$ by adding $(2,1)$ and $(1,1)$? – 2011-03-10
-
0(2,1) first appears in P+P+P while (1,1) first appears in P+P, so their sum appears in (P+P+P)+(P+P) = P+P+P+P+P, i.e. the fifth stage. – 2011-03-10
-
0Oh, I thought you could take any point from a previous triangle. Thanks. – 2011-03-10
The number of points after adding $n$ of the $P$s is the number of solutions of non-negative solutions of $a + b \leq n$. Imagine the points $0$ to $n$ on a line. Pick two points $p_1 A useful identity is $$ \sum_{m=0}^n \binom{m + k}{k} = \binom{n+k+1}{k+1}. $$ This is true since each $k+1$ subset of $n+k+1$ with maximal point $M \geq k+1$ is a $k$ subset of $M - 1 \geq k$, and this process is reversible. Given a generating series, multiplying it by $1/(1-x) = 1 + x + x^2 + \ldots$ is like computing "running sums". So starting with $$ 1,0,0,0,\ldots, $$ multiplying by $1/(1-x)$ we get $$ 1,1,1,1,\ldots, $$ multiplying again we get $$ 1,2,3,4,\ldots, $$ and once again $$ 1,3,6,10,\ldots. $$ The general term for $1/(1-x)^d$ is $\binom{n+d-1}{d-1} x^n$, as can be easily proven by induction using the identity above.