2

Total number of non negative integer solution of the equation $x+y+z=n$ subjected to the condition $x\leq y \leq z.$

Try:if $x=0$ Then we have $y+z=n$

If $x=1$ Then we have $y+z=n-1$

.....if $x=n$ Then we have $y+z=0$ so $x=y=0$

Could some help me how to calculate for $x+y=n,n-1,n-2$ ect.

Or any nice way to find solution of original equation.Thanks

DXT
  • 11,241

2 Answers2

1

Let us define $A,B,C$ as follows :

$A$ : The number of non-negative solutions $(x,y,z)$ such that $x\lt y\lt z$.

$B$ : The number of non-negative solutions $(x,y,z)$ such that $x=y\lt z$ or $x\lt y=z$.

$C$ : The number of non-negative solutions $(x,y,z)$ such that $x=y=z$.

Then, the number of solutions such that $x\le y\le z$ is given by $A+B+C$.

The number of non-negative solutions for $x+y+z=n$ is given by $\binom{n+2}{2}=\frac{(n+2)(n+1)}{2}$, so we have $$\frac{(n+2)(n+1)}{2}=3!A+\frac{3!}{2!}B+C\tag1$$

Since $C$ is given by $$C=\begin{cases}1&\text{if $n\equiv 0\pmod 3$}\\\\0&\text{if $n\not\equiv 0\pmod 3$}\end{cases}$$ we can write $$C=\left\lfloor\left\lfloor\frac n3\right\rfloor\div\frac n3\right\rfloor\tag2$$

To find $B$, let us consider $a+a+b=n$ where $a\not=b$, and then

$$b=n-2a\ge 0\implies a\le\frac n2\implies a=0,1,\cdots,\left\lfloor\frac n2\right\rfloor$$

So, we have $$B=\left\lfloor\frac n2\right\rfloor+1-C\tag3$$

From $(1)$, we have $$A=\frac 16\left(\frac{(n+2)(n+1)}{2}-3B-C\right)\tag4$$

Therefore, from $(2)(3)(4)$, the number of solutions with $x\le y\le z$, i.e. $A+B+C$ is given by $$\frac{1}{12}\left((n+2)(n+1)+6\left\lfloor\frac n2\right\rfloor+6+4\left\lfloor\left\lfloor\frac n3\right\rfloor\div\frac n3\right\rfloor\right)$$

mathlove
  • 139,939
1

We transform the equation $x+y+z=n$ with integer solutions $0\leq x\leq y\leq z$ by putting \begin{align*} x&=a&a \geq 0\\ y&=x+b&b\geq 0\\ z&=y+c&c\geq 0 \end{align*} and get the equivalent system \begin{align*} \color{blue}{3a+2b+c=n\qquad\qquad 0\leq a,b,c\leq n}\tag{1} \end{align*}

We solve (1) with the help of generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of a series.

We obtain the number of valid solutions by calculating \begin{align*} \color{blue}{[z^n]}&\color{blue}{\left(1+z^3+z^6+\cdots\right)\left(1+z^2+z^4+\cdots\right)\left(1+z+z^2+\cdots\right)}\\ &=[z^n]\frac{1}{\left(1-z^3\right)\left(1-z^2\right)\left(1-z\right)}\tag{2}\\ &=[z^n]\left(\frac{1}{6}\cdot\frac{1}{(1-z)^3}+\frac{1}{4}\cdot\frac{1}{(1-z)^2} +\frac{1}{4}\cdot\frac{1}{1-z^2}+\frac{1}{3}\cdot\frac{1}{1-z^3}\right)\tag{3}\\ &=\frac{1}{6}\binom{-3}{n}(-1)^n+\frac{1}{4}\binom{-2}{n}+\frac{1}{4}[[n\equiv 0(3)]]+\frac{1}{3}[[n\equiv 0(3)]]\tag{4}\\ &=\frac{1}{6}\binom{n+2}{2}+\frac{1}{4}\binom{n+1}{1}+\frac{1}{4}[[n\equiv 0(3)]]+\frac{1}{3}[[n\equiv 0(3)]]\tag{5}\\ &=\frac{1}{12}(n+1)(n+5)+\frac{1}{4}[[n\equiv 0(3)]]+\frac{1}{3}[[n\equiv 0(3)]]\tag{6}\\ &=\frac{1}{12}(n+3)^2-\frac{1}{3}+\frac{1}{4}[[n\equiv 0(3)]]+\frac{1}{3}[[n\equiv 0(3)]]\tag{7}\\ &\color{blue}{=\mathrm{round}\left(\frac{(n+3)^2}{12}\right)}\tag{8}\\ &\color{blue}{=(1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37,\ldots)}\tag{9} \end{align*}

Comment:

  • In (2) we use the geometric series expansion.

  • In (3) we do a (nice) partial fraction expansion.

  • In (4) we select the coefficients of the binomial series. We also use the Iversion brackets $[[P]]$ which is $1$ iff $P$ is true and $0$ otherwise.

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

  • In (6) we do a simplification.

  • In (7) we do a small trick which is indicated in the note at the end.

  • In (8) we find a nice representation as rounded expression which can be easily justified by checking the remainders modulo $6$ of the terms in (7).

Note: The numbers listed in (9) are stored in OEIS as A001399. The nice representation (8) is stated there in the formula section.

Markus Scheuer
  • 108,315