Combination with Exclusion

Question

• Kate is planning for her $8$ days Study Period.
• Each day she can choose one of the $3$ Subjects: Math, English or Physics.
• She never studies Math and English on consecutive days. (i.e.No ME or EM)
• She also wants to study at least all $3$ subjects on at least one day of her study period.

How many different schedules are possible?.

I tried $3^4-3 \cdot 2^4+3 \cdot 1= 36$ for $4$ day schedule. I draw the picture and there shall be only $10$ possible schedules. Not sure how to do exclusion on no math and English on consecutive days. Please help. Thank you.

Answer 1

The following answer is a two step approach based upon the Goulden-Jackson Cluster Method and PIE, the principle of inclusion-exclusion.

Fist step: $A(z)$ avoiding bad words

We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{E,M,P\}$$ and the set $B=\{EM, ME\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $A(z)$ with the coefficient of $z^n$ being the number of wanted words of length $n$.

According to the paper (p.7) the generating function $A(z)$ is \begin{align*} A(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1} \end{align*} with $d=|\mathcal{V}|=3$, the size of the alphabet and $\mathcal{C}$ being the weight-numerator of bad words with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[EM])+\text{weight}(\mathcal{C}[ME]) \end{align*}

We also keep track of the used letters which are needed when considering PIE and calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[EM])&=-(EM)z^2-Ez\cdot\text{weight}(\mathcal{C}[EM])\\\ \text{weight}(\mathcal{C}[ME])&=-(ME)z^2-Mz\cdot\text{weight}(\mathcal{C}[ME])\\ \end{align*} which results in \begin{align*} \text{weight}(\mathcal{C}[EM])=-EMz^2\frac{1-Ez}{1-EMz^2}\tag{2}\\ \text{weight}(\mathcal{C}[ME])=-EMz^2\frac{1-Mz}{1-EMz^2}\\ \end{align*}

From (1) and (2) in (1) we obtain the generating function

\begin{align*} \color{blue}{A}&\color{blue}{(z;E,M,P)}\\ &=\frac{1}{1-(E+M+P)+EMz^2\frac{1-Ez}{1-EMz^2}+EMz^2\frac{1-MZ}{1-EMz^2}}\\ &\,\,\color{blue}{=\frac{1-EMz^2}{1-(E+M+P)z+EMz^2+EMPz^3}}\tag{3} \end{align*}

Note that \begin{align*} A(z)&=A(z;1,1,1)\\ &=\frac{1-z^2}{1-3z+z^2+z^3}\\ &=1+3z+7z^2+17z^3+41z^4+99z^5\\ &\qquad+239z^6+577z^7+\color{blue}{1\,393}z^8+3\,363z^9+8\,119z^{10}+\cdots \end{align*} where the coefficients of $z^n$ give the number of words of length $n$ which do not contain $EM$ or $ME$. These coefficients (calculated with Wolfram Alpha) are in accordance with the numbers stated in @GregBrowns answer.

Second step: With PIE to $B(z;E,M,P)$

We are looking for words which contain each of the letters $\{E,M,P\}$ and denote the corresponding generating function $B(z;E,M,P)$. We do so by excluding words which do not contain one of these letters using PIE. To get words which do not contain for instance $E$, we calculate \begin{align*} [E^0]A(z;E,M,P)=A(z;E,M,P)|_{E=0} \end{align*} which we denote as $A(z;0,M,P)$.

Using PIE we calculate $B(z;E,M,P)$ with the help of (3) as \begin{align*} B&(z;E,M,P)\\ &=A(z;E,M,P)\\ &\qquad-A(z;0,M,P)-A(z;E,0,P)-A(z;E,M,0)\\ &\qquad+A(z;0,0,P)+A(z;0,M,0)+A(z;E,0,0)\\ &\qquad-A(z;0,0,0)\\ &=\frac{1-EMz^2}{1-(E+M+P)z+EMz^2+EMPz^3}\\ &\qquad-\frac{1}{1-(M+P)z}-\frac{1}{1-(E+P)z}-\frac{1-EMz^2}{1-(E+M)z+EMz^2}\\ &\qquad+\frac{1}{1-Pz} +\frac{1}{1-Mz}+\frac{1}{1-Ez}\\ &\qquad-1\tag{4}\\ \end{align*}

