Ways of constructing 10 unit high tower w/ infinite # blocks 1, 2, & 3 units high?

85 Views Asked by At

A variation of this question has already been asked here, but I wish to solve via generating function.

My question's answer is equivalent to the bijection...

$$ card\left(\left\{\left[x_1\;x_2\;x_3\right]^T\in \mathbb{W}^3 : 1x_1 + 2x_2 + 3x_3 = 10\right\}\right) \\ = \left[x^{10}\right]\left(x^0 + x^1 + \cdots + x^{10}\right)\left(x^0 + x^2 + \cdots + x^{10}\right)\left(x^0 + x^3 + \cdots + x^9\right) $$

2

There are 2 best solutions below

3
On BEST ANSWER

As no one's had a go at answering this I'll give it a shot. In the comments you state that the order of the blocks is important which makes me think you need to keep track of the different types of block which I don't think the set up of the answer you suggest in the question can do. So I think you need to consider, $$\left[x^{p}y^{q}z^{r}:p+q+r=10\right]$$$$\left(x^0 + x^1 + x^2 +\cdots \right)\left(y^0 + y^2 + y^4 +\cdots \right)\left(z^0 + z^3 +z^6+ \cdots \right)$$ Wolfram Alpha would expand this for you, but as there's only 14 bits, I'll give it a go by hand; $$x^{10}y^0z^0:1 : {10 \choose 1}$$ $$x^8y^2z^0:9: {9 \choose 1}or{9 \choose 8}$$ $$x^7y^0z^3:8:{8 \choose 1} or {8 \choose 7}$$ $$x^6y^4z^0:28:{8 \choose 2} or {8 \choose 6}$$ $$x^5y^2z^3:42: \frac{7!}{5!1!1!}$$ $$x^4y^6z^0:35: {7 \choose 3} or {7 \choose 4}$$ $$x^4y^0z^6:15: {6 \choose 2} or {6 \choose 4}$$ $$x^3y^4z^3: 60 : \frac{6!}{3!2!1!}$$ $$x^2y^8z^0:15: {6 \choose 2} or {6 \choose 4}$$ $$x^2y^2z^6:30: \frac{5!}{2!1!2!}$$ $$x^1y^6z^3:20:\frac{5!}{1!3!1!}$$ $$x^1y^0z^9:4 : {4 \choose 1}or{4 \choose 3}$$ $$x^0y^{10}z^0:1 : {10 \choose 0}$$ $$x^0y^4z^6: 6 : {4 \choose 2}$$ Phew!

I make that 274 different ways of building the tower.

0
On

Following on from your comment that you got the same answer by solving the recurrence relation, that too is amenable to a generating function approach.

Given you have that, $$a_n=a_{n-1}+a_{n-2}+a_{n-3}, a_1=1, a_2=2, a_3=4$$ Start with the deduction that $$a_{0}=1$$ then get the generating function (I can provide more detail if required), $$GF=\frac{1}{1-x-x^2-x^3}$$ which expands as, $$1+x+2x^2+4x^3+7x^4+13x^5+24x^6+44x^7+81x^8+149x^9+274x^{10}+504x^{11}+\dots$$ and there's the part we want just sitting there; $$274x^{10}$$ Resource : I expanded the brackets using the online Taylor Series Expansion Calculator at https://www.numberempire.com/taylorseriesexpansion.php

Other Generating Function Resources was the subject of a recent post on MSE at : How can I learn about generating functions?