Combination with Exclusion 
*

*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.
 A: 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
A: 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}
