\problemdata     
{S01-PS7-3}           
{counting, permutations, division rule}              
{} 		
{S01-PS7}
{S01 Karger}


\begin{problem}

 Your 6.042 tutorial has 12 students, who are supposed to break up into 4 groups of 3 students each. Your TA has observed that the students waste too much time trying to form balanced groups, so he decided to pre-assign students to groups and email the group assignments to his students.

\problempart {\bf 1 point} Your TA is the laziest person on the
planet. He has a list of the 12 students in front of him. How would
he form groups of 3?

\solution{\textbf{Solution:}
\medskip
The TA would divide the list from the top down.}

\problempart {\bf 9 points} How many \emph{different} group
assignments are possible? (Clarification: There is no ``numbering" of
the groups. All that matters is who ends up with whom. Two group
assignments are different if they differ in at least one group.)
\solution{

\textbf{Solution:}
\medskip

Notice the similarity to Problem 2 in Tutorial 8, which asked you to find in how many ways $2n$ students can be divided into $n$ pairs. The answer was $\frac{(2n)!}{2^n\cdot n!}$ where the numerator represents the different permutations of the list of students, and the denominator represents the number of different permutations that give rise to the \emph{same} grouping. 
 
In this problem, say the list is ABCDEFGHIJKL. The lazy TA's policy gives the following grouping: \fbox{ABC}\fbox{DEF}\fbox{GHI}\fbox{JKL}. There are $12!$ different permutations of the list. However, not all permutations result in a different group assignment. For example, if B and C change places, the list is different but the assignment is the same. We will try to see how many different lists represent the \emph{same} group. 

There are $3!$ ways to move the people in \fbox{ABC} around without changing the assignment. The same holds for all other groups. This means that there are $(3!)^4$ ways to move people around within their group.
 
Then, if \fbox{ABC} switches places with \fbox{JKL} we still get the same assignment. There are $4!$ ways to permute the groups without actually affecting the assignment. 

So, there are $4! (3!)^4$ different lists that end up producing the same assignment. 

There are $12!$ possible lists, and each assignment is represented by \emph{exactly} $4! (3!)^4$ different lists so according to the \emph{division rule} there are 
\[
\frac{12!}{4!\cdot(3!)^4}=15400
\]
 different assignments.

\paragraph{Alternative solution} Another way to see this is as follows:

We need to compute the number of partitions of a set of 12~students
into 4~groups of 3~students each. We first compute the number of
partitions given that the groups are numbered. The first group can be
selected in $\binom{12}{3}$ ways, the second in $\binom{9}{3}$ ways,
the third in $\binom{6}{3}$ ways, and the fourth in $\binom{3}{3}$
ways. Therefore, the number of different partitions is
\begin{displaymath}
  \binom{12}{3}\binom{9}{3}\binom{6}{3}\binom{3}{3}
  =
  \frac{12!}{(3!)^4}= 369600.
\end{displaymath}
Now, to account for the fact that the groups are not numbered, we need
to divide $369600$ by the number of permutations of the numbered
groups, $4! = 24$. To conclude, the number of tutorials we can have in
6.042 is at most $369600 / 24 = 15400$.
}

\end{problem}
