# Pretty "gnomonic" recurrence

David W. Wilson wilson at cabletron.com
Thu May 13 22:17:53 CEST 1999

```-------------- 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.

```