Editing Combinatorial proof (section)

==Example==
An archetypal double counting proof is for the well known formula for the number <math>\tbinom nk</math> of ''k''-[[combination]]s (i.e., subsets of size ''k'') of an ''n''-element set:
:<math>\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}.</math>
Here a direct bijective proof is not possible: because the right-hand side of the identity is a fraction, there is no set ''obviously'' counted by it (it even takes some thought to see that the denominator always evenly divides the numerator). However its numerator counts the [[Cartesian product]] of ''k'' finite sets of sizes ''n'', {{nowrap|''n'' − 1}}, ..., {{nowrap|''n'' − ''k'' + 1}}, while its denominator counts the [[permutations]] of a ''k''-element set (the set most obviously counted by the denominator would be another Cartesian product ''k'' finite sets; if desired one could map permutations to that set by an explicit bijection). Now take ''S'' to be the set of sequences of ''k'' elements selected from our ''n''-element set without repetition. On one hand, there is an easy bijection of ''S'' with the Cartesian product corresponding to the numerator <math>n(n-1)\cdots(n-k+1)</math>, and on the other hand there is a bijection from the set ''C'' of pairs of a ''k''-combination and a permutation ''σ'' of ''k'' to ''S'', by taking the elements of ''C'' in increasing order, and then permuting this sequence by&nbsp;''σ'' to obtain an element of&nbsp;''S''. The two ways of counting give the equation
:<math>n(n-1)\cdots(n-k+1)=\binom nk k!,</math>
and after division by ''k''! this leads to the stated formula for <math>\tbinom nk</math>. In general, if the counting formula involves a division, a similar double counting argument (if it exists) gives the most straightforward combinatorial proof of the identity, but double counting arguments are not limited to situations where the formula is of this form.

Here is a simpler, more informal combinatorial proof of the same identity:
:<math>\binom nk k!(n-k)!=n!</math>
Suppose that n people would like to enter a museum, but the museum only has room for ''k'' people. First choose which ''k'' people from among the ''n'' people will be allowed in. There are <math>\tbinom nk</math> ways to do this by definition. Now order the ''k'' people into a single-file line so that they may pay one at a time. There are ''k''! ways to permute this set of size&nbsp;''k''. Next, order the ''n''&nbsp;−&nbsp;''k'' people who must remain outside into a single-file line so that later they can enter one at a time, as the others leave. There are (''n''&nbsp;−&nbsp;''k'')! ways to do this. But now we have ordered the entire group of n people, something which can be done in ''n''! ways. So both sides count the number of ways to order the ''n'' people. Division yields the well-known formula for <math>\tbinom nk</math>.