Home > Discussions > Combinatorics

Note: this page uses MathJax for formatting, so may take a few seconds to load.

Note: this page uses MathJax for formatting, so may take a few seconds to load.

Adventures with Generating Functions III

Note: This is the third article of a planned 5-part series.

- The previous article: Adventures with Generating Functions II: How To Make a Million Dollars
- The first article: Adventures with Generating Functions I: An Infinite Sum

Third Adventure: Integer Triangles

How many incongruent triangles have integer sides and perimeter 10?

As you can verify, there are only two: $(2,4,4)$ and $(3,3,4)$. Let's call triangles with integer side lengths *integer triangles*.
We write the sides of an integer triangle as $(a,b,c)$, where $a \leq b \leq c$. Of course, these triples must satisfy the triangle
inequality: $a+b >c$. In fact, a few moments thought should convince you that any triple satisfying the triangle inequality can be realized
by a triangle. (Think of moving rods of the given lengths to form a triangle.)

How many incongruent integer triangles are there with perimeter $10^{100}$? We will find a formula which enables you to calculate this. For $n \geq 0$, let $t(n)$ be the number of incongruent integer triangles with perimeter $n$. It is easy to find the values of $t(n)$ for small $n$. \begin{array}{cccccccccccc} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ t(n) & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 2 & 1 & 3 & 2 \end{array}

We call $\{t(n)\}$ *Alcuin's sequence*, named after Alcuin
of York (c. 735-804), who wrote a problem-solving book which contained some problems equivalent to finding integer triangles.

Like the Fibonacci sequence, Alcuin's sequence satisfies a linear recurrence relation and therefore has a rational generating function. The generating function is \[ \sum_{n=0}^{\infty}t(n)x^n=\frac{x^3}{(1-x^2)(1-x^3)(1-x^4)}. \] We can prove this by showing how to make any integer triangle $(a,b,c)$, starting with the $(1,1,1)$ triangle and adding nonnegative integer multiples of $(0,1,1)$, $(1,1,1)$, and $(1,1,2)$: \[ (a,b,c)=(1,1,1)+\alpha(0,1,1)+\beta(1,1,1)+\gamma(1,1,2) \quad (\ast). \] Such triples satisfy the triangle inequality since we start with the triangle $(1,1,1)$ and each of the triples $(0,1,1)$, $(1,1,1)$, $(1,1,2)$ satisfies the weak triangle inequality (with $\geq$ instead if $>$). We have three equations: \begin{align*} a&=1+\beta+\gamma\\ b&=1+\alpha+\beta+\gamma\\ c&=1+\alpha+\beta+2\gamma. \end{align*} You can verify that there is a unique solution to these equations in nonnegative integers $\alpha$, $\beta$, $\gamma$.

Taking the sum of the coordinates in ($\ast$), we get \[ a+b+c=3+2\alpha+3\beta+4\gamma. \] Therefore, $t(n)$ is the number of nonnegative integer solutions to the equation \[ n=3+2\alpha+3\beta+4\gamma. \] Equivalently, $t(n)$ is the number of ways of making the amount $n-3$ with units of $2$, $3$, and $4$. This is a "making change" problem, which was covered in the previous article in this series: Adventures with Generating Functions II: How To Make a Million Dollars. Using the ideas of that article, we can write down the above generating function for {t(n)}.

If we rewrite the denominator of the generating function as \[ (1-x^2)(1-x^3)(1-x^4) = 1-x^2-x^3-x^4+x^5+x^6+x^7-x^9 \] we can obtain a linear recurrence relation for $t(n)$: \[ t(n)=t(n-2)+t(n-3)+t(n-4)-t(n-5)-t(n-6)-t(n-7)+t(n-9), \quad n \geq 9. \] This recurrence, together with the initial values $t(0)$ through $t(8)$ generates the sequence $\{t(n)\}$.

A computer algebra system can find the partial fractions decomposition of the generating function: \[ -\frac{1}{24(x-1)^3}+\frac{13}{288(x-1)}-\frac{1}{16(x+1)^2}-\frac{1}{32(x+1)}-\frac{x+1}{8(x^2+1)}+\frac{x+2}{9(x^2+x+1)}. \] What an ugly expression!

To find the coefficient of $x^n$, we use the binomial series formula for each of the six terms. The first term is \[ \frac{1}{24}\sum_{n=0}^\infty \binom{-3}{n} (-1)^n x^n, \] and we use the identity $\binom{-k}{n}=(-1)^n\binom{n+k-1}{n}$ to change this sum to \[ \frac{1}{24}\sum_{n=0}^\infty \binom{n+2}{2} x^n=\frac{1}{48}\sum_{n=0}^\infty (n+2)(n+1) x^n. \] We make similar calculations for the other five terms in the ugly expression. (To put the last term into the right form, we multiply the numerator and denominator by $x-1$.) We find that $t(n)$, the coefficient of $x^n$, is given by \[ t(n)=\frac{6n^2+18n-1-18n(-1)^n-27(-1)^n+4c}{288}, \] where $c$ is defined according to the following table. \[ \begin{array}{ccccc} n \bmod{12} & 1,4,5,8 & 2,7,10,11 & 0,9 & 3,6\\ c & -17 & 1 & 7 & 25 \end{array} \] This formula simplifies to \[ t(n)= \left\{ \begin{array}{cc} \left\{\frac{n^2}{48}\right\} &\mbox{for $n$ even}\\ \left\{\frac{(n+3)^2}{48}\right\} &\mbox{for $n$ odd} \end{array} \right. \] where $\{x\}$ is the nearest integer to $x$.

Now you can find (by hand!) the number of integer triangles with perimeter $10^{100}$: \[ t(10^{100})=208\underbrace{3 \ldots 3}_{196}. \]

The next article in the series: Adventures with Generating Functions IV: Rook Paths.