%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