Finding maximum ways to separate

30 Views Asked by At

Lets say I have a group a students. I am to put them into rooms, and each room must contain at least 5 students. The number of rooms can be varied, and I am to find the number of ways to do so. Question: how many ways are there to separate 100 students?

For instance if I have 11 students, there are 2 ways: (5, 6) or (11).

For an extension, is there a generalisation to this problem?

2

There are 2 best solutions below

0
On

Unless I'm oversimplifying the problem, and you don't care about the identity of which student goes to what room, I can separate $s$ students into $r$ rooms by using the floor function,$$\left\lfloor\frac{s}{r}\right\rfloor$$and then selecting a random subset of rooms to contain one extra student until the remaining $s\bmod r$ students are placed.

For instance, $\lfloor 11/2 \rfloor = 5$, so both rooms get 5 students to start, then $11\bmod 5 = 1$ which means one room gets one additional student.

Your condition of "at least 5 students per room" is a corner case, not possible if there are fewer than $5r$ students.

2
On

Suppose you have $n$ students and $m$ rooms, and that students are indistinguishable whereas rooms are distinguishable. You have to put at least $5$ students in each room, so you are left with $n-5m$ students which you can distribute in any way you like between $m$ rooms. This is a "stars and bars" problem - see https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics). The number of ways of distributing the students is

$\binom{n-4m-1}{m-1}$

as long as $n \ge 5m$.