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: 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 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 k. Next, order the n − 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 − 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 . The benefit of a combinatorial proof gives an example of a combinatorial enumeration problem (counting the number of sequences of k subsets S1, S2, ... Sk, that can be formed from a set of n items such that the subsets have an empty common intersection) with two different proofs for its solution. The first proof, which is not combinatorial, uses mathematical induction and generating functions to find that the number of sequences of this type is (2k −1)n. The second proof is based on the observation that there are 2k −1 proper subsets of the set {1, 2, ..., k}, and (2k −1)n functions from the set {1, 2, ..., n} to the family of proper subsets of {1, 2, ..., k}. The sequences to be counted can be placed in one-to-one correspondence with these functions, where the function formed from a given sequence of subsets maps each element i to the set {j | i ∈ Sj}. Stanley writes, “Not only is the above combinatorial proof much shorter than our previous proof, but also it makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simple combinatorial proof.” Due both to their frequent greater elegance than non-combinatorial