6 tests in one month, each must be separated from other tests by 2 free days in between

Question

A university is determining the dates for tests in January. There can be a test on every day in January(all $31 $of them), but each two tests have to have at least $2$ free days in between them. (so if there was a test on Monday, the next one can be on Thursday or later)

How many ways are there to arrange tests in this manner?

I'm guessing inclusion-exclusion would be a way to solve this, but I'm not really sure how to put it because everything I've wanted to do seems to overcount things. Maybe it could be seen as a multiset and look for specific permutations but I'm really not sure.

I would really appreciate any hints whatsoever.

Answer 1

You want to see in how many ways you can arrange $6$ letters T ("test") and $25$ letters F ("free day") in a row so that there are at least two letters F between each two letters T?

To solve this, extract those (five) pairs of letters F between T's, and you get to arrange, freely, $6$ letters T and $15$ letters F in the row. This can be done in $\binom{21}{6}$ ways.

Example:

$$FFTFFFFFTFFFTFFFFFFTFFTFFFFFFTF$$

(exam on Jan 3rd, 9th, 13th, 20th, 23th 30th) maps into the sequence:

$$FFTFFFTFTFFFFTTFFFFTF$$

and vice versa.

Answer 2

You could have used star and bars method too. Let $x_i$ ($2\le i \le 6$) represent the number of free days between two tests while $x_1$ and $x_7$ represent the number of free days before and after the last test. Hence we have $x_i\ge 2$ ($2\le i \le 6$) Hence by star and bars method we have to find non negative integral solutions of $$x_1+x_2+x_3+x_4+x_5+x_6+x_7= 15$$

Hence the answer would simply be $\binom {21}{6}$

Answer 3

Misunderstood Question

Before, I noticed that the title specified $6$ test, I computed all the possible test days.

Use atoms of $\left(x+x^3\right)$ representing a free day, $x$, or a test and two free days, $x^3$.

We also need to note that we can end in two or more free days, $1$, or one free day, $x^2$, or no free days, $x$, represented by $1+x+x^2$

This can be counted by the coefficient of $x^{31}$ in $$ (1+x+x^2)\sum_{k=0}^\infty\left(x+x^3\right)^k =\frac{1+x+x^2}{1-x-x^3} $$ which is $183916$.

---

Another way to count is to add up the number of ways to have $k$ tests. $$ \begin{align} &\sum_{k=0}^{11}\left[\vphantom{\binom{31}{k}}\right.\overbrace{\binom{31-2k}{k}}^{\substack{\text{ending in $2$ or}\\\text{more days off}}}+\overbrace{\binom{32-2k}{k-1}}^{\substack{\text{ending in $0$}\\\text{days off}}}+\overbrace{\binom{31-2k}{k-1}}^{\substack{\text{ending in $1$}\\\text{days off}}}\left.\vphantom{\binom{31}{k}}\right]\\ &=\sum_{k=0}^{11}\binom{33-2k}{k} \end{align} $$ which is also $183916$.

---

Six Test Month

Once I notice the $6$ test days, all the question really needed was the second approach above, using only the $k=6$ term. That gives, as other answers say $$ \binom{21}{6}=54264 $$

---

Another Approach

Similar to the first answer to the misunderstood question above, arrange $6$ "test and two free" days and $31-6\cdot3=13$ "free days". To handle the problem a test cannot happen on the last day or the day before the last day, we add $2$ "free days" to January and ignore them at the end. Thus, we arrange $6$ "test and two free" and $15$ "free days" giving a total number of ways of $$ \binom{15+6}{6}=\binom{21}{6}=54264 $$