Dynamic Programming Recursive Algorithm - Number of heads in a series

Question

So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic Programming to do this and I'm having a hell of a time identifying the recursive algorithm for this.

My first thought was a bottom up approach where I start from a singular toss and then increment a variable whenever I find a sequence that has three heads in a row and then subtract that number from the total number of possible permutations to get the answer but I'm having trouble implementing the logic behind that.

I see that instead of thinking increasingly large sequences, it would be better to think of each individual toss in the sequence. Mostly what I'm having trouble with is how I should be keeping track of all this.

For example, the first toss is a H, that affects the rest of the sequence because I can't have 2 more H's consecutively, but if the first toss is a T, that doesn't affect the rest of the sequence. So, do I wait till the third toss to tell if I increment? Do I discard the first toss if it's a T? I'm having quite a bit of trouble visualizing and comprehending this problem.

• noman pouigt: You have to think something like this: if the first coin throw ends as head and next as also head then the current coin can be head ? HHTHH..... recursion + memorization should do.
• Yuval Filmus: You're using permutations in the everyday sense, but this word has a different and very particular meaning in mathematics which doesn't fit here. This could hamper communication with computer scientists, who use the language of mathematics.

Answer 1

Method 1: DFA. Construct a DFA that accepts the language of valid coin tosses (of any length). Let $A$ be a $Q \times Q$ matrix (where $Q$ is a set of states) such that $A(j,i)$ is the number of symbols that cause the DFA to transition from state $i$ to state $j$. The number of coin tosses that you're after is 1ドル_F A^{32} 1_{\{q_0\}},ドル where $q_0$ is the initial state, $F$ is the set of final states, and 1ドル_S$ is the characteristic vector of $S \subseteq Q$.

This method actually works with more general automaton models. For example, you can have a DFA in which some transitions are "missing": when at state $i,ドル upon reading a symbol $\sigma$ you might just get stuck. More generally, UFAs would work.

Method 2: Recurrence relation. This is a reformulation of the DFA approach without mentioning DFAs. Let $A(n,i)$ be the number of binary words $w$ of length $n$ such that $wH^i \notin L$ but (if $i \neq 0$) $wH^{i-1} \in L,ドル where $L$ consists of all strings with no three consecutive heads. You're after $B(n) = A(n,1) + A(n,2) + A(n,3)$. These sequences are given by the following recurrence:

• $A(0,1) = A(0,2) = 0,ドル $A(0,3) = 1$.
• $A(n+1,1) = A(n,2)$.
• $A(n+1,2) = A(n,3)$.
• $A(n+1,3) = A(n,1) + A(n,2) + A(n,3)$.

I'll let you figure out where these recurrences come from.

We can also come up with a direct recurrence for $B$:

• $B(0) = 1,ドル $B(1) = 2,ドル $B(2) = 4$.
• $B(n+3) = B(n+2) + B(n+1) + B(n)$.

You can prove this recurrence from the preceding ones for $A(n,i),ドル and also directly.

Standard methods show that $B(n) \sim C \alpha^n,ドル where $\alpha \approx 1.839$ and $C \approx 1.137$. In fact, $B(n)$ can be calculated as the integer closest to $C \alpha^n$ for $n$ larger than some constant.