Number of solutions via generating function

Question

How to find generating function for number of solutions $x_1+x_2+x_3=n$ in set of positive integers such that $x_1 \ge x_2 \ge x_3$ and $x_1<x_2+x_3$.

Answer 1

Hint: First rewrite $x_2 = x_3 + d_{2,3}$, with $d_{2,3} \geq 0$ and $x_1 = x_2 + d_{1,2} = x_3 + d_{2,3} + d_{1,2}$ with $d_{1,2} \geq 0$. In terms of $d_{1,2} \geq 0$, $d_{2,3} \geq 0$, $x_3 \geq 1$, we have arranged for all three variables to be (so far) independent.

Now we need to implement $x_1 < x_2 + x_3$, or, what is the same thing, $x_3 + d_{2,3} + d_{1,2} < x_3 + d_{2,3} + x_3$, which is just $d_{1,2} < x_3$. Set $x_3 = d_{1,2} + e$ with $e \geq 1$. Now we have arranged for the problem to be in terms of the independent variables $d_{1,2} \geq 0$, $d_{2,3} \geq 0$, and $e \geq 1$.

Rolling back, we see that \begin{align*} n &= x_1 + x_2 + x_3 \\ &= (x_3 + d_{2,3} + d_{1,2}) + (x_3 + d_{2,3}) + x_3 \\ &= 3 x_3 + 2 d_{2,3} + d_{1,2} \\ &= 3(d_{1,2} + e) + 2 d_{2,3} + d_{1,2} \\ &= 4d_{1,2} + 2d_{2,3} + 3e \text{.} \end{align*} So the given problem is equivalent to finding a partition of $n$ into zero or more $2$s, one or more $3$s, and zero or more $4$s.

Answer 2

This is the number of triangles with integer sides and perimeter $n$, also known as Alcuin's sequence. Its generating function is $$\frac{x^3}{(1-x^2)(1-x^3)(1-x^4)}.$$

Answer 3

We are looking for a generating function $G(z)$ where the coefficient of $z^n$ gives the wanted number of solutions. We want to find a proper representation for \begin{align*} G(z)=\sum_{{{x_1,x_2,x_3\geq 1}\atop{x_1\geq x_2\geq x_3}}\atop{x_1<x_2+x_3}}z^{x_1+x_2+x_3}\tag{1} \end{align*}

In order to simplify $x_1\geq x_2\geq x_3\geq 1$ (and also $x_1,x_2,x_3\geq 1$) we write \begin{align*} x_3&=y_3+1\qquad\qquad\ \, y_3\geq 0\\ x_2&=y_2+x_3\qquad\qquad y_2\geq 0\tag{2}\\ x_1&=y_1+x_2\qquad\qquad y_1\geq 0 \end{align*} We obtain from (2): \begin{align*} x_1&<x_2+x_3\\ y_1+y_2+y_3+1&<(y_2+y_3+1)+(y_3+1)\\ y_1&<y_3+1\\ \color{blue}{y_1}&\color{blue}{\leq y_3}\tag{3}\\ \\ x_1+x_2+x_3&=(y_1+y_2+y_3+1)+(y_2+y_3+1)+(y_3+1)\\ &\,\,\color{blue}{=y_1+2y_2+3y_3+3}\tag{4} \end{align*}

With the help of (2) and (3) we can write $G(z)$ as \begin{align*} G(z)=\sum_{{y_1,y_2,y_3\geq 0}\atop{y_1\leq y_3}}z^{y_1+2y_2+3y_3+3}\tag{5} \end{align*}

In order to simplify $y_1\leq y_3$ in (5) we write \begin{align*} y_3&=t_3+y_1\qquad\quad t_3\geq 0\\ y_2&=t_2\qquad\qquad\quad\, t_2\geq 0\tag{6}\\ y_1&=t_1\qquad\qquad\quad\, t_1\geq 0 \end{align*} and we obtain from (6) \begin{align*} y_1+2y_2+3y_3+3&=t_1+2t_2+3(t_3+t_1)+3\\ &\,\,\color{blue}{=4t_1+2t_2+3t_3+3}\tag{7} \end{align*}

