Number of integer triplets $(a,b,c)$ such that $a<b<c$ and $a+b+c=n$

Question

What is an equivalent combinatorial presentation for the problem? Can I use the stars and bars approach to find the number of integral solutions of $a+b+c=n$ where $a,b,c\geq 0$?

If in addition $a+b>c$, $b+c>a$, $a+c>b$ hold, then the problem can be seen as $a,b,c$ being the sides of a triangle with perimeter $n$. I would like a hint on how to do that as well.

Answer 1

This answer is a continuation and completion of the nice approach by @SteveKass.

Part 1: Looking for the number of triples $(a,b,c)$ with \begin{align*} 0\leq a<b<c\qquad\text{and}\qquad a+b+c=n\tag{1} \end{align*} we set \begin{align*} &b=a+1+i\qquad &i\geq 0\\ &c=b+1+j=a+2+i+j\qquad &j\geq 0 \end{align*} and obtain the following condition equivalent to (1) \begin{align*} 0\leq a,i,j\qquad \text{with}\qquad 3a+2i+j=n-3\tag{2} \end{align*}

The generating function $G(x)=\sum_{n=0}^\infty g_nx^n$ with $g_n=[x^n]G(x)$ the number of solutions to (1) resp. (2) is according to Steves answer \begin{align*} G(x)=\frac{x^3}{(1-x)(1-x^2)(1-x^3)} \end{align*}

We obtain the coefficient $g_n$ by partial fraction decomposition. Note the zeros of the denominator are the $n$-th roots of unit: $1,-1$ and $e^{\pm\frac{2\pi i}{3}}$.

We obtain with some help of Wolfram Alpha \begin{align*} G(x)&=\frac{x^3}{(1-x)(1-x^2)(1-x^3)}\\ &=-\frac{1}{8}\cdot\frac{1}{1+x}-\frac{1}{72}\cdot\frac{1}{1-x}-\frac{1}{4}\cdot\frac{1}{(1-x)^2}+\frac{1}{6}\cdot\frac{1}{(1-x)^3}\\ &\qquad+\frac{1}{9}\cdot\frac{1}{1-e^{-\frac{2\pi i}{3}}x}+\frac{1}{9}\cdot\frac{1}{1-e^{\frac{2\pi i}{3}}x}\tag{3}\\ &=\color{blue}{1}x^3+\color{blue}{1}x^4+\color{blue}{2}x^5+\color{blue}{3}x^6+\color{blue}{4}x^7+\color{blue}{5}x^8+\color{blue}{7}x^9+\color{blue}{8}x^{10}\\ &\qquad+\color{blue}{10}x^{11}+\color{blue}{12}x^{12}+\color{blue}{14}x^{13}+\color{blue}{16}x^{14}+\color{blue}{19}x^{19}+\color{blue}{21}x^{20}+\cdots \end{align*}

From (3) we obtain a closed formula for the coefficients $g_n=[x^n]G(x)$ for $n\geq 3$:

\begin{align*} [x^n]G(x)&=-\frac{1}{8}(-1)^{n}-\frac{1}{72}-\frac{1}{4}\binom{-2}{n}(-1)^{n}+\frac{1}{6}\binom{-3}{n}(-1)^{n}\\ &\qquad+\frac{1}{9}e^{-\frac{2\pi i (n-3)}{3}}+\frac{1}{9}e^{\frac{2\pi i (n-3)}{3}}\tag{4}\\ &=\frac{1}{8}(-1)^{n+1}-\frac{1}{72}-\frac{1}{4}\binom{n+1}{1}+\frac{1}{6}\binom{n+2}{2}\\ &\qquad+\frac{1}{9}\left(e^{-\frac{2\pi i n}{3}}+e^{\frac{2\pi i n}{3}}\right)\tag{5}\\ &=\frac{1}{8}(-1)^{n+1}+\frac{1}{72}\left(6n^2-7\right)+\frac{2}{9}\cos\left(\frac{2\pi n}{3}\right)\tag{6}\\ &=\begin{cases} \frac{1}{12}n^2\qquad&\qquad n\equiv 0(2), n\equiv 0(3)\\ \frac{1}{12}\left(n^2-4\right)\qquad&\qquad\qquad\qquad\, n\not\equiv 0(3)\\ \frac{1}{12}\left(n^2+3\right)\qquad&\qquad n\equiv 1(2), n\equiv 0(3)\\ \frac{1}{12}\left(n^2-1\right)\qquad&\qquad\qquad\qquad\, n\not\equiv 0(3)\\ \end{cases} \end{align*}

