1
$\begingroup$

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.

2 Answers 2

3

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

  • 0
    Oh, I thought you could take any point from a previous triangle. Thanks.2011-03-10
1

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, 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.