Number of integer solutions of linear equation.

Question

I have the following problem.

Assume we have an unlimited number of blocks of 1cm, 2cm and 3cm height. Ignoring the position of the blocks, how many towers of 15cm height can we build?

I know I must find the coefficient of $x^{15}$ of the function $$ f(x)=\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}=(1+x+x^2)\frac{1}{1-x^2}\frac{1}{(1-x^3)^2} $$ How do I find it?

Answer 1

Denote the coefficient of $x^n$ in $(\frac{1}{1-x} \frac{1}{1-x^2})$ by f(n). Then $f(n) = \lceil \frac{n+1}{2} \rceil$. Obviously, the answer is

$f(0) + f(3) +...+f(12) + f(15) = 1 + 2 + 4 + 5 + 7 + 8 = 27 $

Answer 2

$\mathbf{\text{Remember :}}$ $$\sum_{k=0}^{\infty}\binom{n+k-1}{k}x^k= \bigg(\frac{1}{1-x}\bigg)^n$$

By using given formula ,

• $$\frac{1}{1-x}= \sum_{n=0}^{\infty}x^n=1+x+x^2+x^3+...$$ , so the coefficient of $x^n$ is $\binom{n+1-1}{n}$

• $$\frac{1}{1-x^2}= \sum_{k=0}^{\infty}(x^2)^k=1+x^2+x^4+x^6+...$$ , so the coefficient of $x^{2k}$ is $\binom{k+1-1}{k}$

• $$\frac{1}{1-x^3}= \sum_{m=0}^{\infty}(x^3)^m=1+x^3+x^6+x^9+...$$ , so the coefficient of $x^{3m}$ is $\binom{m+1-1}{m}$

where $n+2k+3m =15$ , so find the possible $n,k,m$ values that satify the equation and they are nonnegative integers such that

• $n=15,k=0,m=0$

• $n=13,k=1,m=0$

• $n=12,k=0,m=1$

• $n=11,k=2,m=0$

• $n=10,k=1,m=1$

• $n=9,k=3,m=0$

• $n=9,k=0,m=2$

• $n=8,k=2,m=1$

• $n=7,k=4,m=0$

• $n=7,k=1,m=2$

• $n=6,k=0,m=3$

• $n=6,k=3,m=1$

• $n=5,k=5,m=0$

• $n=5,k=2,m=2$

• $n=4,k=4,m=1$

• $n=4,k=1,m=3$

• $n=3,k=6,m=0$

• $n=3,k=3,m=2$

• $n=3,k=0,m=4$

• $n=2,k=5,m=1$

• $n=2,k=3,m=3$

• $n=1,k=7,m=0$

• $n=1,k=4,m=2$

• $n=1,k=1,m=4$

• $n=0,k=0,m=5$

• $n=0,k=3,m=3$

• $n=0,k=6,m=1$

As you see , there are $27$ possible solution that satisfy the equation .Moreover , realize that whichever integer we put in place of $n,k,m$ , the result of binomial coefficient is $1$ , so we just need to sum how many possible solution there are , so the answer is $27$.

I highly recommend you to use wolfram or other softwares to calculate generating functions. I am putting a LINK

Answer 3

Define sequences $\{a_n\}$, $\{b_n\}$ and $\{c_n\}$ by $$\begin{align} \frac{1}{1-x^3} &= \sum_{n=0}^{\infty} a_n x^n \\ \frac{1}{1-x^3}\frac{1}{1-x^2} &= \sum_{n=0}^{\infty} b_n x^n \\ \frac{1}{1-x^3}\frac{1}{1-x^2} \frac{1}{1-x} &= \sum_{n=0}^{\infty} c_n x^n \end{align}$$ Then we have $a_0=b_0=c_0=1$ and the recursive relations $$\begin{align} a_n &= [3 | n] \\ b_n &= b_{n-2}+a_n \quad \text{ for } n \ge 2\\ c_n &= c_{n-1}+b_n \quad \text{ for } n \ge 1 \end{align}$$ where $[]$ is the Iverson Bracket: $[P] = 1$ if $P$ is true, $0$ otherwise. So $[3|n]= 1$ if $3$ divides $n$, otherwise $[3|n]=0$.

Using these relations and working from $n=0$ to $n=15$, we find $c_{15} = 27$.