1
$\begingroup$

$n$ students are standing in a row. Teacher must divide them into smaller teams - it could be one team or more - (team must consist of students standing next to each other in a row) and choose in every team a team leader. On how many ways he can do it?

I know how to calculate numbers of solution of the equasion

$x_1 + x_2 + \ldots + x_k = n$, where $x_i\in\mathbb{Z}$ and $x_i\ge 0$.

I have no idea how to attack version with team leaders.

$\endgroup$
  • $\begingroup$ It's just number of arrangements cleared from number of local arrangements in each subset, where number of subsets are the sum of combination from 0 to n from n, it's long and complicated yes with inclusion/exclusion principle. $\endgroup$ – Abr001am Aug 23 at 0:50
1
$\begingroup$

How do you tackle any enumerative combinatorics question? First look at the structure and try to find a recurrence. Here the first person in the row must be in a team of some size: having fixed the size, the number of possibilities for the team leader of that team is known and independent from the number of ways of teaming up the rest of the row.

This gives a recurrence which is easily (in this case) transformed into a closed form generating function, which you should find looks rather familiar.

$\endgroup$
  • $\begingroup$ Thanks, I did not thought about finding recurrence equation. It turned out to be a very simple problem, thanks again. $\endgroup$ – Maciej Aug 24 at 13:31
0
$\begingroup$

Suppose we have a single team of $n$ students. The number of ways to designate a leader is simply $n$; so the exponential generating function of the number of ways to designate a leader is $$T(z) = \sum_{n=0}^{\infty} n \cdot \frac{1}{n!} z^n = \sum_{n=1}^{\infty} \frac{1}{(n-1)!} z^n = z e^z$$ The organization of all the students into teams with leaders is the set of all teams with leaders. So its exponential generating function is $$e^{T(z)} = e^{z e^z}$$

The reader unfamiliar with generating functions might find this question and its answers useful: How can I learn about generating functions?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.