Solving recurrence of 3 variables using generating functions

Question

This comes from another question in Wilf's generatingfunctionology book (the part highlighted in light yellow):

If I read the question right, if I do it for $n=3$ (and assuming a substring like $111$ is considered to have 3 consecutive $1$'s and something like $01010$ has 2 non-consecutive $1$'s): \begin{array}{|c|c|} \hline & m & k \\ \hline 000 & 0 & 0 \\ \hline 001 & 1 & 1 \\ \hline 010 & 1 & 1 \\ \hline 011 & 2 & 0 \\ \hline 100 & 1 & 1 \\ \hline 101 & 2 & 2 \\ \hline 110 & 2 & 0 \\ \hline 111 & 3 & 0 \\ \hline \end{array}

So this means $f(3,1,1)=3, f(3,2,0)=2$ and $f(3,3,0) = 1$ for instance.

I have then found the recurrence in the form:

$$f(n,m,k) = f(n-1,m,k) + f(n-2,m-1,k-1) + \sum_{t \geq 0} {f((n-3)-t,(m-3)+1-t,k)}$$

Where:

• The first term is the case when we have $01$ at the start of the string.
• The 2nd term when we have $10$ at start of string.
• The 3rd term is when we have $110$, $1110$, $11110$, etc at the start of the string.

With base cases:

• $f(1,0,0)=f(1,1,1)=1$, and
• $f(n,n,0) =1$ if $n = 0$ or $n > 1$.

And also some other conditions, including $n,m,k\geq 0$, $n\geq m$ and $m\geq k$

This leads me to part (b) of the question where I could multiply the recursion by $x^n y^m$ and sum it, or sum for $n$ or $m$ separately by first defining $A_{m,k} = \sum _{n\geq 0} {f(n,m,k)x^n}$, for example. However, I am confused as to how to deal with the 3rd term.

I believe I may have read the question incorrectly (since there's a mentioning of $k=1,2,...$, but I'm having trouble understanding what the question is asking for otherwise), but am still curious if this recurrence could be solved and would like to ask for hints/help as to how to approach this recurrence, or if I am reading the question right.

Thank you!

Answer 1

For the generating function we get more or less by inspection that it is given by

$$F_k(x, y) = (1+x+x^2+\cdots) \\ \times \sum_{q\ge 0} (y+y^2+\cdots+y^{k-1})^q (x+x^2+\cdots)^q \\ \times (1+y+y^2+\cdots+y^{k-1}) \\ = (1+x+x^2+\cdots) \\ \times \sum_{q\ge 0} x^q y^q (1+y+\cdots+y^{k-2})^q (1+x+\cdots)^q \\ \times (1+y+y^2+\cdots+y^{k-1}) .$$

This is

$$F_k(x, y) = \frac{1}{1-x} \frac{1}{1-xy(1-y^{k-1})/(1-y)/(1-x)} \frac{1-y^{k}}{1-y} \\ = \frac{1-y^{k}}{(1-x)(1-y)-xy(1-y^{k-1})} \\ = \frac{1-y^k}{1-x-y+xy^k}.$$

For the explicit formula we write

$$F_k(x, y) = \frac{1-y^k}{1-y-x(1-y^k)} = \frac{1-y^k}{1-y} \frac{1}{1-x(1-y^k)/(1-y)}.$$

Extracting the coefficient on $x^n$ first followed by $y^m$ we get

$$[x^n] [y^m] F_k(x,y) = [y^m] \frac{1-y^k}{1-y} \frac{(1-y^k)^n}{(1-y)^n} = [y^m] \frac{(1-y^k)^{n+1}}{(1-y)^{n+1}} \\ = [y^m] \frac{1}{(1-y)^{n+1}} \sum_{q=0}^{n+1} {n+1\choose q} (-1)^q y^{kq} \\ = \sum_{q=0}^{n+1} {n+1\choose q} (-1)^q [y^{m-kq}] \frac{1}{(1-y)^{n+1}} \\ = \sum_{q=0}^{\lfloor m/k \rfloor} {n+1\choose q} (-1)^q {m+n-kq\choose n}.$$

