prove the identity using combinatorics Question:
prove combinatorically that $$\frac{(2n)!}{(n!2^n)}$$  is an integer.
I've tried to explain that if we have n white flowers and n different colorfull flowers,
ans we need to arrarnge them in a row, so the solution is $(2n)!/n!$...
I don't know what is the condition that I need in order to get the $2^n$...
Thank you.
 A: The number of ways of arranging $n$ white and $n$ different colourfull flowers is indeed equal to $\binom{2n}{n} \cdot n! = \frac{(2n)!}{n!}$. However, I don't see an easy way to introduce the $2^n$.
To get the desired expression, a different combinatorial model can be used. For instance, consider the number of ways to pair up $2n$ people. This can be done by first arranging the people in a row ($(2n)!$ possibilities) and then choosing the first and second person, the third and fourth, etcetera. We can order the pairs in $n!$ ways and order the people in each pair in $2$ ways, hence we have to divide $(2n)!$ by $n! 2^n$.
A: Consider this problem: a mega-spider has $n$ legs.  Under the requirement that for each leg the spider has to put on a sock before putting on a shoe, how many ways can the spider put on $n$ identical socks and $n$ identical shoes?
A: I'd like to add a short remark to the answer already given from user133281, since I think one argument is missing to completely answer the question. user133281 provides us with two fine models. The first model places $2n$ people in a row, which can be arranged in $(2n)!$ ways. The second gives us $n$ pairs, which can be arranged in $n!$ ways and within each pair both people can exchange their position, resulting in a factor $2^n$ for each of the $n$ pairs, giving a total of $n!2^n$. Now we have to act carefully. At this point we can only conclude that $$n!2^n<(2n)!$$ and we (additionally) have to argue, that $n!2^n$ divides  $(2n)!$ in order to show that $(2n)!/(n!2^n)$ is an integer. Of course, simple calculation gives the result immediately, since e.g. by using double factorial notation you have $(2n)!=(2n)!!(2n-1)!!=(n!2^n)(2n-1)!!$ showing that $(2n)!$ is an integer multiple of $n!2^n$.
But we should give a combinatorial proof. So, we ask in how many ways can we select $n$ pairs. No significance attaches to the order of the $n$ pairs, nor the order within each pair, since we already know, there are $n!2^n$ different possible arrangements for one specific selection. All that matters now is who is together and who is apart. For a person in the first pair there are $2n-1$ different possibilities to complete this pair. For a person in the second pair there are $2n-3$ different possibilities to choose from the remaining people to complete this pair. Proceeding this way gives a total of $(2n-1)(2n-3)\cdot\ldots\cdot3\cdot1=(2n-1)!!$ different possibilities for selecting $n$ pairs. Now we have exhausted all possible arrangements of $2n$ people showing, that $(2n)!$ is a multiple of $2^nn!$. And so we can conclude, that $(2n)!/(2^nn!)$ gives an integer. :-)