Comment:

• In (4) we apply the binomial series expansion to the series in (3)

• In (5) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)q$

• In (6) we make some simplifications and use the identity $\cos x=\frac{1}{2}\left(e^{ix}+e^{-ix}\right)$

The sequence $(g_n)_{n\geq 0}$ with \begin{align*} 1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37, 40, 44, 48,\cdots \end{align*} is known to OEIS as A069905. It counts the number of partitions of $n$ into $3$ positive parts.

Now we take a look at the second part of OPs question

Part 2: Number of solutions with additional constraints \begin{align*} a+b>c\qquad b+c>a\qquad c+a>b \end{align*}

In fact we only have to consider $a+b>c$, since the other inqualities follow from $a<b<c$. We will do the same approach as in part 1.

We obtain according to the settings from above with $b=a+1+i, c=2a+2+i+j$ \begin{align*} a+b&>c\\ a+(a+1+i)&>a+2+i+j\\ a&>j+1 \end{align*} The condition $a>j+1$ is equivalent with $a=k+j+1, k\geq 0$ and we conclude from (2) the number of solutions is \begin{align*} 0\leq i,j,k\qquad \text{with}\qquad &3(k+j+1)+2i+j=n-3\\ &4j+3k+2i=n-6\tag{7}\\ \end{align*}

We can now proceed in the same as we did in part 1.

We obtain from (7) the generating function $H(x)$ with \begin{align*} H(x)&=\frac{x^6}{(1-x^2)(1-x^3)(1-x^4)}\\ &=-\frac{5}{32}\cdot\frac{1}{1+x}+\frac{1}{16}\cdot\frac{1}{(1+x)^2}\\ &\qquad+\frac{23}{288}\cdot\frac{1}{1-x}-\frac{1}{8}\cdot\frac{1}{(1-x)^2}+\frac{1}{24}\cdot\frac{1}{(1-x)^3}\\ &\qquad-\frac{1}{16}\cdot\frac{1+i}{1-ix}-\frac{1}{16}\cdot\frac{1-i}{1+ix} +\frac{1}{9}\cdot\frac{1}{1-e^{-\frac{2\pi i}{3}}x}+\frac{1}{9}\cdot\frac{1}{1-e^{\frac{2\pi i}{3}}x}\tag{8}\\ &=\color{blue}{1}x^6+\color{blue}{0}x^7+\color{blue}{1}x^8+\color{blue}{1}x^9+\color{blue}{2}x^{10}+\color{blue}{1}x^{11}+\color{blue}{3}x^{12}+\color{blue}{2}x^{13}+\color{blue}{4}x^{14}\\ &\qquad+\color{blue}{3}x^{15}+\color{blue}{5}x^{16}+\color{blue}{4}x^{17}+\color{blue}{7}x^{18}+\color{blue}{5}x^{19}+\color{blue}{8}x^{20}+\color{blue}{8}x^{21}\cdots \end{align*}

From (8) we obtain a closed formula for the coefficients $h_n=[x^n]H(x)$ for $n\geq 6$:

