9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe this sequence can help you out: oeis.org/A001399 $\endgroup$ – Zack Ni Jul 22 '16 at 12:06
  • 1
    $\begingroup$ For the first part, 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)}_\mbox{contribution of a}\underbrace{(1+x^2+x^4+\cdots)}_\mbox{contribution of b}\underbrace{(1+x^1+x^2+\cdots)}_\mbox{contribution of c}=\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)}.$$ $\endgroup$ – Steve Kass Jul 22 '16 at 19:21
  • $\begingroup$ @SteveKass Why don't you write it as an answer? $\endgroup$ – StubbornAtom Jul 25 '16 at 7:26
  • $\begingroup$ I didn’t address the second part of your question, but I’ll copy this to an answer. $\endgroup$ – Steve Kass Jul 25 '16 at 17:18
2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I've added an answer and continuation based upon your approach. Regards, $\endgroup$ – Markus Scheuer Jul 30 '16 at 15:28
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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