2
$\begingroup$

I would like to calculate the number of ways in which we can split $N$ members into $k$ different in size teams, $k<N$. Let $n_i$ be a size of $i$th team, and $1\leq n_i \leq N$, then $n_1+n_2+...+n_k=N$.

My solution is based on the Multinomial theorem, question1, and question2.

At first step, we can choosing $n_1$ members from $N$ members by $C_N^{n_1}$ ways. At second step, from the remaining $N − n_1$ members choose $n_2$ members. This can be done $C_{N-n_1}^{n_2}$ ways. At $(k-1)$th step, we can choosing $n_{k-1}$ members from the remaining $N-(n_1+n_2+...+n_{k-1})$ members by $C_{N-(n_1+n_2+...+n_{k-1})}^{n_{k-1}}$ ways. At the $k$th we can choosing $n_k$ members from $n_k$ members by $C_{n_k}^{n_k}=1$ way. Multiplying the number of choices at each step results in:

$\underbrace{C_N^{n_1} \times C_{N-n_1}^{n_2} \times \ldots \times C_{N-(n_1+n_2+...+n_{k-1})}^{n_{k-1}} \times C_{n_k}^{n_k}}_{k \text{times}}$.

For instance, if $N$=20, $k$=4, and $n_i=N/k=20/4=5$, $i=1,2, \ldots, k$, we have the number of ways in which we can split $N=20$ members into $k=4$ teams of equal size:

a) labeled teams $Num1=C_{20}^5 C_{15}^5 C_{10}^5 C_{5}^5=\frac{20!}{15!5!}\frac{15!}{10!5!}\frac{10!}{5!5!}\frac{5!}{5!0!}$.

b) unlabeled teams $Num2=\frac{1}{4!}Num1$.

update:

After the N.F. Taussigs' answers:

In common case, when $n_1 \neq n_2 \neq \ldots \neq n_k$:

$Num=\underbrace{\frac{n_1}{N} \frac{n_2}{N-n_1} \times \ldots \times \frac{n_{k-1}}{N-(n_1+n_2+...+n_{k-1})} \times \frac{n_k}{n_k}}_{k \text{times}}\times \underbrace{C_N^{n_1} \times C_{N-n_1}^{n_2} \times \ldots \times C_{N-(n_1+n_2+...+n_{k-1})}^{n_{k-1}} \times C_{n_k}^{n_k}}_{k \text{times}}$

update 2:

Additional condition: to the each member $1, 2, \ldots N$ assigned an integer number from the range $[1, k]$. This number correspond to preferences on the number of possible teams, i.e. '1' means that a member can be to distribute only into one team; '2' means that a member can be to distribute into two team, ... '$k$' means that a member can be to distribute into all $k$ teams.

My question is: How to apply this condition to the formula in common case?

$\endgroup$
  • $\begingroup$ That is correct but you can simplify = $N!\over n_1!\times n_2!\times n_3!\times...$. $\endgroup$ – user202729 May 9 '16 at 10:01
  • $\begingroup$ If the teams are distinct i think your method is right , but if they are not there might be repition $\endgroup$ – avz2611 May 9 '16 at 10:02
  • $\begingroup$ Your answer is correct if the teams are labeled. If they are not labeled, you have to divide by the number of orders in which teams of equal sizes can be formed. $\endgroup$ – N. F. Taussig May 9 '16 at 10:08
  • $\begingroup$ @N.F.Taussig, thanks for reply. What is the number of orders in my case? (k-1)! or k! $\endgroup$ – Nick May 9 '16 at 11:53
  • $\begingroup$ In your example, you have four teams. The same four five-member teams could be assembled in any order, so divide by $4!$. Keep in mind that another way of writing your answer for four labeled teams of size $5$ is $$\binom{20}{5}\binom{15}{5}\binom{10}{5}\binom{5}{5}$$ so the number of ways of choosing unlabeled teams is $$\frac{1}{4!}\binom{20}{5}\binom{15}{5}\binom{10}{5}\binom{5}{5}$$ More generally, if you have $k$ unlabeled teams of equal size, divide the number of labeled teams by $k!$. $\endgroup$ – N. F. Taussig May 9 '16 at 11:59

Your Answer

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

Browse other questions tagged or ask your own question.