Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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