1
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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 $

$\endgroup$
1
$\begingroup$

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

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