How to derive recursive formula in combinatoric problems?

Question

I know that certain combinatorics problems (I will provide example at the end of the post) can be solved by figuring out recursive formula. However I seem to fail everytime I try to do that. Could anybody of you show me how is it done generally?

Example: How many sequences of length n, consisting of 1 and 0, which don´t contain string "000" are there? Formula: f(n+1)=f(n)+f(n-1)+f(n-2)

How was it derived?

Answer 1

You can do this by cases. For the rest of this post I will call a string "000" a triplet. Such sequences $S$ of length $(n+1)$ split into 3 categories:

1. The last term of $S$ is a 1. Then the only restriction you have is that there must be no triplet in the first $n$ digits, because you cannot create a triplet with the last digit. So there are as many sequences of this kind as there are sequences of length $n$ with no triplets: $f(n)$.
2. The last terms of $S$ are 10. Then with the same line of reasoning, you have no restriction on the other $(n-1)$ terms, so there are $f(n-1)$ such sequences.
3. The last terms of $S$ are 00. Then you must end with 100, or you would have a triplet. Now the same reasoning as before applies: you can choose the other $(n-2)$ digits in $f(n-2)$ ways.

Putting this all together gives you the result.

This kind of method generally works when you just have a sum: look at how many terms you have, and try to divide in as many cases, then make every case equivalent to one of a previous step in the recursion.

Answer 2

One way to do it is to build a generating function for it by looking at a regular expression.

A regular expression for strings that don't contain $000$ is

$$ \{1,01,001\}^*\{\varepsilon,0,00\}. $$

This says that every string without $000$ can be obtained by taking $1, 01, 001$ and repeating them some number of times (the Kleene star means repeat 0 or more times) followed by adding the empty string ($\varepsilon$) or $0$ or $00$ to the end. For instance $011110010101$ is $01$ then $1$ three times then $001$ then $01$ twice with the empty string on the end.

The generating function for $\{1,01,001\}$ is $x + x^2 + x^3$ (the coefficient of $x^k$ tells you how many strings there are of length $k$; e.g. $4x^3$ means $4$ strings of length $3$). The generating function for $\{\varepsilon,0,00\}$ is $1 + x + x^2$. If $A(x)$ is the generating function for a set $S$ then $\frac{1}{1 - A(x)}$ is the generating function for $S^* = \{\text{elements of $S$ repeated 0 or more times}\}$ (the Kleene star of $S$).

Thus the generating function for $\{1,01,001\}^*\{\varepsilon,0,00\}$ is

$$ \frac{1}{1 - (x + x^2 + x^3)} \cdot (1 + x + x^2) = \frac{1 + x + x^2}{1 - x - x^2 - x^3}. $$

The correspondence between recurrence relations and rational generating functions (see e.g. Stanley EC1, Theorem 4.1.1) says that:

A rational generating function with denominator $1 + a_1x + a_2x^2 + \dots + a_d x^d$ gives a recurrence relation $$f(n + d) + a_1f(n + d - 1) + a_2f(n + d - 2) + \dots + a_d f(n) = 0.$$

Thus we get the recurrence relation

$$ f(n + 3) - f(n + 2) - f(n + 1) - f(n) = 0 $$

Since $d = 3$ and $a_1 = a_2 = a_3 = -1$. This is of course equivalent to what you have.