# n students standing in line are to be divided into teams and in each team appointed a captain. How many ways to do that? (I need last transformation)

There are $$n$$ students in the class. They stand in a line in front of the teacher, who is to divide them into any number of non-empty teams (in particular, the sets can be of size $$1$$ or $$n$$) and in each set appoint a captain. A team can only consist of students standing consecutively in the line. In how many different ways can the teacher do this?

Arrange a suitable equation or system of recursive equations and determine the general formula.

I belive that the same question was asked right here: Counting the number of ways to divide into teams - complicated

There's no concrete solution provided so I tried to get my own.

I calculated manually the numbers of sequences for some of the initial values of $$n$$:

• $$a_1 = 1$$ (because we can have just $$1$$ team and $$1$$ captain of that team)
• $$a_2 = 1 + 2 = 3$$ (because we can have $$2$$ teams in which case the captains are obvious or $$1$$ team in which case we need to choose the captain in one of $$2$$ ways)
• $$a_3 = 1 + 2 \cdot 2 + 3 = 8$$ (because we can have $$3$$ teams in which case the captains are obvious or we can have in $$2$$ ways $$2$$ teams of $$1 + 2$$ students in which case we need to choose the captain in one of $$2$$ ways or we can have one big team of $$3$$ students for which we need to choose the captain in one of $$3$$ ways)
• $$a_4 = 1 + 2 \cdot 3 + 2 \cdot 2 + 3 \cdot 2 + 4 = 21$$ (because we can have $$4$$ teams in which case the captain are obvious or we can have in $$2$$ ways $$2$$ teams of $$1 + 3$$ students in which case we need to choose the captain in one of $$3$$ ways or we can have in one way $$2$$ teams of $$2+2$$ students in which case we can choose $$2$$ captains in $$2$$ ways each or we can have in $$3$$ ways $$3$$ teams of $$1 + 1 + 2$$ students in which case we can choose captain in $$2$$ ways or we can have one big team of $$4$$ students for which we need to choose the captain in one of $$4$$ ways)

When we add one student in the line at the plece n, we have:

• one big team with n students (so we can choose the captain of that team in one of n ways) and...
• as many teams with captains as in the line of lenght n-1, but we have that one 'new student' alone in his own team and...
• as many teams with captains as in the line of lenght n-2, but we have that one 'new student' in a team of 2 (so we can choose the captain of that team in one of 2 ways) and...
• as many teams with captains as in the line of lenght n-3, but we have that one 'new student' in a team of 3 (so we can choose the captain of that team in one of 3 ways) and so on

Therefore, I thought that the recurrence equation would look like this:

$$a_n = n + a_{n-1} + 2a_{n-2} + 3a_{n-3} +...$$

As you can see while comparing with the numbers of sequences for some of the initial values of $$n$$ (those that I calculated manually above), the formula does work.

Now, from the comments below I know that the general formula needs to be of form: $$a_n = 3a_{n-1} - a_{n-2}$$

Could somebody explain to me how to get from: $$a_n = n + a_{n-1} + 2a_{n-2} + 3a_{n-3} +...$$ to: $$a_n = 3a_{n-1} - a_{n-2}$$ ?

I would like to see an algebraic way of transformation, not a proof by induction.

• That regression works...but you need to add $n$ (or just define $a_0=1$ to make the form hold).
– lulu
Commented Sep 10, 2023 at 18:55
• The sequence in question is A001906.
– lulu
Commented Sep 10, 2023 at 18:55
• @lulu where that $n$ comes from? In my interpretation - what are those $n$? Commented Sep 10, 2023 at 20:23
• I am using your notation. $n$ is the number of students. But, really, just set $a_0=1$. Makes everything simpler.
– lulu
Commented Sep 10, 2023 at 21:54
• Ok, but in the context of "story" that I provided (that starts with: "When we add one student in the line at the plece n, we have:") - why I should add that $n$? What is that $n$ in that context? @lulu Commented Sep 10, 2023 at 21:57

## 3 Answers

A generating function approach. We consider the recurrence relation \begin{align*} a_n&=3a_{n-1}-a_{n-2}\qquad\qquad n\geq 3\tag{1}\\ a_1&=1\\ a_2&=3 \end{align*} and want to show this relation fulfills \begin{align*} \color{blue}{a_n=n+a_{n-1}+2a_{n-2}+3a_{n-3}+\cdots}\tag{2} \end{align*}

Setting $$n=2$$ in the recurrence relation (1) we find from $$a_2=3a_1-a_0$$ that $$a_0=0$$. We consider the generating function \begin{align*} A(z)=\sum_{n=0}^{\infty}a_nz^n=z+3z^2+21z^3+55z^4+\cdots \end{align*}

Using the Ansatzmethode we obtain from (1) \begin{align*} \color{blue}{\sum_{n=2}^{\infty}a_nz^n} &=3\sum_{n=2}^{\infty}a_{n-1}z^n-\sum_{n=2}^{\infty}a_{n-2}z^n\tag{3}\\ &=3z\sum_{n=2}^{\infty}a_{n-1}z^{n-1}-z^2\sum_{n=2}^{\infty}a_{n-2}z^{n-2}\\ &=3z\sum_{n=1}^{\infty}a_{n}z^{n}-z^2\sum_{n=0}^{\infty}a_{n}z^{n}\\ &=3z\left(A(z)-a_0\right)-z^2A(z)\\ &\,\,\color{blue}{=\left(3z-z^2\right)A(z)}\tag{4} \end{align*}

