Find the number of ways the commander can be chosen 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.
 A: We use $$\frac{1}{(1-2x)^2}=1+2(2x)+3(2x)^2+....$$
Hence $$C(x)=(x-x^2)(1+2(2x)+3(2x)^2..)$$
So, coefficient of $x^n$ is $n.2^{n-1}-(n-1)2^{n-2}$.
Hence the answer is $(n+1)2^{n-2}$
A: 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

*

*$b_{n,k} = k\, b_{n+1-k,1}$

*$b_{n+1,1} = b_{n,1}+ \sum\limits_{m=1}^n b_{m,1}$

*$b_{n+1,1}=3b_{n,1}-b_{n-1,1}$

*sine the number you want $a_n = b_{n+1,1}$: $$a_{n,1}=3a_{n-1,1}-a_{n-2,1}$$
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)$.
