Find the number of ways the commander can be chosen

combinatoricsgenerating-functions

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

  • $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)$.

Related Question