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.
More information about the SeqFan
mailing list