A class contains 15 students, with three students in each grade from grade 1 to grade 5. The teacher want to divide the class into five groups of three students, so that in each group, the grades of any two students differ by at most 1. How many different ways can the teacher form the groups? How should I start? Thanks. $8$ is a wrong answer. I don't know if the students are same or different. This is the exact question given to me.
[Math] Dividing a class into groups
combinatorics
Related Solutions
There are many approaches to an answer. Note that the job cannot be done if $n$ is odd. So let $n$ be even, say $n=2m$.
For concreteness, let $n=10$.
Line up the students in increasing order of student number. The first person in the list can choose her study partner in $9$ ways. For every such choice, the so far unpartnered student with smallest student number can choose her study partner in $7$ ways.
For every such choice, the so far unpartnered student with smallest student number can choose her study partner in $5$ ways. For every such choice, the so far unpartnered student with smallest student number can choose her study partner in $3$ ways. That gives a total of $(9)(7)(5)(3)$ ways.
The answer looks a little nicer if we write instead $(9)(7)(5)(3)(1)$. Maybe to make things look even nicer, we can multiply top, and missing bottom, by $(10)(8)(6)(4)(2)$. We get $$\frac{10!}{(10)(8)(6)(4)(2)},\quad\text{which is} \frac{10!}{2^5 \cdot 5!}.$$
Now that we have gone through the reasoning got $n=10$, the general case is straightforward. Suppose there are $2m$ students.
The student with lowest student number can choose her partner in $2m-1$ ways. For every such way, the so far unpartnered student with lowest student number can choose her partner in $2m-3$ ways. And then the so far unpartnered student with lowest student number can choose her partner in $2m-5$ ways, and so on, for a total of $$(2m-1)(2m-3)(2m-5)\cdots(3)(1).$$ The same manipulation as before gives the more compact expression $$\frac{(2m)!}{2^m \cdot m!}.$$
WE Tutorial School's approach of looking at graphs with parallel edges is pretty neat and simple. Here is a more painstaking way that involves tons of casework, but has the virtue of completing OP's attempt.
Let Joe's original group of 3 be Joe, Alice, and Bob.
There are $9$ choices for Joe's new partner.
Alice has $8$ choices for her partner. There are two cases to consider.
Case 1. Alice's partner was in the same group of 3 as Joe's partner. ($2$ possibilities)
Case 2. Alice's partner was not in the same group of $3$ as Joe's partner. ($6$ possibilities)
We take each case separately.
Case 1: Bob now has $7$ choices.
One person is in the same group as Joe's partner and Alice's partner. If he chooses that person, then we just need to form pairs out of the remaining two untouched groups of $3$; there are $6$ ways to do that.
Otherwise, Bob chooses one of the $6$ people in the two untouched groups of $3$. Now there remains an untouched group of $3$, another group with $2$ people left, and another group with $1$ person left. There are $6$ ways to pair them up, since each pair must contain one person from the untouched group of $3$.
Case 2: Bob also has $7$ choices in this case. There is one untouched group of $3$, and two groups of two people each.
If Bob chooses someone from a group of $2$ ($4$ ways to do this), then there are again $6$ ways to pair up the remaining $6$ people.
If Bob chooses someone from the group of $3$ ($3$ ways to do this), then there are three groups of $2$ left. There are $8$ ways to pair them up.
Combining everything we have $$9 \cdot (2 \cdot (1 \cdot 6 + 6 \cdot 6) + 6 \cdot (4 \cdot 6 + 3 \cdot 8)) = 3348.$$
Best Answer
Let $f(n)$ be the number of ways to sort the $3n$ students into $n$ trios, with the condition imposed.
Therefore we have $$f(n)=f(n-1)+9f(n-2)$$ with the starting values $f(1)=1,\ f(2)=10$.
This is equivalent to Emperor of Ice Cream's second solution. The other solutions are correct if we are looking only for the number of schemes (e.g. 111-223-233-445-455). The answer to the original question is $$f(5)=280.$$.