Combinatorics question involving incongruent integral-sided triangles

Question

Find a recurrence relation for the number of incongruent integral-sided triangles whose perimeter is n (the relationship is different for n odd and n even).

Here is the solution:

$a_n$ = $a_{n-3}$ when n is even

$a_n$ = $a_{n-3}$ + $\left\lfloor\dfrac{n+1}{4}\right\rfloor$ when n is odd

I'm not even sure where to start on this one, but I want to be able to understand the solution rather than just have it. I said this in a previous problem, but recurrence relations is a big struggle of mine I find this topic to be quite difficult.

Answer 1

In the context of this problem, define a triangle as a triple $(a,b,c)$ of positive integers such that

• $a\le b\le c$.$\\[4pt]$
• $a+b \ge c$.

We classify triangles as non-degenerate or degenerate according as $a+b>c$, or $a+b=c$.

Let $\mathbb{N}$ denote the set of positive integers, and let $f:\mathbb{N}^3\to \mathbb{N}^3$ be given by $$f(a,b,c)=(a+1,b+1,c+1)$$

It's immediate that

• $f$ is injective.$\\[4pt]$
• $f$ maps triangles (possibly degenerate) to non-degenerate triangles.

For each nonnegative integer $n$, let $X_n$ be the set of non-degenerate triangles with perimeter $n$, and let $x_n=|X_n|$.

Clearly, $x_0=x_1=x_2=0$.

Claim:

$\;\;\;(1)\;\;x_n=x_{n-3}$, if $n$ is even, and $n\ge 4$.

$\;\;\;(2)\;\;x_n=x_{n-3}+\left\lfloor{\large{\frac{n+1}{4}}}\right\rfloor$, if $n$ is odd, and $n\ge 3$.

Proof:

First we prove claim $(1)$ . . .

It's easily verified that $x_4=0$, hence $x_4=x_1$, so claim $(1)$ holds for $n=4$.

Let $n$ be even, with $n\ge 6$.

Let $g$ denote the restriction of $f$ to $X_{n-3}$. Then we can regard $g$ as a function from $X_{n-3}$ to $X_n$.

Claim $g$ is bijective.

To prove $g$ is surjective, let $(a,b,c)\in X_n$. We need to show $(a-1,b-1,c-1)\in X_{n-3}$.

Claim $a \ge 2$. Suppose instead that $a=1$. Since $(a,b,c)$ is non-degenerate, we get $1+b > c$. Then $b\le c < b+1$, hence $b=c$, so $n=a+b+c=1+2c$, contradiction, since $n$ is even. Thus, $a\ge2$, as claimed.

From $2\le a\le b \le c$, we get $1\le a-1 \le b-1 \le c-1$, and from $a+b+c=n$, we get $(a-1)+(b-1)+(c-1)=n-3$.

It remains to verify that $(a-1,b-1,c-1)$ is non-degenerate. \begin{align*} \text{Then}\;\;&a+b > c\\[4pt] \implies\;&a+b+c > 2c\\[4pt] \implies\;&a+b+c \ge 2c+2&&\text{[since $a+b+c=n$, which is even]}\\[4pt] \implies\;&a+b \ge c+2\\[4pt] \implies\;&(a-1)+(b-1) \ge c\\[4pt] \implies\;&(a-1)+(b-1) > (c-1)\\[4pt] \end{align*} so $(a-1,b-1,c-1)$ is non-degenerate.

Thus, $g$ is surjective. Since $f$ is injective, so is $g$, hence $g$ is bijective, as claimed.

It follows that $x_n=x_{n-3}$.

Thus, claim $(1)$ is proved.

Next we prove claim $(2)$ . . .

For each integer $n\ge 2$, let $Y_n$ be the set of all triangles (possibly degenerate) with perimeter $n$, and let $y_n=|Y_n|$.

Let's consider the question of how $y_n$ relates to $x_n$.

Note that the perimeter of a degenerate triangle $(a,b,c)$ must be even, since $a+b=c$ implies $a+b+c=2c$. Hence, if $n$ is odd, we get $y_n=x_n$.

If $n$ is even, the degenerate triangles with perimeter $n$ correspond to pairs $(a,b)$ of positive integers with $a\le b$, and $a+b={\large{\frac{n}{2}}}$, or equivalently, they correspond to positive integers $a\le {\large{\frac{n}{4}}}$. Hence, for the case where $n$ is even, we get $y_n=x_n+\left\lfloor{\large{\frac{n}{4}}}\right\rfloor$.

