Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate.

Solution 1:

Fortunately with this problem we can still use a decomposition as with regular expressions which becomes less and less useful as the complexity of the language grows.

First introduce the language of strings of zeros and twos having run length at most $k$ starting with a fixed digit

$$H(z) = z\frac{1-z^k}{1-z} \sum_{q\ge 0} \left(z\frac{1-z^k}{1-z} z\frac{1-z^k}{1-z} \right)^q \frac{1-z^{k+1}}{1-z}.$$

For the main generating function start the string with a chain of zeros or twos or the empty string, follow this by a loop anchored at blocks of ones and finally add a possible string of ones at the end to get

$$G(z) = (1+2H(z)) \sum_{q\ge 0} \left(z\frac{1-z^{k-1}}{1-z} 2 H(z) + z^k (1+v) H(z)\right)^q \frac{1-z^{k+1}}{1-z}.$$

Here we have used $v$ to mark the critical transition $1^k 2.$ To simplify this start with $H(z)$ which yields

$$H(z) = z\frac{1-z^k}{1-z} \frac{1}{1-z^2 (1-z^k)^2/(1-z)^2} \frac{1-z^{k+1}}{1-z} \\ = z \frac{1-z^{k}-z^{k+1}+z^{2k+1}} {1-2z+2z^{k+2}-z^{2k+2}}.$$

Some simplification on $G(z)$ produces

$$G(z) = \frac{(1+2H(z))(1-z^{k+1})}{1-H(z)(2z-2z^k+z^k(1+v)(1-z))/(1-z)} \frac{1}{1-z} \\ = \frac{(1+2H(z))(1-z^{k+1})}{1-z-H(z)(2z-2z^k+z^k(1+v)(1-z))}.$$

The reader is strongly urged to perform additional simplification on this. Continuing we seek the generating function

$$Q(z) = \left. G(z) - G(z, 0) \right|_{v=1}.$$

This yields

$$Q(z) = \frac{(1+2H(z))(1-z^{k+1})}{1-z-H(z)(2z-2z^{k+1})} - \frac{(1+2H(z))(1-z^{k+1})}{1-z-H(z)(2z-z^k-z^{k+1})}.$$

E.g. we obtain for $k=3$ the following result: $$Q_3(z) = {\frac { \left( {z}^{2}+z+1 \right) {z}^{4} \left( z+1 \right) \left( {z}^{2}+1 \right) }{ \left( {z}^{6}+3\,{z}^ {5}+5\,{z}^{4}+5\,{z}^{3}+3\,{z}^{2}+z-1 \right) \left( 2\, {z}^{3}+2\,{z}^{2}+2\,z-1 \right) }}.$$

Starting at $n=1$ this yields the sequence

$$0, 0, 0, 1, 5, 21, 80, 287, 993, 3347, 11067, 36055, \\ 116089, 370222, 1171353,\ldots$$

We will not show $Q_4(z)$ here. The sequence is $$0, 0, 0, 0, 1, 5, 21, 81, 296, 1043, 3585, 12095, \\ 40221, 132225, 430633, 1391623,\ldots$$

Using $Q_5(z)$ we obtain $$0, 0, 0, 0, 0, 1, 5, 21, 81, 297, 1052, 3635, 12333, \\ 41255, 136449, 447147, 1454091,\ldots$$

These sequences have been verified with a total enumeration routine which is included with the Maple code for this problem, which we now present. The total enumeration routine is practical for up to about $n=11.$

RL :=
proc(n, k)
    option remember;
    local ind, d, pos, cur, run, runs, res;

    res := 0;

    for ind from 3^n to 2*3^n-1 do
        d := convert(ind, base, 3);

        cur := -1; pos := 1;
        run := []; runs := [];


        while pos <= n do
            if d[pos] <> cur then
                if nops(run) > 0 then
                    runs := [op(runs), run];
                fi;

                cur := d[pos];
                run := [cur];
            else
                run := [op(run), cur];
            fi;

            pos := pos + 1;
        od;

        runs := [op(runs), run];

        if max(map(r->nops(r), runs)) <= k then
            for pos to nops(runs) -1 do
                run := runs[pos];

                if run[1] = 1 and nops(run) = k
                and runs[pos+1][1] = 2 then
                    break;
                fi;
            od;

            if pos < nops(runs) then
                res := res + 1;
            fi;
        fi;
    od;

    res;
end;

RNG := (minv, maxv) -> add(z^q, q=minv..maxv);

