[seqfan] "Types/lengths of runs" in binary numbers
q1qq2qqq3qqqq at yahoo.com
Tue Sep 1 22:36:49 CEST 2009
I have already posted several sequences involving the concept of "types of runs" in a binary number.
I just posted this today.
%S A164953 1,1,1,1,2,1,1,3,2,1,1,3,4,3,1,1,4,5,6,3,1
%N A164953 Square array read by antidiagonals: a(m,n) = the number of different combinations of types of runs in the binary representations of positive integers that contain exactly m 0's and n 1's in binary. (The leftmost digit must be 1 in each binary number.)
%C A164953 The top row of the array is where m=0. The leftmost column of the array is where n=1.
%C A164953 Clarification regarding the definition: Each positive integer can be thought of as a finite binary string with 1 as the leftmost digit. The "runs" alternate between those completely of 1's and those completely of 0's. Each run of digit b (0 or 1) is bounded by the digit 1-b or by the edge of the string. By "types" of runs, it is meant that the lengths of the runs of digit b's (b=0 or 1) form a permutation of the lengths of the runs of b's in all binary number with the same types of runs. (See example.)
%e A164953 Consider those binary numbers with exactly four 1's and two 0's. There are 10 such binary numbers that each have a 1 as the leftmost digit. These binary numbers, grouped by those numbers with the same types of runs, are: (111100), (111010, 101110), (111001, 100111), (110110), (110101, 101101, 101011), (110011). There are 6 such groupings, so a(2,4) = 6.
%K A164953 base,more,nonn,tabl
%O A164953 0,5
I know that the "clarification" is somewhat confusing. Perhaps there is some better terminology or wording that someone could suggest for these types of sequences.
(Also, I probably should have had "lengths of runs" in the definition instead of "types of runs", I realize now.
Second, also interesting is the sequence of the sums of the antidiagonals, the number of different combinations of lengths of runs in the binary representations of positive integers that each contain exactly n digits in binary.
The first couple terms are: 1,2,4,7,12,20. Unfortunately, this matches up with a number of pre-existing sequences. So I haven't submitted this.
And as always I ask, have I made any mistakes in calculating the sequence so far? (I figured these terms by hand.)
[ ( [ ([( [ ( ([[o0Oo0Ooo0Oo(0)oO0ooO0oO0o]]) ) ] )]) ] ) ]
More information about the SeqFan