# What is the bijection in this combinatorics example?

Example 3.19. A medical student has to work in a hospital for five days in January. However, he is not allowed to work two consecutive days in the hospital. In how many different ways can he choose the five days he will work in the hospital?

Solution. The difficulty here is to make sure that we do not choose two consecutive days. This can be assured by the following trick. Let $a_1$, $a_2$, $a_3$, $a_4$, $a_5$ be the dates of the five days of January that the student will spend in the hospital, in increasing order. Note that the requirement that there are no two consecutive numbers among the $a_i$, and $1 \le a_i \le 31$ for all $i$ is equivalent to the requirement that $1 \le a_1 \lt a_2 - 1 \lt a_3 - 2 \lt a_4 - 3 \lt a_5 - 4 \le 27$. In other words, there is an obvious bijection between the set of 5-element subsets of $[31]$ containing no two consecutive elements and the set of 5-element subsets of [27]. Instead of choosing the numbers $a_i$, we can choose the numbers $1 \le a_1 \lt a_2 - 1 \lt a_3 - 2 \lt a_4 - 3 \lt a_5 - 4 \le 27$, that is, we can simply choose a five-element subset of $[27]$, and we know that there are $27 \choose 5$ ways to do that.

Note: the bracket notation $[27]$ means $\{1,2,3,...27\}$.

Was reading this example from A Walkthrough Combinatorics (Bona), but I'm not really sure I follow what the "obvious bijection" is suppose to be. Does this mean that if I choose a random five-element subset of $[27]$ say: $\{1,7,27,25,6\}$ then ordered it from least to greatest: $\{1,6,7,25,27\}$ then to map to the actual days (the five-element subset of $[31]$) I would compute:

$\{1+0, 6+1, 7+2, 25+3, 27+4\} = \{1, 7, 9, 28, 31\}$ So the bijection (to map from a five element set of [27]) is to add 0,1,2,3,4 to that ordered set? (Sorry not really sure how to express this in more mathematical notation)

-

The following does not precisely answer your bijection question, but it gives what we believe is a quick way to see what the answer is.

There will be $26$ non-work days. To represent them, put $26$ $\times$ (or perhaps beer bottles) in a row, somewhat separated from each other, like this: $$\times\quad\times \quad\times\quad\times\quad \times\quad\times \quad\times\quad \dots\dots \quad\times\quad\times\quad\times \quad\times$$ These determine $27$ "gaps." We are including the two invisible endgaps.

We need to choose $5$ of these gaps as workdays.

Remark: If one really wants to use the word, there is a bijection from the set of workday choices to the set of choices of $5$ gaps: once we know the workdays, we will know which gaps were chosen and vice-versa.

-
Thanks your use of the X's and gaps really helped me see this. – user17753 Feb 14 '13 at 16:57
As I thought more on it, I think the bijection would be $f(a_1,a_2,a_3,a_4,a_5) = (a_1,a_2+1,a_3+2,a_4+3,a_5+4)$ To go from say gap numbers to day numbers. – user17753 Feb 14 '13 at 18:44
Yes, that is correct, you advance by $1$ each time. And of course the idea generalizes. – André Nicolas Feb 14 '13 at 18:48
I was still pondering this question, and I think I understand better the "invisible" endgaps. Those are the start/end of some other Months (e.g. Dec & Feb) so that's why we include them. Had Jan wrapped around on itself then one end gap would be lost. – user17753 Feb 15 '13 at 15:33
There is a difference of treatment, albeit not a very large one, between ordinary permutations and the "circular" permutations, precisely because of the "wraparound." – André Nicolas Feb 15 '13 at 17:19