There are $40$ students who must be assigned to $4$ supervisors. And each supervisor must have at least $8$ students, then how many ways students can be assigned?

I tried a lot but not able to think about it, it is not a homework problem. I am taking combinatorics in fall, so I started studying on my own.


closed as off-topic by Brian Borchers, Namaste, Saad, Claude Leibovici, John B May 22 '18 at 15:55

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Brian Borchers, Namaste, Saad, Claude Leibovici, John B
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ For problems like this it is important to specify details. Are the students distinguishable from one another? Are the supervisors? Suppose I have three students and two supervisors and require that each supervisor have at least one student. What is the answer then? $\endgroup$ – lulu May 21 '18 at 23:07
  • 2
    $\begingroup$ This is an unfortunately tedious problem. I see little way around this beyond finding all of the different ways of distributing the amount of students to each advisor and then for each such way of distributing the amounts count how many ways the students could be assigned in those amounts. For example, you could have them split up as $8,8,10,14$ where the first supervisor gets eight, the second gets eight, the third gets 10 etc... which the students could be assigned in that fashion in $\binom{40}{8,8,10,14}=\frac{40!}{8!8!10!14!}$ number of ways. $\endgroup$ – JMoravitz May 21 '18 at 23:08
  • 1
    $\begingroup$ @Daugmented you will overcount doing it like that. $\endgroup$ – JMoravitz May 21 '18 at 23:08
  • $\begingroup$ Yep, sorry, that true... $\endgroup$ – Daugmented May 21 '18 at 23:10
  • $\begingroup$ @JMoravitz , third supervisor can also be assigned with 8 students and 4th with 16. Can you explain it little more $\endgroup$ – Randhawa May 21 '18 at 23:15

You can take a generating function approach here. That is, you let $x$ be an indeterminate and find the $40!$ times the coefficient of $x^{40}$ in $$\left(\frac{x^8}{8!} + \frac{x^9}{9!} + \cdots + \frac{x^{16}}{16!}\right)^4.$$

The reason this works is that when you expand the product in all possible ways, factoring out a factorial of the degree, each product has a multinomial coefficient. For example, taking $$\frac{x^{11}}{11!} \frac{x^9}{9!} \frac{x^8}{8!} \frac{x^{12}}{12!} = \frac{40!}{11!\, 9!\, 8!\, 12!}\frac{x^{40}}{40!} $$ and multiplying by $40!$ gives the coefficient $$\frac{40!}{11!\, 9!\, 8!\, 12!}$$ which is the number of ways of choosing groups where the first supervisor has $8$ students, the second supervisor has $9$ students, etc. You only have to go up to degree $16$ in each factor because no group can have more than $16$ people.

Of course, expanding this out completely is equivalent to adding up all the possible multinomials corresponding to how many students each supervisor takes as JMoravitz mentions. But software packages like Sage are optimized to do this kind of convolution pretty quickly.

Edit: In Sage,

p = sum([x^n / factorial(n) for n in range(8, 17)])
q = (p^4).expand()
print q.coefficient(x,40) * factorial(40)

prints $435451605680654896510320$.

  • $\begingroup$ This one looks correct. As I am satisfied with solution, So, accepting as an answer but I will add some opinions in Fall, if I had. $\endgroup$ – Randhawa May 21 '18 at 23:47

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