Back to the proof of claim $(2)$ . . .

We have $x_3 = 1 = x_0 + \left\lfloor{\large{\frac{3+1}{4}}}\right\rfloor$, so claim $(2)$ holds for $n=3$.

Let $n$ be odd, with $n\ge 5$. Then $n=2k+1$, for some integer $k\ge 2$.

Let $h$ be the restriction of $f$ to $Y_{n-3}$. Then we can regard $h$ as a function from $Y_{n-3}$ to $X_n$.

Since $f$ is injective, so is $h$.

Note that $X_n$ has a unique triple with $a=1$, namely the triple $T_1=(1,k,k)$. Clearly $T_1$ is not in the image of $h$. Claim the image of $h$ is all of $X_n$, except for $T_1$.

Thus, let $(a,b,c)\in X_n$ with $a\ge 2$.

From $2\le a\le b \le c$, we get $1\le a-1 \le b-1 \le c-1$, and from $a+b+c=n$, we get $(a-1)+(b-1)+(c-1)=n-3$. It remains to verify that $(a-1,b-1,c-1)$ is a triangle (possibly degenerate). \begin{align*} \text{Then}\;\;&a+b > c\\[4pt] \implies\;&a+b\ge c+1\\[4pt] \implies\;&(a-1)+(b-1) \ge (c-1)\\[4pt] \end{align*} hence $(a-1,b-1,c-1)\in Y_{n-3}$, and $h$ maps $(a-1,b-1,c-1)$ to $(a,b,c)$. Thus, the image of $h$ is all of $X_n$, except for $T_1$, as claimed.

It follows that $x_n=y_{n-3}+1$.

Since $n-3$ is even, and $n-3 \ge 2$, we get $y_{n-3}=x_{n-3}+\left\lfloor{\large{\frac{n-3}{4}}}\right\rfloor$, hence \begin{align*} x_n&=y_{n-3}+1\\[4pt] &=\left(x_{n-3}+\left\lfloor{\small{\frac{n-3}{4}}}\right\rfloor\right)+1\\[4pt] &=x_{n-3}+\left(\left\lfloor{\small{\frac{n-3}{4}}}\right\rfloor+1\right)\\[4pt] &=x_{n-3}+\left\lfloor{\small{\frac{n+1}{4}}}\right\rfloor\\[4pt] \end{align*} Thus, claim $(2)$ is proved.

Answer 2

A nondegenerate triangle $\triangle$ with integer side lengths is admissible. If $a\leq b\leq c$ are the side lengths of such a $\triangle$ I call the numbers $$x:=b-a\geq0,\quad y:=c-b\geq0,\quad z:=a+b-c-1\geq0\tag{1}$$ the data of $\triangle$. Given a data vector $(x,y,z)\in{\mathbb N}_{\geq0}^3$ the equations $(1)$ determine $$a=1+y+z,\quad b=1+x+y+z,\quad c=1+x+2y+z\ ,\tag{2}$$ which are obviously the side lengths $a\leq b\leq c$ of an admissible triangle.

Denote by $X_n$ the set of all admissible triangles with circumference $n\geq3$, and let $a_n:=\# X_n$. The triangle with sides $(2)$ has circumference $3+2x+4y+3z$. Therefore $a_n$ is given by $$a_n=\#\bigl\{(x,y,z)\in {\mathbb N}_{\geq0}^3\bigm|2x+4y+3z=n-3\bigr\}\ .\tag{3}$$ If $(x,y,z)$ are the data of a $\triangle\in X_n$, and $z\geq1$ for this triangle, then $(x,y,z-1)$ are the data of a $\triangle'\in X_{n-3}$. Conversely, if $(x',y',z')$ are the data of a $\triangle'\in X_{n-3}$ then $(x',y',z'+1)$ are the data of a $\triangle\in X_n$ with $z\geq1$. It remains to count the solutions to $(3)$ having $z=0$. Now $$2x+4y=n-3\tag{4}$$ only has solutions if $n=2m+1$ is odd. We then have to solve $x+2y=m-1$. As $y$ can take values between $0$ and $\left\lfloor{m-1\over2}\right\rfloor$ inclusive there are $\left\lfloor{m+1\over2}\right\rfloor=\left\lfloor{n+1\over4}\right\rfloor$ solutions to $(4)$. The recursion we are after therefore is $$a_n=a_{n-3}+{\rm odd}(n)\left\lfloor{n+1\over4}\right\rfloor\qquad(n\geq3)\ .$$ More information on the $a_n$ can be found at A005044 at OEIS.