Arranging $120$ students into $6$ different groups so that the largest and smallest group differ by $2$ members

Question

In how many different ways can we arrange $120$ students into $6$ groups for $6$ different classes so that the largest group has at most $2$ members more than the smallest group?

My initial plan was to use a generating function, but I stumbled across a problem. Let's mark the groups with numbers $1$ to $6$ and let $n_i,i\in\{1,\ldots,6\}$ denote the number of members of the $i-$ th group in some arrangment. To see where this would lead me, for a moment, I assumed $n_1\le n_2\le\cdots\le n_6\le n_1+2$ in hope to find some range $\{m,\ldots M\}$ for $n_i$'s and use a generating function $f(x)=(x^m+\cdots+x^M)^6$ and find $\langle x^{120}\rangle-$ the coefficient in front of $x^{120}$, however students are distinct entities and $m$ and $M$ still remained misterious. I then tried figuring out if I was on the somewhat right track by, again taking $m=\min\{n_1,\ldots, n_6\}$ and write $n_i=m+j_i, j_i\in\{0,1,2\}.$ I believe, an arrangement with $2$ groups of $19, 2$ groups of $20$ and $2$ groups of $21$ people suggests there should be at least $19$ people in each group.

I also had a look at this problem:

The number of the partition of the set $A$ into $k$ bounded blocks.

but, again, I don't have any bounds on the blocks.

How should I proceed?

Answer 1

Let $l$ be the size of the smallest group, we get $6l \leq 120 \leq 6l+5\times 2$. Hence we must have $6l = 120$ or $6l= 114$.

If $6l = 120$ then there is $\binom{120}{20,20,20,20,20,20}/6!$ solutions as all groups have size $20$. See this related question.

So lets move to the other case. We must see the possibilities for the group sizes, each group has size at least $19$ but there is $6$ extra people if they all have size $19$, so we must find all partitions of $6$ into at most $5$ summands, such that each is at most $2$.

There are only $3$ ways:

$2,2,2$. This corresponds to groups of sizes $19,19,19,21,21,21$ for which there are $\binom{120}{19,19,19,21,21,21}/(3!3!)$ partitions.

$1,1,2,2$. This corresponds to groups of sizes $19,19,20,20,21,21$ for which there are $\binom{120}{19,19,20,20,21,21}/(2!^3)$ partitions.

$1,1,1,1,2$. This corresponds to groups of sizes $19,20,20,20,20,21$ for which there are $\binom{120}{19,20,20,20,20,21}/{4!}$ partitions.

Answer 2

You can do this a smidgen more simply (at least, it's simpler to me).

First, the average size of a group is $20$. If any group is smaller than average, then some other group must be larger than average, which means that there must be a group of size at least $21$. Thus, the smallest group must have size at least $19$.

Distribute $19$ people into each group. This can be done in $x=\binom{114}{19, 19, 19, 19, 19, 19}$ ways.

Now count the ways to distribute the remaining $6$ people across the groups with the constraint that no more than $2$ of these people can go into any group and multiply the result by $x$. The unconstrained number of solutions of $x_1 + \cdots + x_6=6$ is $\binom{11}{6}$. Using the principal of inclusion and exclusion, you must subtract the number of solutions where $x_i \geq 3$. For any $i$, there are $\binom 83$ such solutions, so you must subtract $6 \binom 83$. But you also must add back the double-counted solutions where $x_i, x_j \geq 3$, of which there are $\binom 62$.

So the answer is:

$$\left ( \binom{11}{6}-6 \binom 83 + \binom 62 \right) x.$$

Answer 3

For an another approach : When we check over the question , we see that it is distributing distingusiable objects into distinguishable boxes question. By that reason , using exponential generating function is more suitable than using ordinary generating functions.

It is given that the largest class can have at most $2$ more students than the smallest. Then , by using the reason given by @Yorch , we see that a group can have at least $19$ and at most $21$ students. Then if the groups will be distingusihable then our exponential generating function of each group will be $$\bigg(\frac{x^{19}}{19!} + \frac{x^{20}}{20!} +\frac{x^{21}}{21!} \bigg)$$

Then ,we should find the coefficient of $\frac{x^{120}}{120!}$ or find the coefficient of $x^{120}$ and multiply it by $120!$ in the expansion of $$\bigg(\frac{x^{19}}{19!} + \frac{x^{20}}{20!} +\frac{x^{21}}{21!} \bigg)^6$$

However , if the groups will be $\color{red}{\text{indistinguishable}}$ , then multiply the result of $$[x^{120}]\bigg(\frac{x^{19}}{19!} + \frac{x^{20}}{20!} +\frac{x^{21}}{21!} \bigg)^6$$ by $\frac{1}{6!}$

Then , the result is $$\frac{1}{6!} \times [x^{120}]\bigg(\frac{x^{19}}{19!} + \frac{x^{20}}{20!} +\frac{x^{21}}{21!} \bigg)^6$$

Wolfram -calculation

When we calculate the result using given coefficient in the link , the answer is $5.756410166785662e+87$