We finally get the wanted generating function $B(z)$ from (4) as \begin{align*} \color{blue}{B(z)}&=B(z;1,1,1,1)\\ &=\frac{1-z^2}{1-3z+z^2+z^3}-\frac{2}{1-2z}-\frac{1-z^2}{1-2z+z^2}+\frac{3}{1-z}-1\\ &\,\,\color{blue}{=\frac{1+z}{1-2z-z^2}-\frac{2}{1-2z}+\frac{1}{1-z}}\\ &=2z^3+10z^4+36z^5+112z^6+322z^7+\color{blue}{882}z^8+2\,340z^9+\cdots\tag{5} \end{align*} where the last line was calculated with some help of Wolfram Alpha.

Result: There are $\color{blue}{882}$ valid words of length $8$ which do not contain $EM$ and $ME$ and so, that each word contains the three letters $E,M,P$.

---

---

Two plausibility checks: $n=4$ and $n=8$.

• We see in (5) there are $10$ valid words of length $4$. These are \begin{align*} &\text{EEPM}\quad\text{EPMM}\quad\text{EPMP}\quad\text{EPPM}\quad\text{MMPE}\\ &\text{MPEE}\quad\text{MPEP}\quad\text{MPPE}\quad\text{PEPM}\quad\text{PMPE} \end{align*}

• We manually calculate the coefficient of $z^8$ from (5). We use the coefficient of operator $[z^n]$ to denote the coefficient of a series. We obtain \begin{align*} \color{blue}{[z^8]}&\color{blue}{B(z)}=[z^8]\left(\frac{1+z}{1-2z-z^2 }-\frac{2}{1-2z}+\frac{1}{1-z}\right)\\ &=\left([z^8]+[z^7]\right)\sum_{j=0}^\infty z^j(2+z)^j-2[z^8]\sum_{j=0}^\infty(2z)^j+[z^8]\sum_{j=0}^\infty z^j\\ &=\sum_{j=0}^8[z^{8-j}](2+z)^j+\sum_{j=0}^7[z^{7-j}](2+z)^j-2(2^8)+1\\ &=\sum_{j=0}^8\binom{j}{8-j}2^{2j-8}+\sum_{j=0}^7\binom{j}{7-j}2^{2j-7}-2^9+1\\ &=\binom{4}{4}2^0+\binom{5}{3}2^2+\binom{6}{2}2^4+\binom{7}{1}2^6+\binom{8}{0}2^8\\ &\qquad+\binom{4}{3}2^1+\binom{5}{2}2^3+\binom{6}{1}2^5+\binom{7}{0}2^7-511\\ &=1+40+240+448+256\\ &\qquad+8+80+192+128-511\\ &\,\,\color{blue}{=882} \end{align*} as expected.

Answer 2

Here's a simple recursive approach. For $d \in \{0, \dots, 8\}$, $m \in \{0,1\}$, $e \in \{0,1\}$, $p \in \{0,1\}$, $s \in \{.,\text{M},\text{E},\text{P}\}$, let $f(d,m,e,p,s)$ be the number of schedules, given $d$ days remaining, $m$ required days of Math remaining, $e$ required days of English remaining, $p$ required days of Physics remaining, and previous subject $s$. Then $$f(d,m,e,p,s) = \begin{cases} 0 & \text{if $d < m + e + p$} \\ 1 & \text{if $d = 0$} \\ [s \not= \text{E}] f(d-1,\max(m-1,0),e,p,\text{M})\\ + [s \not= \text{M}] f(d-1,m,\max(e-1,0),p,\text{E})\\ + f(d-1,m,e,\max(p-1,0),\text{P}) &\text{otherwise} \end{cases} $$ If $d<m+e+p$, there are not enough days left to satisfy the requirement of all subjects. Otherwise, if $d=0$, there is only the empty schedule. Otherwise, the allowable choices of the current subject depend on the previous subject $s$, and whichever subject is chosen reduces the days remaining by $1$ and the requirement for that subject by $1$ unless the requirement has already been met. The brackets $[]$ are Iverson notation that yields $1$ if the expression is true and $0$ if the expression is false. We want to compute $f(8,1,1,1,.)$, which turns out to be $882$.