We obtain from (5) - (7) \begin{align*} \color{blue}{G(z)}&=\sum_{t_1,t_2,t_3\geq 0}z^{4t_1+2t_2+3t_3+3}\\ &=z^3\sum_{t_2\geq 0}z^{2t_2}\sum_{t_3\geq 0}z^{3t_3}\sum_{t_1\geq 0}z^{4t_1}\\ &\,\,\color{blue}{=\frac{z^3}{(1-z^2)(1-z^3)(1-z^4)}} \end{align*}

Answer 4

Consider the diagram

where the number of dots in column $1$ is no greater than the number of dots in column $2$, which is no greater than the number of dots in column $3$, which is equal to the number of dots in column $4$ (columns $3$ and $4$ are identical).

The diagram represents a solution to $$ a\le b\le c\quad\text{and}\quad c\le a+b\quad\text{and}\quad a+b+c=n\tag1 $$ where $a$ is the number of dots in column $2$, $b$ is the number of dots in column $3$, $c$ is the sum of the number of dots in columns $1$ and $4$, and $n$ is the number of dots in all columns. All solutions to $(1)$ can be uniquely represented this way.

We can count the number of solutions to $(1)$ by looking at the diagrams sideways. Each diagram represents a term in the expansion of $$ \frac1{1-x^2}\frac1{1-x^3}\frac1{1-x^4}\tag2 $$ The diagram above represents the $x^{16}$ term from $$ \underbrace{\color{#AAA}{\overbrace{\left(1+\color{#000}{x^2}+x^4+x^6+\cdots\right)}^{\large\frac1{1-x^2}}}}_\text{$1$ rows with $2$ dots} \underbrace{\color{#AAA}{\overbrace{\left(1+x^3+\color{#000}{x^6}+x^9+\cdots\right)}^{\large\frac1{1-x^3}}}}_\text{$2$ rows with $3$ dots} \underbrace{\color{#AAA}{\overbrace{\left(1+x^4+\color{#000}{x^8}+x^{12}+\cdots\right)}^{\large\frac1{1-x^4}}}}_\text{$2$ rows with $4$ dots}\tag3 $$ The diagram

represents the $x^{16}$ term from $$ \underbrace{\color{#AAA}{\overbrace{\left(1+x^2+\color{#000}{x^4}+x^6+\cdots\right)}^{\large\frac1{1-x^2}}}}_\text{$2$ rows with $2$ dots} \underbrace{\color{#AAA}{\overbrace{\left(\color{#000}{1}+x^3+x^6+x^9+\cdots\right)}^{\large\frac1{1-x^3}}}}_\text{$0$ rows with $3$ dots} \underbrace{\color{#AAA}{\overbrace{\left(1+x^4+x^8+\color{#000}{x^{12}}+\cdots\right)}^{\large\frac1{1-x^4}}}}_\text{$3$ rows with $4$ dots}\tag4 $$ Thus, the number of such diagrams with $n$ dots is $$ \left[x^n\right]\frac1{1-x^2}\frac1{1-x^3}\frac1{1-x^4}\tag5 $$ That is, the generating function for the number of solutions to $(1)$ is given by $(2)$.

---

Each solution to $(1)$ can be mapped uniquely to a solution of $$ a\le b\le c\quad\text{and}\quad c\lt a+b\quad\text{and}\quad a+b+c=n+3\tag6 $$ by adding $1$ to $a$, $b$, and $c$. Thus, the number of solutions to $(6)$ is given by $(5)$. Therefore, the number of solutions to $$ a\le b\le c\quad\text{and}\quad c\lt a+b\quad\text{and}\quad a+b+c=n\tag7 $$ is $$ \left[x^{n-3}\right]\frac1{1-x^2}\frac1{1-x^3}\frac1{1-x^4}=\left[x^n\right]\frac{x}{1-x^2}\frac{x}{1-x^3}\frac{x}{1-x^4}\tag8 $$ Thus, the generating function for the number of solutions to $(7)$ is $$ \bbox[5px,border:2px solid #C0A000]{\frac{x^3}{\left(1-x^2\right)\left(1-x^3\right)\left(1-x^4\right)}}\tag9 $$