Since the left-hand side in (3) is \begin{align*} \sum_{n=2}^{\infty}a_nz^n=A(z)-a_0-a_1z=A(z)-z \end{align*} we get from (4) \begin{align*} A(z)-z&=\left(3z-z^2\right)A(z)\\ \color{blue}{A(z)}&\color{blue}{=\frac{z}{1-3z+z^2}}\tag{5} \end{align*}

We now have to show that $$a_n$$ also fulfills the recurrence relation (2).

We consider a sequence $$b_n, n\geq 0$$ fulfilling (2) with the same starting values $$b_0=0, b_1=1, b_2=3$$ and show it has the same generating function $$A(z)$$. We start with \begin{align*} \color{blue}{b_n}&=n+b_{n-1}+2b_{n-2}+3b_{n-3}+\cdots\\ &\color{blue}{=n+\sum_{k=0}^nkb_{n-k}}\tag{6} \end{align*} and write this recurrence relation using generating functions. We get \begin{align*} \color{blue}{B(z)}&=\sum_{n=0}^{\infty}b_nz^n\tag{7}\\ &=\sum_{n=0}^{\infty}nz^n+\sum_{n=0}^{\infty}\left(\sum_{k=0}^nkb_{n-k}\right)z^n\\ &=z\sum_{n=0}^{\infty}nz^{n-1}+\left(\sum_{k=0}^{\infty}kz^k\right)\left(\sum_{l=0}^{\infty}b_lz^l\right)\tag{8}\\ &=z\frac{d}{dz}\left(\frac{1}{1-z}\right)+\left(z\frac{d}{dz}\left(\frac{1}{1-z}\right)\right)B(z)\tag{9}\\ &\,\,\color{blue}{=\frac{z}{(1-z)^2}+\frac{z}{(1-z)^2}B(z)}\tag{10} \end{align*}

Comment:

• In (8) we use the Cauchy product of power series.

• In (9) we have the derivation of the geometric series $$\sum_{n=0}^{\infty}z^n=\frac{1}{1-z}$$.

We get from (7) and (10) \begin{align*} B(z)&=\frac{z}{(1-z)^2}+\frac{z}{(1-z)^2}B(z)\\ B(z)(1-z)^2&=z+zB(z)\\ B(z)\left(1-2z+z^2\right)&=z+zB(z)\\ \color{blue}{B(z)}&\color{blue}{=\frac{z}{1-3z+z^2}} \end{align*} We conclude since the generating function $$B(z)=A(z)$$, that $$a_n, n\geq 0$$ also fulfills the recurrence relation (6) resp. (2) and the claim follows.

• I appreciate your help. I needed to get from $a_n = n + a_{n-1} + 2a_{n-2} + 3a_{n-3} ...$ to $a_n = 3a_{n-1} - a_{n-2}$, but as I said - your solution is very informative, provides much inside for anybody to understand similar problems. Thank you! Commented Sep 13, 2023 at 3:30
• @thefool: You're welcome. You might observe that you are free to start as well from (6) to (10) and continue then with (1) to (5). It's just a matter of convenience. Commented Sep 13, 2023 at 4:20

Could somebody explain to me how to get from: $$a_n = n + a_{n-1} + 2a_{n-2} + 3a_{n-3} +...$$ to: $$a_n = 3a_{n-1} - a_{n-2}$$ ?

The usual trick is to use $$a_{n-1}$$ and $$a_{n-2}$$ to cancel the sums.

For each $$n\ge 4$$ we have

$$a_n=n+\sum_{i=1}^{n-1} a_i(n-i)$$,

$$a_{n-1}=n-1+\sum_{i=1}^{n-2} a_i(n-1-i)$$.

So $$a_n-a_{n-1}=1+a_{n-1}+\sum_{i=1}^{n-2} a_i$$.

Similarly

$$a_{n-1}-a_{n-2}=1+a_{n-2}+\sum_{i=1}^{n-3} a_i$$.

So $$(a_n-a_{n-1})-(a_{n-1}-a_{n-2})=(a_{n-1}+a_{n-2})-a_{n-2}$$,

that is $$a_n=3a_{n-1}-a_{n-2}$$.

• That's what I was looking for, thank you. Commented Sep 13, 2023 at 3:30

It does work. You just need to consider $$a_0 = 1$$ since there is, so to speak, $$1$$ way of choosing if there is no student at all.

• Nonempty teams. Commented Sep 10, 2023 at 19:06
• The teams have to be non-empty Commented Sep 10, 2023 at 20:22
• Setting $a_0=1$ is a useful convention here. It makes the recurrence formula simple, doesn't matter if it makes a lot of sense on its own.
– lulu
Commented Sep 10, 2023 at 21:55
• @thefool sure, the all the teams are non-empty in that choice (since there are no teams). Commented Sep 12, 2023 at 23:36