Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days?

I think the solution is: $\displaystyle\binom{27}{5}$
But I have no idea if I’m right.

Solutions Collecting From Web of "Combination Problem Understanding"

The argument goes: after the first four hospital days ($H$), there must be a non-hospital day ($NH$). So we find a permutation of $$\{H,H,H,H,H,\overbrace{NH,NH,\ldots,NH}^{27}\}$$ of which there are $\binom{27}{5}$ then add $NH$ after the first four $H$s.


For example, the permutation might come out as:

$$(NH,NH,NH,NH,NH,NH,NH,\color{blue}{H},\color{red}{H},NH,NH,NH,NH,NH,NH,NH,NH,NH,NH,\color{green}{H},NH,NH,\color{orange}{H},NH,NH,NH,NH,NH,NH,NH,H,NH)_{27 \text{ days}}$$

which has a clash initially, but no longer after we insert $NH$s after the first four $H$s:

$$(NH,NH,NH,NH,NH,NH,NH,\color{blue}{H},\color{blue}{NH},\color{red}{H},\color{red}{NH},NH,NH,NH,NH,NH,NH,NH,NH,NH,NH,\color{green}{H},\color{green}{NH},NH,NH,\color{orange}{H},\color{orange}{NH},NH,NH,NH,NH,NH,NH,NH,H,NH)_{31 \text{ days}}.$$

You can represent the 26 days when the doctor does not go to the hospital by 26 sticks, which create 27 gaps. If you select 5 of these gaps, this determines the 5 days when the doctor does go in; so this shows that your answer of $\binom{27}{5}$ is correct.


Another way to see this is to let $x_1, \cdots, x_6$ be the number of days in the gaps created by the 5 visits.

Then $x_1+\cdots+x_6=26$ where $x_1\ge0$, $x_6\ge0$, and $x_i\ge1$ for $2\le i\le5$.

If we let $y_i=x_i$ for $i=1,6$ and $y_i=x_i-1$ for $2\le i\le5$,

then $y_1+\cdots+y_6=22$ with $y_i\ge0$ for each $i$, and

the number of integral solutions to this equation is given by $\binom{27}{5}$.

First off I’m not particularly good at combinatorics, however I think I figured this one out.

There are $\binom{31}{5}$ ways for the doctor to arrange his visits. Now we want non of his visits to be consecutive. I will denote a visiting day by $V$ and a non-visiting day by $N$. Now we look at three different cases.

  • He doesn’t visit on January $1^{\large\text{st}}$ nor January $31^{\large\text{st}}$. In this case every $V$ is followed by an $N$. So we have five blocks of $V,N$. The first day is definitely an $N$. This means we’ve $20$ days remaining. Now consider the $V,N$-blocks to be seperate entities. This means we have $\binom{25}{5}$ ways of arranging.

  • He visits on either January $1^{\large\text{st}}$ or January $31 ^{\large\text{st}} $. We use the same trick. Here The first two days have to be $V,N$ so we only have four $V,N$-blocks. So in either case we have $\binom{25}{4}$ ways of arranging. (The arrangments where he visits on January $31^{\large\text{st}}$ are just the opposites.)

  • He visits both on January $1^{\large\text{st}}$ and January $31^{\large\text{st}}$. Now we have three days already accounted for and three $V,N$-blocks left. This means we have $\binom{25}{3}$ ways of arranging.

Now you add the three cases. The second case is counted twice (look closely). This gives us a final answer of $$\binom{25}{5}+2\binom{25}{4}+\binom{25}{3}=\binom{27}{5}.$$