Number of elements in set $S = \{(x,y,z): x,y,z \in \mathbb{Z}, x+2y+3z=42, x,y,z \ge 0\}$ is?

Question

Number of elements in set $S = \{(x,y,z): x,y,z \in \mathbb{Z}, x+2y+3z=42, x,y,z \ge 0\}$ is?

My solution:

This is equal to the coefficient of $t^{42}$ in

$(1+t+t^2+t^3+...+t^{43})(1+t^2+t^4+...+t^{42})(1+t^3+t^6+...+t^{42})$

= $\frac{(1-t^{43})}{1-t} \times \frac{(1-t^{44})}{1-t^2} \times \frac{(1-t^{45})}{1-t^3} $

= $\frac{1} {(1-t)(1-t^2)(1-t^3)}$

since I neglected higher powers of t

= $\frac{1} {(1-t)^3(1+t)(1+t+t^2)}$

= $\frac{(1-t)^{-3}} {(1+t)(1+t+t^2)}$

Now I know the coefficient of $x^n$ in $(1-x)^{-r}$ is $\binom {n+r-1}{r-1}$.

But I don't know what to do with the denominator part. Can someone help??

Answer 1

Let $$A=\frac{1} {(1-t)(1-t^2)(1-t^3)}$$ Then we can say that $$A=(1-t)^{-1}(1-t^2)^{-1}(1-t^3)^{-1}$$ and it is well known that for $\displaystyle{(1-x)^{-n}=1+\binom{n}{1}x+\binom{n+1}{2}x^2 +\binom{n+2}{3}x^3+\cdots\textrm{till}\:\: \infty}$

where $n$ is a positive integer. I hope you can continue from here.

Answer 2

Just use partial fractions. Write $$ \frac{1}{(1-t)^3(1+t)(1+t+t^2)}=\frac{A_1}{1-t}+\frac{A_2}{(1-t)^2}+\frac{A_3}{(1-t)^3}+\frac{B}{1+t}+\frac{C_0+C_1t}{1+t+t^2}. $$

Multiplying LHS by $1+t$ and letting $t=-1$ yields $$ B=\left[\frac{1}{(1-t)^3(1+t+t^2)}\right]_{t=-1}=\frac{1}{(1+1)^3(1-1+1)}=\frac{1}{8}. $$

Multiplying LHS by $(1-t)^3$ and letting $t=1$ yields $$ A_3=\left[\frac{1}{(1+t)(1+t+t^2)}\right]_{t=1}=\frac{1}{(1+1)(1+1+1)}=\frac{1}{6}. $$

You can keep going like this (using your favorite method of partial fraction expansion) to obtain the following: \begin{multline*} \frac{1}{(1-t)^3(1+t)(1+t+t^2)}=\\ =\frac{1}{6}\cdot\frac{1}{(1-t)^3}+\frac{1}{4}\cdot\frac{1}{(1-t)^2}+\frac{17}{72}\cdot\frac{1}{1-t}+\frac{1}{8}\cdot\frac{1}{1+t}+\frac{1}{9}\cdot\frac{2+t}{1+t+t^2}. \end{multline*}

Everything except the last summand is expands easily into a power series, and for the last summand we can write $$ \frac{2+t}{1+t+t^2}=\frac{(1-t)(2+t)}{(1-t)(1+t+t^2)}=\frac{2-t-t^2}{1-t^3}=\frac{2}{1-t^3}-\frac{t}{1-t^3}-\frac{t^2}{1-t^3}. $$

Thus, $$ \begin{split} [t^n]\frac{1}{(1-t)^3(1+t)(1+t+t^2)} &=\frac{1}{6}\binom{n+2}{2}+\frac{1}{4}\binom{n+1}{1}+\frac{17}{72}+\frac{(-1)^n}{8}+\frac{-1+[3 \text{ if } 3\mid n]}{9}\\ &=\frac{2n^2+12n+13+3(-1)^n+8[3\mid n]}{24}, \end{split} $$ where "$[\cdot]$" is the Iverson bracket (i.e. $1$ if the statement in the bracket is true, and $0$ if it is false).

In this case, $3\mid 42$, so $[3\mid 42]=1$ and $$ \begin{split} [t^{42}]\frac{1}{(1-t)^3(1+t)(1+t+t^2)}&=\frac{2\cdot 42^2+12\cdot 42+13+3(-1)^{42}+8\cdot 1}{24}\\ &=\frac{2\cdot 42^2+12\cdot 42+24}{24}\\ &=\frac{42\cdot 96+24}{24}=42\cdot4+1=169 \end{split} $$