The problem is : $n$ boys and $n$ girls go out to dance. How many ways so they all dance simultaneously (only couples of different sex can dance together) ?
My thinking is we can look at it as $2n$ ordered slots
So lets say $n = 3$, then we have _ _ _ _ _ _
For the first slot, we can choose any of the $3$ boys, and for the second any of the $3$ girls. $3~3$ _ _ _ _
For the next $2$ slots, we have $2$ boys and girls respectively $3~3~2~2$ _ _
and finally $3~3~2~2~1~1$
That would give us $3 \cdot 3 \cdot 2 \cdot 2 \cdot 1 \cdot 1 = 36$ arrangements or $3! \cdot 3!$.
If we take one example arrangement lets say $B_1G_1B_2G_2B_3G_3$, amongst the $36$ arrangements we will have counted it $3!=6$ times since $B_1G_1B_2G_2B_3G_3 = B_2G_2B_1G_1B_3G_3$ etc… So we divide by $3!$ to get $6$.
My questions:
-
Is this a valid argument for why the general form answer is $n!$ ?
-
What other ways to reason about this problem are there?
Best Answer
You gave a valid argument for the case $n = 3$.
For the general case, we can line up the boys in $n!$ ways and the girls in $n!$ ways, then match the $k$th boy in the boys' line with the $k$th girl in the girls' line to form $n$ couples. This gives $n!n!$ ways of selecting the couples. However, we have counted the same set of couples $n!$ ways, once for each way we could have lined up the same $n$ couples (or, equivalently, the number of ways we could have lined up the girls). Therefore, the number of ways the dance partners can be selected is $$\frac{n!n!}{n!} = n!$$
Here is a simplified version of your argument: Line up the girls in some order, say alphabetically. There are $n!$ ways of lining up the boys. Match the $k$th girl in the line with the $k$th boy in the line to determine the dance partners. Hence, there are $n!$ ways to form the dance partners.
By fixing the order of the girls, we eliminate the need to divide by the $n!$ orders in which the same $n$ couples could be formed.