I have a confusion on the one-to-one correspondence in combinatorics.

Take the problem:

In how many ways may five people be seated in a row of twenty chairs given that no two people may sit next to one another?

Take the solution:

Solution for Example: Consider some arrangement of the five people as specified, then take one chair out from between each pair of people. What you’re left with is a unique arrangement of 5 people in 16 chairs without restrictions. Similarly, starting with an unrestricted arrangement of 5 people in 16 chairs, adding a chair between each pair of people gives a unique arrangement of 5 non-adjacent people in 20 chairs. (Convince yourself of these two assertions.) Thus there is a one to one correspondence between the restricted 20-chair arrangements of the problem and unrestricted 16-chair arrangements. The number of unrestricted 16-chair arrangements is the number of ways to choose 5 chairs out of 16, or ${16\choose5}$. □

Okay, I get that we begin with (the following arrangement of 20 chairs/5 people, and restriction): $(*)$ is empty chair, $P_k$ person on chair.

$$* * P_1 * * P_2 ** P_3 ** P_4 ** P_5 ***** \tag1$$

I remove one chair (*).

$$** P_1 * P_2 * P_3 * P_4 * P_5 ***** \tag2$$

What they are saying is:

To go from $(2) \to (1)$ there is only one possible arrangement for $(2)$.

So what the one-to-one idea means is for one configuration $A$ of $(2)$ there is exactly one one configuration $f(A)$ for $(1)$

My question is according to this theorem, there are: $$\binom{16}{5} = 4368 \space \text{arrangements for} \space (1)$$ Does this even make sense! Considering there that the order of chairs or people doesn't matter, how is the number of arrangements this large possible?

  • 1
    $\begingroup$ To convince yourself, I suggest trying smaller examples: $6$ or $7$ chairs and $3$ people. The argument says there should be $\binom43=4$ and $\binom53=10$ arrangements respectively, and you should be able to list them all by hand. $\endgroup$ – Tad Jul 18 '15 at 12:44

I think it's hard to get intuition for large combinations...there are just under 2.6 million ways to deal a 5 card poker hand, the number of possible shuffles of an ordinary deck is comparable to the number of hydrogen atoms in the known universe.

The argument you give to solve the given problem is a very good one. Another way to do it, which may or may not convey any better insight, is to work recursively: Let F(n,k) be the solution to your problem with n seats and k people. Then, either the first seat is occupied or it is not. If it is not occupied then all k people must be in the other n - 1 seats (and there are F(n-1, k) ways to put them there. If it is occupied then the other k - 1 people must be in the n-2 seats starting with seat #3 (and there are F(n-2, k-1) ways to put them there). Thus we get the recursion: $$F(n,k) = F(n-1,k) + F(n-2, k-1)$$ This is very easy to automate (or even do with pencil and paper). And putting the numbers on a grid lets you see how they grow.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.