# Generating function for Minkowski Sum

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.

-

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}$$

-
Thanks 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)$? – Dani Hobbes Mar 10 '11 at 6:36
(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. – Henry Mar 10 '11 at 7:13
Oh, I thought you could take any point from a previous triangle. Thanks. – Dani Hobbes Mar 10 '11 at 7:22

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<p_2$, and let $a = p_1$, $b = p_2 - p_1 - 1$. This process is reversible, and so the number of solutions is $\binom{n+2}{2}$.

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.

-