Pretty "gnomonic" recurrence

[David W. Wilson]

-------------- next part --------------

I have found an interesting recurrence.

Let f(n,k) count the number of n-bit strings whose longest run of
consecutive 1-bits contains k bits.  Here is a table of f(n,k):

 n\k |    0    1    2    3    4    5    6    7    8    9   10
-------------------------------------------------------------
   0 |    1    0    0    0    0    0    0    0    0    0    0
   1 |    1    1    0    0    0    0    0    0    0    0    0
   2 |    1    2    1    0    0    0    0    0    0    0    0
   3 |    1    4    2    1    0    0    0    0    0    0    0
   4 |    1    7    5    2    1    0    0    0    0    0    0
   5 |    1   12   11    5    2    1    0    0    0    0    0
   6 |    1   20   23   12    5    2    1    0    0    0    0
   7 |    1   33   47   27   12    5    2    1    0    0    0
   8 |    1   54   94   59   28   12    5    2    1    0    0
   9 |    1   88  185  127   63   28   12    5    2    1    0
  10 |    1  143  360  269  139   64   28   12    5    2    1

Some immediate observations are

    f(n,k) = 0, for k > n
    f(n,0) = f(n,n) = 1 
    f(n,1) = Fib(n+2)-1
    SUM(0 <= k <= n, f(n, k)) = 2^n.

Also, the sequence of nonzero elements in the kth column =
{ a(n,k) | n = k, k+1, ... } seems to be approaching A045623
with increasing k.

Let's consider, say, f(10,3). This is the number of 10-bit strings
having maximal 1-bit run of length 3.  To count these, we
partition the 10-bit strings based on their initial bits:

A 10-bit string with maximal 1-bit run of length 3 must fall into
exactly one of the following categories:

A: "0" followed by a 9-bit string with maximal 1-bit run of length 3.
B: "10" followed by an 8-bit string with maximal 1-bit run of length 3.
C: "110" followed by a 7-bit string with maximal 1-bit run of length 3.
D: "1110" followed by a 6-bit string with maximal 1-bit run of length 3.
E: "1110" followed by a 6-bit string with maximal 1-bit run of length 2.
F: "1110" followed by a 6-bit string with maximal 1-bit run of length 1.
G: "1110" followed by a 6-bit string with maximal 1-bit run of length 0.

The number of strings in each of these categories is:

A: f(9,3)
B: f(8,3)
C: f(7,3)
D: f(6,3)
E: f(6,2)
F: f(6,1)
G: f(6,0)

So that

f(10,3) = f(9,3)+f(8,3)+f(7,3)+f(6,3)+f(6,2)+f(6,1)+f(6,0).

If we generalize the argument to k < n, we get

f(n,k) = f(n-1,k) + f(n-2,k) + ...
        + f(n-k,k) + f(n-k-1,k) + f(n-k-1, k-1) + ...
        + f(n-k-1, 1) + f(n-k-1, 0).

When, for a given row (here row n = 5), we mark the summands and the
sums for that row in spreadsheet fashion, we obtain a pretty figure.
The summands form a square gnomon ending in the sum:

 n\k |    0    1    2    3    4    5
------------------------------------
   0 |    e    e    e    e    e    0
   1 |    d    d    d    d    e    0
   2 |    c    c    c    d    e    0
   3 |    b    b    c    d    e    0
   4 |    a    b    c    d    e    0
   5 |    A    B    C    D    E    1

Here the A-cell is the sum of all the a-cells, the B-cell is the sum
of all the b-cells, etc.  f(n, n) = f(5, 5) is set to 1.

The summation pattern clearly shows that the sum of any row is the
sum of all previous rows + 1.  Given that the first row sums to 1,
we easily conclude that the nth row sums to 2^n, as required.

By playing around a bit, you can arrive at the (uglier) finite
recurrence

    f(n, k) = 0 if k < 0 or k > n,
              1 if k = 0 or k = n,
              2f(n-1,k)+f(n-1,k-1)-2f(n-2,k-1)+f(n-k-1,k-1)-f(n-k-2,k)
                 otherwise.