Dividing a class into groups 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.
 A: Let $f(n)$ be the number of ways to sort the $3n$ students into $n$ trios, with the condition imposed.


*

*Suppose all three students in grade $n$ are together. There is $1$ way to put them together, and then $f(n-1)$ way to put everyone else into trios.

*Suppose two students in grade $n$ are together. The third student must be in grade $n-1$. That means that there is another trio containing one student in grade $n$ and two students in grade $n-1$. There are $9$ ways to arrange this, and then $f(n-2)$ ways to put the younger students into trios.


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.$$.
A: Consider the generalisation of the problem to $3n$ students, and let $a_n$ be the number of ways of forming the groups.  (So you want $a_5$.)  If we begin by arranging the students from grade $n$, here are the possibilities.


*

*Put them all into one group.  Then arrange the remaining students: this can be done in $a_{n-1}$ ways.

*Put two in one group and one in another.  To complete these groups we may only use students from grade $n-1$, and there is only one way to place these students; then we have to arrange the remaining students, which can be done in $a_{n-2}$ ways.

*You could try putting the grade $n$ students into three separate groups, but this will not work.  I'll leave it to you to figure out the reason why.


Therefore
$$a_n=a_{n-1}+a_{n-2}\ ,$$
and it is easy to find the initial conditions $a_1=1$ and $a_2=2$.  So the answer is given by the (shifted) Fibonacci numbers, and in particular, $a_5=8$.

Edit in response to clarification of the question.  If the students are regarded as distinguishable, we require a modification in the second step above.


*

*Put two in one group and one in another.  To complete these groups we may only use students from grade $n-1$, and we have to choose which student from grade $n$ goes with the two grade $n-1$ students, and which from grade $n-1$ goes with the grade $n$ students.  There are $9$ ways to make these choices, and then we have to arrange the remaining students, which can be done in $a_{n-2}$ ways.


So the recurrence and initial conditions become
$$a_n=a_{n-1}+9a_{n-2}\ ,\quad a_1=1\ ,\quad a_2=10\ .$$
Iterating, we have
$$a_3=19\ ,\quad a_4=109\ ,\quad a_5=280\ .$$
Alternatively, the recurrence can be solved by standard methods to give the general formula
$$a_n=\frac1{\sqrt{37}}\left(\Bigl(\frac{1+\sqrt{37}}{2}\Bigr)^{n+1}
  -\Bigl(\frac{1-\sqrt{37}}{2}\Bigr)^{n+1}\right)\ .$$
If you like you can now expand both powers by the binomial theorem: you will find that every second term cancels, leaving you with
$$a_n=\frac1{2^n}\sum_{m=0}^{\lfloor n/2\rfloor}\binom{n+1}{2m+1}37^m\ .$$
A: There are three cases that group students such that the grades of no two students in the group differ by more than one.


*

*All three students in a group are in the same grade

*Two students in a group are in the same grade, one student is in the grade above.

*Two students in a group are in the same grade, one student is in the grade below.


So if we start by placing all students in the same grade into a group, then we need to count the ways we can swap students between two groups that are adjacent, and that each group swaps just once.
We can make at most two such swaps.  Example: if one of the three grade 1 student swaps with one of the three grade 2 students and one of the three grade 4 students swaps with one of the three grade 5 student, then none of the grade 3 student can swap out.
Now count the ways to make 0, 1, or 2 swaps.
A: Assuming all students of the same grade are identical:
We can find a recursion: We write the problem a little more generally: There are $3n$ students in a classroom, in how many ways can we split them in groups of $3$ so that the grades of any two students differ by at most one, call this number $a_n$.
It is clear $a_1=1$ and $a_2=3$. 
We prove the recursion $a_n=a_{n-1}+2a_{n-2}$
In how many ways are the students of grade $1$ all together? Clearly $a_{n-1}$
In how many ways are the students of grade $1$ not all together? The students end up in two groups, one of $1$ and one of $2$, and these groups take up all of the students of grades $1$ and $2$. so there are $a_{n-2}$ of these.
Hence $a_n=a_{n-1}+a_{n-2}$.

If we do not assume all students are identical the problem becomes slightly harder. But a similar argument works. Notice that the previous argument shows that when dividing into groups all we have to do to determine an arrangement is select some pairs of adjacent grades and pair them up (meaning the students of grades $k$ and $l$ are together in two groups. Suppose we are told how to arrange the students if all of the students where equal , how many different ways can the children be put in  this arrangement? (When students are not considered identical)
The argument above shows us that the arrangement basically consists of some pairs of consecutive integers (It tells us which pairs of grades are to be combined into two groups, and which grades are composed of one class containing all three students). The only choices we can take are with the students of grades which do not have all their students in one class. If grades $j$ and $j+1$ are paired up we can choose in $3$ ways the student of grade $j$ that is alone and in $3$ ways the student of $j+1$ that will be alone. Do for each pair of "entangles" students there are $9$ options. So if our initial arrangement of the $n$ students consisted of $j$ pairs of grades and $n-2j$ alone grades there are $9^j$ different arrangements which "look the same" when the students are equal.
How many arrangements consist of $j$ entangled pairs of  grades and $n-2j$ alone grades? Consider $j$ blocks of length $2$ and $n-2j$ block of length $1$, in how many ways can we put them in a line? There are $n-j$ objects to arrange, and we must select the positions for $j$ of them. Therefore $\binom{n-j}{j}$.
Therefore there are:
$$\sum\limits_{j=0}^{\lfloor n/2 \rfloor} \binom{n-j}{j}9^j$$
Different ways to separate the students.
A: Write out the options explicitly, using $N=\{N,N,N\}$ and $NM=\{N,N,M\}$. We get:
No swaps:


*

*1 2 3 4 5


Swap once:


*

*12 3 4 5

*1 23 4 5

*1 2 34 5

*1 2 3 45


Swap twice:


*

*12 34 5

*12 3 45

*1 23 45


So $8$ in total.
If the individual students are to be counted, each swap has $9$ variations, and so we get $1+4.9+3.81=1+36+243=280$ possible groupings.