We now present a combinatorial recurrence. Observe that $f(n,m,k) - f(n,m,k-1)$ gives the strings where a block of $k-1$ ones appears at least once. Now there are two cases. The first appearance is right at the beginning or at the end and we get $f(n-1,m+1-k,k)$ or $f(n-1,m+1-k,k-1)$ possibilities because the run of $k-1$ ones must be followed / preceded by a zero. The second is that the inital segment before the first appearance of such a block has length $p\ge 0$ to $n+m-k-1$ followed by the $k-1$ ones surrounded by zeros followed by a string of length $n+m-p-(k+1)$ from the set that has at most $k-1$ consecutive ones. This yields with $q$ the number of ones in the prefix

$$f(n,m,k) = f(n,m,k-1) + f(n-1,m+1-k, k) + f(n-1,m+1-k,k-1) \\ + \sum_{p=0}^{n+m-k-1} \sum_{q=0}^m f(p-q, q, k-1) f(n-2+q-p, m+1-q-k,k).$$

There is some Maple code to help explore these recurrences and generating functions which also includes the boundary conditions for the recurrence.

with(combinat);

RL :=
proc(n, m, k)
    option remember;
    local res, iter;

    iter :=
    proc(restx, resty, d)
    local pos, cur, runlen;

        if restx = 0 and resty = 0 then
            cur := -1; pos := 1; runlen := 0;

            while pos <= m+n do
                if d[pos] <> cur then
                    cur := d[pos];
                    runlen := 1;
                else
                    runlen := runlen + 1;

                    if cur = 1 and runlen >= k then
                        break;
                    fi;
                fi;

                pos := pos + 1;
            od;

            if pos = n+m+1 then
                if cur = 0 or (cur = 1 and runlen < k)
                then
                    res := res + 1;
                fi;
            fi;
        fi;

        if restx > 0 then
            iter(restx-1, resty, [op(d), 0]);
        fi;
        if resty > 0 then
            iter(restx, resty-1, [op(d), 1]);
        fi;
    end;

    res := 0;
    iter(n, m, []);
    res;
end;

EX := (n, m, k) ->
coeftayl(coeftayl((1-y^k)/(1-x-y+x*y^k),
                  x=0, n), y=0, m);

EX2 := (n, m, k) ->
add(binomial(n+1,q)*(-1)^q*
    binomial(m+n-k*q, n), q=0..floor(m/k));

f :=
proc(n, m, k)
option remember;

    if n < 0 or m < 0 then return 0 fi;

    if n = 0 and m = 0 then return 1 fi;

    if n = 0 then
        if m <= k-1 then
            return 1
        else
            return 0
        fi;
    fi;

    if m = 0 then return 1 fi;

    if k <= 1 then return 0 fi;

    f(n,m,k-1) + f(n-1,m+1-k,k) + f(n-1, m+1-k, k-1) +
    add(add(f(p-q, q, k-1)*f(n-2+q-p, m+1-q-k, k),
            q=0..m), p=0..n+m-k-1);
end;

There is also a recurrence that is algebraic rather than combinatorial. We start from the observation that

$$\frac{\partial}{\partial x} F_k(x, y) = F_k^2(x, y).$$

Extracting coefficients on $[x^{n-1}] [y^m]$ yields

$$f(n, m, k) = \frac{1}{n} \sum_{p=0}^{n-1} \sum_{q=0}^m f(p, q, k) f(n-1-p, m-q, k).$$

This is implemented below.

g :=
proc(n, m, k)
option remember;

    if n < 0 or m < 0 then return 0 fi;

    if n = 0 and m = 0 then return 1 fi;

    if n = 0 then
        if m <= k-1 then
            return 1
        else
            return 0
        fi;
    fi;

    if m = 0 then return 1 fi;

    if k <= 1 then return 0 fi;

    1/n*add(add(g(p, q, k)*g(n-1-p, m-q, k),
                q=0..m), p=0..n-1);
end;