Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.