Difference between distributing (distinguishable/indistinguishable) objects into groups

224 Views Asked by At

I'm having a bit of problem doing the following:

1) Number of ways to distribute 7 (different) students in 4 (non empty) teams:

  1. $490$
  2. $350$
  3. $560$
  4. $210$

My understanding this is the Stirling number of the second kind and we can use inclusion-exclusion: $$S(7,4)=\frac{1}{4!}\sum_{j=1}^4(-1)^{4-j}\binom{k}{j}j^n=\frac{1}{24}(-4+768-8748+16384)=\frac{8400}{24}=350.$$

2) Number of ways to distribute 7 tutors into 4 departments where each department must get at least 1 tutor:

  1. $350$
  2. $4200$
  3. $1400$
  4. $8400$

I don't quite see the difference here. How does the fact that the "tutors" are not distinguishable affect this?

1

There are 1 best solutions below

0
On BEST ANSWER

People are considered to be distinguishable unless otherwise specified. The difference between the two questions is that departments are distinguishable while unlabeled teams are not.

Number of ways to distribute $7$ students to $4$ (nonempty) teams.

Your answer of $S(7, 4) = 350$ is correct since the teams are not labeled.

Number of ways to assign $7$ tutors to $4$ departments so that each department receives at least one tutor.

Since departments are distinguishable (the mathematics department is different from the physics department), the answer to this question is $$4!S(7, 4) = \sum_{k = 0}^{4} (-1)^k \binom{4}{k}(4 - k)^7 = 4^7 - \binom{4}{1}3^7 + \binom{4}{2}2^7 - \binom{4}{3}1^7 + \binom{4}{4}0^7 = 8400$$ where $\binom{4}{k}$ is the number of ways of excluding $k$ of the $4$ departments from receiving a tutor and $(4 - k)^7$ is the number of ways of distributing the $7$ students to the remaining $4 - k$ departments.