\begin{align*} [x^n]H(x)&=-\frac{5}{32}(-1)^{n}+\frac{1}{16}\binom{-2}{n}+\frac{23}{288} -\frac{1}{8}\binom{-2}{n}(-1)^{n}+\frac{1}{24}\binom{-3}{n}(-1)^{n}\\ &\qquad-\frac{1}{16}(1+i)i^n-\frac{1}{16}(1-i)(-i)^n+\frac{2}{9}\cos\left(\frac{2\pi n}{3}\right)\\ &=\frac{5}{32}(-1)^{n+1}+\frac{1}{16}\binom{n+1}{1}(-1)^n+\frac{23}{288}-\frac{1}{8}\binom{n+1}{1}+\frac{1}{24}\binom{n+2}{2}\\ &\qquad-\frac{1}{16}(1+i)i^n-\frac{1}{16}(1-i)(-i)^n+\frac{2}{9}\cos\left(\frac{2\pi n}{3}\right)\\ &=\frac{1}{32}(-1)^{n}(2n-3)+\frac{1}{288}\left(6n^2-18n-1\right)\\ &\qquad-\frac{1}{16}i^n\left((1+i)+(1-i)(-1)^n\right)+\frac{2}{9}\cos\left(\frac{2\pi n}{3}\right)\\ &=\begin{cases} \frac{1}{48}n^2\qquad&\qquad n\equiv 0(4), n\equiv 0(3)\\ \frac{1}{48}\left(n^2-16\right)\qquad&\qquad\qquad\qquad\, n\not\equiv 0(3)\\ \frac{1}{144}\left(3n^2-18n-1\right)\qquad&\qquad n\equiv 1(4), n\equiv 0(3)\\ \frac{1}{144}\left(3n^2-18n+15\right)\qquad&\qquad\qquad\qquad\, n\not\equiv 0(3)\\ \frac{1}{48}\left(n^2+12\right)\qquad&\qquad n\equiv 2(4), n\equiv 0(3)\\ \frac{1}{48}\left(n^2-4\right)\qquad&\qquad\qquad\qquad\, n\not\equiv 0(3)\\ \frac{1}{48}\left(n^2-6n+9\right)\qquad&\qquad n\equiv 3(4), n\equiv 0(3)\\ \frac{1}{144}\left(3n^2-18n-21\right)\qquad&\qquad\qquad\qquad\, n\not\equiv 0(3)\\ \end{cases} \end{align*}

We can also find this sequence in OEIS:

A shifted variant of the sequence $(h_n)_{n\geq 0}$ with generating function $x^{-3}H(x)$ and beginning with \begin{align*} 0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2, 4, 3, 5, 4, 7, 5, 8, 7, 10, 8, 12, 10, 14, 12, 16, 14, 19, 16, 21,\cdots \end{align*} is known to OEIS as Alcuin's sequence. It counts the number of triangles with integer side and perimeter $n$.

Answer 2

For the first part or your question:

Write $b=a+1+i$ and $c=(a+1+i)+1+j=a+2+i+j$ where $i,j\ge0$. Then $$a+b+c=a+(a+1+i)+(a+2+i+j)=3a+2i+j+3,$$ and you can restate the question as the number of solutions to $$3a+2i+j=n-3$$ where $a,i,j\ge0$. This is the coefficient of $x^{n-3}$ in $$\underbrace{(1+x^3+x^6+\cdots)}_{\text{contribution of } a}\cdot\underbrace{(1+x^2+x^4+\cdots)}_{\text{contribution of } i}\cdot\underbrace{(1+x^1+x^2+\cdots)}_{\text{contribution of } j}=\frac1{(1-x^3)(1-x^2)(1-x)},$$ or the coefficient of $x^n$ in $$\frac{x^3}{(1-x^3)(1-x^2)(1-x)}.$$

Answer 3

Let $Q(n,3)$ be the number of partitions of $n$ into unequal parts and $P(n,3)$ the number of partitions of $n$ for any $n$. If $a < b < c$ and $a+b+c = n$, then $a \leq b-1 \leq c-2$ and $(a,b-1, c-2)$ is a partition of $n-3$. Thus we need to calculate $P(n-3,3)$. For a $p-$partition of $n$, we have the recurrence ralation \begin{equation*} P(n,p) = P(n-p,p) + P(n-1, p-1) \end{equation*} Hence we have $P(n-3, 3) = P(n-6, 3) + P(n-4, 2)$. Noting that $P(k,2) = \left[\frac{k}{2}\right]$, we can calculate $P(n-3,3)$ recursively.