# One-to-One correspondence in Counting

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?

• 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. – Tad Jul 18 '15 at 12:44

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.