By the way, $f(4,1,1,1,.)=10 \not= 8$.

---

Because the required number of days for each subject is $1$, you could instead let $g(d,S,s)$ be the number of schedules, given $d$ days remaining, $S\subseteq\{\text{M},\text{E},\text{P}\}$ subset of subjects remaining, and previous subject $s$. Then $$g(d,S,s) = \begin{cases} 0 & \text{if $d < |S|$} \\ 1 & \text{if $d = 0$} \\ [s \not= \text{E}] g(d-1,S\setminus \{\text{M}\},\text{M})\\ + [s \not= \text{M}] g(d-1,S\setminus \{\text{E}\},\text{E})\\ + g(d-1,S\setminus \{\text{P}\},\text{P}) &\text{otherwise} \end{cases} $$ Then $g(8,\{\text{M},\text{E},\text{P}\},.)=882$.

---

Here's a formalization of the first part of @GregBrown's approach, ignoring the requirement to study each subject at least once. Let $m_n$ (and $e_n$ and $p_n$) be the number of schedules of length $n$ that end in $M$ (and $E$ and $P$, respectively) and do not contain $ME$ or $EM$. Then $m_1=e_1=p_1=1$, $m_2=e_2=2$, $p_2=3$, and for $n\ge 3$ we have \begin{align} m_n &= m_{n-1} + p_{n-1} \tag1\\ e_n &= e_{n-1} + p_{n-1} \tag2\\ p_n &= m_{n-1} + e_{n-1} + p_{n-1} \tag3 \end{align} Now let $t_n=m_n+e_n+p_n$ be the number of schedules of length $n$ that do not contain $ME$ or $EM$, and note that summing $(1)$, $(2)$, and $(3)$ implies that $$t_n=2t_{n-1}+p_{n-1}=2t_{n-1}+t_{n-2}.$$ By using this recurrence and the initial conditions $t_1=3$ and $t_2=7$, we find that \begin{align} t_3 &= 2t_2 + t_1 = 2(7)+3=17 \\ t_4 &= 2t_3 + t_2 = 2(17)+7=41 \\ t_5 &= 2t_4 + t_3 = 2(41)+17=99 \\ t_6 &= 2t_5 + t_4 = 2(99)+41=239 \\ t_7 &= 2t_6 + t_5 = 2(239)+99=577 \\ t_8 &= 2t_7 + t_6 = 2(577)+239=1393 \end{align}

Answer 3

In Day1, if P chosen, then all 3 (P, M, E) on Day 2. If she chose M, then she only has 2 (P,M) on day 2 and if she chose E she also only has 2 (P, E) for day 2. Add up all the possibilities she has total 7 cases for day 2.

In day 3 and in all of the scenarios on the day 2, she can do P, so she has 3+2+2=7 options. If she chose E she has 3+2=5 and the same for M. Adds all possibility for Day 3 is 17.

Day 1   Day 2   Day 3   Day 4   Day 5   Day 6   Day 7    Day 8

M 1 2 5 12 29 70 169 408

E 1 2 5 12 29 70 169 408

P 1 3 7 17 41 99 239 577

Total3 7 17 41 99 239 577 1393

Take Away not all 3 subjects in the schedule = 2*2^8(number of days)= 512

Add 1 for undercounting

882