Counting: Distribute n students in 3 teams.

95 Views Asked by At

In how many ways is it possible to distribute a set of n students listed from 1 to n in three different teams so that no team is left without members?

Taking partitions into account this is what I have:

$$ \sum_{i=1}^{n-2} \sum_{j=i}^{n-2} \binom{n}{(i) \: (j) \: (n-(i+j))} $$

However, I think I'm adding some 'extra' partitions. For example, with $ n=6 $, when $ i=1, j=1, $ and the rest is $ 4 $, it's the same that $ i=1, j= 4 $ and the rest is $ 1 $. How can I avoid that?

2

There are 2 best solutions below

0
On BEST ANSWER

In this answer it is preassumed that students are distinguishable and teams are distinguishable. The first assumption is a natural one. The second a bit less, but is encouraged by the use of the terms "different teams" in your question.


If every student is placed in exactly one of the teams $1,2,3$ without further conditions then there are $3^n$ distributions.

Let $A$ denote the distributions such that team $1$ stays empty.

Let $B$ denote the distributions such that team $2$ stays empty.

Let $C$ denote the distributions such that team $3$ stays empty.

Then to be found is: $$|A^{\complement}\cap B^{\complement}\cap C^{\complement}|=3^n-|A\cup B\cup C|$$ and with inclusion/exclusion and symmetry we find:$$|A\cup B\cup C|=3|A|-3|A\cap B|=3\cdot2^n-3$$So our final answer is:$$|A^{\complement}\cap B^{\complement}\cap C^{\complement}|=3^n-3\cdot2^n+3$$

0
On

In your expression, you cannot have $1\le i,j\le n-2$ in general ($i+j$ will surpass $n$).

Here's an approach using binomial coefficients. For each $i$ between $1$ and $n-2$ you have ${n\choose i}$ ways for the first team, and for each $j$ between $1$ and $n-i-1$ you have ${n-i\choose j}$ ways to form the second team (the -1 so that at least one is left-over for the third team). Then the third team is determined.

The number of formations is then:

$$\sum_{i=1}^{n-2}\sum_{j=1}^{n-i-1} {n\choose i}{n-i\choose j}$$

Which is equivalent to

$$\sum_{i=1}^{n-2}\sum_{j=1}^{n-i-1} {n\choose (i) \ (j) \ (n-i-j)}$$