login
Table read by antidiagonals upward: T(n,k) is the number of binary strings of length k with the property that every substring of length A070939(n) is lexicographically earlier than the binary expansion of n; n, k >= 0.
1

%I #14 Sep 25 2023 08:22:42

%S 1,1,0,1,1,0,1,2,1,0,1,2,2,1,0,1,2,3,2,1,0,1,2,4,5,2,1,0,1,2,4,4,8,2,

%T 1,0,1,2,4,5,4,13,2,1,0,1,2,4,6,7,4,21,2,1,0,1,2,4,7,10,11,4,34,2,1,0,

%U 1,2,4,8,13,16,16,4,55,2,1,0,1,2,4,8,8,24

%N Table read by antidiagonals upward: T(n,k) is the number of binary strings of length k with the property that every substring of length A070939(n) is lexicographically earlier than the binary expansion of n; n, k >= 0.

%F G.f. for row n = 0: 1;

%F G.f. for row n = 1: 1/(1 - x);

%F G.f. for row n = 2: (1 + x)/(1 - x);

%F G.f. for row n = 3: (1 + x)/(1 - x - x^2);

%F G.f. for row n = 4: (1 + x + 2x^2)/(1 - x);

%F G.f. for row n = 5: (1 + x + 2x^2)/(1 - x - x^3);

%F G.f. for row n = 6: (1 + x + x^2)/(1 - x - x^2);

%F G.f. for row n = 7: (1 + x + x^2)/(1 - x - x^2 - x^3);

%F G.f. for row n = 8: (1 + x + 2 x^2 + 4 x^3)/(1 - x);

%F G.f. for row n = 9: (1 + x + 2x^2 + 4x^3)/(1 - x - x^4).

%e Table begins:

%e n\k | 0 1 2 3 4 5 6 7 8 9 10 11

%e -----+----------------------------------------------------

%e 0 | 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e 1 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 2 | 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

%e 3 | 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

%e 4 | 1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, ...

%e 5 | 1, 2, 4, 5, 7, 11, 16, 23, 34, 50, 73, 107, ...

%e 6 | 1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, ...

%e 7 | 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ...

%e 8 | 1, 2, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, ...

%e 9 | 1, 2, 4, 8, 9, 11, 15, 23, 32, 43, 58, 81, ...

%e For (n,k) = (3,4), we see that T(3,4) = 8 because there are 8 binary strings of length k = 4 where all length A070939(3) = 2 substrings are lexicographically earlier than "11" (the binary expansion of n = 3): 0000, 0001, 0010, 0100, 0101, 1000, 1001, and 1010.

%t A365746Row[s_,

%t numberOfTerms_] := (digits = If[s == 0, 1, Ceiling[Log[2, s + 1]]];

%t m = 2^(digits - 1);

%t transferMatrix =

%t If[s == 0, {{0}},

%t Table[If[(Ceiling[i/2] ==

%t j) || ((i <= s - m) && (Ceiling[i/2] == j - m/2)), 1, 0], {i,

%t 1, m}, {j, 1, m}]];

%t sequence =

%t Table[2^k, {k, 0, digits - 1}] ~Join~

%t Table[MatrixPower[transferMatrix, k] // Total // Total, {k, 1,

%t numberOfTerms - digits}];

%t Take[sequence, numberOfTerms])

%Y Cf. A030190, A070939, A209972.

%Y Cf. A000045 (row 3), A164316 (row 5), A128588 (row 6), A000073 (row 7).

%K nonn,tabl,base

%O 0,8

%A _Peter Kagey_, Sep 17 2023