Easy generating functions task from concrete mathematics book

239 Views Asked by At

This question might seem very novice, but i'm not sure about the solution.

We have domino puzzle of size $2 \times\ n$ and we get 4 points for every vertical block and 1 point for horizontal block, every block is size of $2 \times 1$. How many possibilities are there to get exactly $m$ points? For $m=6$ there are 3 possibilities, $\text{VHH}$,$\text{HHV}$,$\text{HHHHHH}$

My attempt: I know it's easy to make this task without generating functions, but it's just an exercise for G.F.

Let's make sequences$$a_n = <1, x^2, x^4, x^6, x^8,\dots >$$ $$b_n = <1,x^4,x^8,x^{12},x^{16},\dots>$$

Exponential generating function(egf) for $a_n$ will be $$\sum a_n\frac{z^n}{n!}$$ and for $b_n$ will be $$\sum b_n\frac{z^n}{n!}$$

And multiplying those two series should give us some new series and answer for $m$(excluding odd $m$ of course, answer here is always 0) is coefficient standing next to $z^m$, but i'm not getting true answer for any $m$. I'd appreciate some help on this task, thanks in advance.

1

There are 1 best solutions below

2
On BEST ANSWER

To tile a $2 \times n$ board, horizontal ($1 \times 2$) blocks must always be used in pairs, one below the other.

As we care about both size (width) and "points", we need a bivariate generating function. Let's use the variable $z$ to mark size, and $u$ to mark points. Then a vertical block corresponds to $zu^4$, and a pair of horizontal block corresponds to $z^2u^2$. Any tiling is a sequence of these, so the class of all configurations is

$$\mathcal{C} = \operatorname{S\scriptsize EQ}(\mathcal{V} + \mathcal{HH}) \implies C(z, u) = \frac{1}{1 - (zu^4 + z^2u^2)}$$

The coefficient of $z^nu^m$ in $C(z)$ gives the answer (number of ways to tile a $2 \times n$ board, and get exactly $m$ points).

If you want to allow all possible values of $n$, just set $z = 1$: then we have

$$C(u) = \frac{1}{1-(u^4 + u^2)} = 1 + u^2 + 2u^4 +3u^6 + 5u^8 + O(u^{10})$$

and you look at the coefficient of $u^m$ in it: indeed the coefficient of $u^6$ is $3$.