Here is the question I'm trying to solve:
n soldiers standing in a line are divided into several non-empty units and then a commander is chosen for each unit. Count the number of ways this can be done.
My approach: Let $C(x)$ be the required generating function. Considering the type A structures on the non empty intervals as $a_k = 1$, the generating function is given as $A(x) = \sum_{k \geq 1} 1\cdot x^k$ which gives, $A(x) = \frac{x}{1-x}$.
Next the type B structures are given by $b_k = {k\choose 1} $ giving the generating function $B(x) = \sum_{k \geq 1} {k\choose 1}\cdot x^k$ which gives, $B(x) = \frac{x}{(1-x)^2}$.
Now $C(x) = B(A(x))$
Solving for $C(x)$ I get
$C(x) = \frac{x \cdot (1-x)}{(1-2x)^2}$
Is my approach correct? How do I find the coefficient of $x^n$ in $C(x)$?
Edit: Any hints on where I'm going wrong here? Because the expected answer doesn't match the answer I have calculated. Any help is appreciated.
Best Answer
I think your generating function may be wrong. In particular when $n=4$, I think it gives $20$ when I can count $21$ cases
I think if $b_{n,k}$ is the number of choices when you have $n$ soldiers and the first group has $k$ individuals then you can consider adding an additional soldier at the beginning so you can say $$b_{n+1,k+1}=\frac{k+1}{k}b_{n,k}$$ for $k\ge 1$ while $$b_{n+1,1}=\sum\limits_{k=1}^n b_{n,k}$$ which leads to results like
Since the numbers are $1,3,8,21,\ldots$ when $n=1,2,3,4,\ldots$, this leads to a generating function of the form $\dfrac{x}{1-3x+x^2}$ if you think the answer is $0$ when $n=0$, or of the form $\dfrac{1-2x+x^2}{1-3x+x^2}$ if you think the answer is $1$ when $n=0$.
This is a second order recurrence and can be solved related to $\frac{3 \pm \sqrt 5}2$ but can also be written by saying the coefficient of $x^n$ is $\text{Fib}(2n)$.