Recurrence relation for string of 1's, 2's and 4's with constraints.

Question

The assignment

(a) Find a recurrence relation for $a_n$, the number of sequences of 1s, 2s and 4s summing to $n$ with the subsequence 421 not allowed.

(b) Repeat part (a) but now with the requirement that you cannot have the subsequence 22.

Answer

$$\tag{a}\quad a_n=a_{n-1}+a_{n-2}+a_{n-4}-a_{n-7}$$ $$\tag{b}\quad a_n=a_{n-2}+2a_{n-5}+a_{n-8}$$ How did my teacher get (b)? Since you cant have 22, shouldn't it be $a_n=a_{n-1}+a_{n-2}$?

Answer 1

First method.

For the first question we get the following system of equations in the corresponding generating functions:

$$Q - 1 = Q (z + z^2) + Q_{4} z + Q_{42} z^2,$$

$$Q_{4} = Q z^4 + Q_4 z^4 + Q_{42} z^4,$$

$$Q_{42} = Q_{4} z^2,$$

$$Q_{421} = Q_{42} z + Q_{421} (z^4 + z^2 + z).$$

Solving this we obtain

$$A(z) = Q + Q_4 + Q_{42} = \frac{1}{1-z-z^2-z^4+z^7}.$$

Extracting coefficients from (here we take $n\ge 7$)

$$[z^n] A(z) (1-z-z^2-z^4+z^7) = [z^n] 1 = 0$$

we find

$$a_n - a_{n-1} - a_{n-2} - a_{n-4} + a_{n-7} = 0$$

or

$$a_n = a_{n-1} + a_{n-2} + a_{n-4} - a_{n-7}$$

as claimed. We need the initial values $a_0$ to $a_6$ in order to use this recurrence. The coefficient extractor yields zero for negative indices so we may start the recurrence with $a_0 = 1$ and compute the next six values by setting the contribution from those indices to zero, getting $1, 1, 2, 3,\ldots$

Second method.

Let $B(z)$ be the generating function of the weighted strings that do contain $421.$ We obtain from first principles

$$A(z) + B(z) = \frac{1}{1-z-z^2-z^4}.$$

We also have by classifying according to the first ocurrence of the pattern $421$ that

$$B(z) = A(z) z^7 \frac{1}{1-z-z^2-z^4}.$$

Solving for $A(z)$ yields the same answer as before. We get the the initial segment as shown:

$$1+z+2\,{z}^{2}+3\,{z}^{3}+6\,{z}^{4}+10\,{z}^{5}+18\,{z}^{6}+30\,{z}^{7} \\+53\,{z}^{8}+91\,{z}^{9}+159\,{z}^{10} \\+274\,{z}^{11}+476\,{z}^{12}+823\,{z}^{13}+\cdots$$

The following Maple code shows how to solve the two systems of equations and presents an enumeration routine whose output matches the generating function $A(z)$ (tested up to $n=13.$)

sys := [Q-1 = Q*(z+z^2) + Q4*z + Q42*z^2,
        Q4 = Q*z^4 + Q4*z^4 + Q42*z^4,
        Q42 = Q4*z^2,
        Q421 = Q42*z + Q421*(z^4+z^2+z)];

sol := op(1, solve(sys, [Q, Q4, Q42, Q421]));

gf := factor(subs(sol, Q + Q4 + Q42));

sys2 := [A + B = 1/(1-z-z^2-z^4), B = A * z^7/(1-z-z^2-z^4)];

sol2 := op(1, solve(sys2, [A, B]));

gf2 := subs(sol2, A);

ENUM :=
proc(X)
option remember;
local len, str, gf, d, pos, wt;

    gf := 1; d := [0]; len := 1;

    while len <= X do
        str := subs([0=1, 1=2, 2=4], d);

        for pos to len - 2 do
            if str[pos] = 4 and
            str[pos+1] = 2 and str[pos+2] = 1 then
                break;
            fi;
        od;

        if len < 3 or pos = len - 1 then
            wt := add(q, q in str);

            if wt <= X then
                gf := gf + z^wt;
            fi;
        fi;

        for pos to len do
            if d[pos] < 2 then
                d := subsop(pos = d[pos] + 1, d);
                break;
            else
                d := subsop(pos = 0, d);
            fi;
        od;

        if pos = len + 1 then
            len := len + 1;
            d := [op(d), 0];
        fi;
    od;

    gf;
end;

The second method was presented at this MSE link.