[
1
This is a screen shot of a problem and solution from Stanley vol 2 but I tried working it out and I can not figure it out. The only thing that I could relate is that $$G(x)= \frac{1}{\sqrt{1-6x-x^2}}$$. Would anyone be kind to explain the solution to me? Thanks.
If $A(x) = \sum_{n \ge 0} a_n x^n$ is the generating function for some class $\mathcal{A}$ of objects, then $\frac{1}{1-A(x)} = 1 + A(x) + (A(x))^2 + \cdots$ is the generating function of the collection of all sequences of objects from $\mathcal{A}$.
$K(x) + P(x)$ is the generating function of steps of types (i) and (ii), while $K(x) + 2P(x)$ is the generating function of steps of all three types.
Since $H(x)$ is the generating function of sequences of steps of types (i) and (ii), it is $H(x) = \frac{1}{1-(K(x) + P(x))}$. Similarly, $G(x) = \frac{1}{1 - (K(x) + 2P(x))}$.