H :=
proc(k)
    RNG(1,k)*
    sum((RNG(1,k)*RNG(1,k))^q, q=0..infinity)
    *RNG(0,k)
end;


H2 := 
proc(k) 
    z*(1-z^k-z^(k+1)+z^(2*k+1))
    /(1-2*z+2*z^(k+2)-z^(2*k+2));
end;

G := 
proc(k)
    (1+2*H(k))
    *sum((RNG(1,k-1)*2*H(k)
          + z^k*(1+v)*H(k))^q,
         q=0..infinity)
    *RNG(0, k);
end;

G2 := 
proc(k)
    (1+2*H2(k))*(1-z^(k+1))
    /(1-z-H2(k)*(2*z-2*z^k+z^k*(1+v)*(1-z)));
end;

Q :=
proc(k)
    subs(v=1, G(k)-subs(v=0, G(k)));
end;

Q2 :=
proc(k)
    (1+2*H2(k))*(1-z^(k+1))
    /(1-z-H2(k)*(2*z-2*z^(k+1)))
    - (1+2*H2(k))*(1-z^(k+1))
    /(1-z-H2(k)*(2*z-z^k-z^(k+1)));
end;

V :=
proc(n, k)
    option remember;

    coeftayl(Q2(k), z=0, n);
end;

Addendum. Observe that the initial segment of all these sequences is in fact the same. We can manually evaluate the case $n=p$ where $k+1\le p\le 2k.$ There is the case that the $1^k 2$ block is situated right at the beginning (position $q=0$). We may freely choose the letters to the right of the block which gives a contribution of $3^{p-k-1}.$ (Note that this stops working when $p\gt 2k$ because forbidden runs may appear to the right of the block.) If the block is at position $q$ where $1\le q\le p-k-1$ we must place a zero or a two just to the left of the block and may freely choose the remaining letters for a contribution of $2\times 3^{q-1} \times 3^{p-(k+1)-q} = 2 \times 3^{p-k-2}.$ Collecting this into a formula we obtain

$$3^{p-k-1} + 2 \sum_{q=1}^{p-k-1} 3^{q-1} 3^{p-(k+1)-q} = 3^{p-k-1} + 2 (p-k-1) 3^{p-k-2}.$$

We see that this depends only on the difference $m = p-k$ i.e.

$$3^{m-1} + 2 (m-1) 3^{m-2} = (2m+1) 3^{m-2}$$

so in fact we have the same initial segment for all $k.$ The sequence here is

$$1, 5, 21, 81, 297, 1053, 3645, 12393, 41553, 137781, \\ 452709, 1476225, 4782969,\ldots$$

which is OEIS A081038.

Solution 2:

There is a general method to compute the generating function of any regular language $L$. In your case, $L$ would be $V^* - V^*(0^{k+1} + 1^{k+1} + 2^{k+1} + 1^k)V^*$, if I understood correctly.

The general method works as follows.

Step 1. Compute the minimal deterministic automaton of $L$. In your case, this automaton has $3k+1$ states, if I am not wrong.

Step 2. Compute an unambiguous regular expression for $L$. Recall that a regular expression $R$ is unambiguous if, for every $u \in L(R)$, there is only one $R$-parse of $u$. In other words, a union is unambiguous if and only if it is disjoint, a product $K = K_0K_1 \cdots K_r$ is unambiguous if every word of $K$ has a unique factorisation as $u = u_0u_1 \cdots u_r$, with $u_0 \in K_0$, ..., $u_r \in K_r$ and $K^*$ is unambiguous if the monoid $K^*$ is free of base $K$.

A standard way to obtain an unambiguous regular expression is to use Kleene's algorithm.

Step 3. The generating function $s(L)$ of $L$ can be now computed from the unambiguous regular expression by using the rules $s(u) = z^{|u|}$, where $|u|$ denotes the length of a word $u$, $s(L_0 + L_1) = s(L_0) + s(L_1)$, $s(L_0L_1) = s(L_0)s(L_1)$ and $s(L^*) = (1-s(L))^*$. For instance, if $L = (a + ba + bba + bbb)^*$ (an unambiguous expression), one gets $s(a) = z$, $s(ba) = z^2$, $s(bba) = s(bbb) = z^3$, and finally $$ s(L) = \frac{1}{1-(z+z^2+2z^3)} $$ Coming back to your case, I suggest to treat the cases $k=0, 1$ and $2$ by hand or with the help of a computer and then guess the general formula for any $k$ before trying a more formal proof.