A365746 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, 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, 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, 1, 2, 4, 8, 13, 16, 16, 4, 55, 2, 1, 0, 1, 2, 4, 8, 8, 24
Offset: 0
Examples
Table begins: n\k | 0 1 2 3 4 5 6 7 8 9 10 11 -----+---------------------------------------------------- 0 | 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... 1 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 2 | 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... 3 | 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ... 4 | 1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, ... 5 | 1, 2, 4, 5, 7, 11, 16, 23, 34, 50, 73, 107, ... 6 | 1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, ... 7 | 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ... 8 | 1, 2, 4, 8, 8, 8, 8, 8, 8, 8, 8, 8, ... 9 | 1, 2, 4, 8, 9, 11, 15, 23, 32, 43, 58, 81, ... 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.
Crossrefs
Programs
-
Mathematica
A365746Row[s_, numberOfTerms_] := (digits = If[s == 0, 1, Ceiling[Log[2, s + 1]]]; m = 2^(digits - 1); transferMatrix = If[s == 0, {{0}}, Table[If[(Ceiling[i/2] == j) || ((i <= s - m) && (Ceiling[i/2] == j - m/2)), 1, 0], {i, 1, m}, {j, 1, m}]]; sequence = Table[2^k, {k, 0, digits - 1}] ~Join~ Table[MatrixPower[transferMatrix, k] // Total // Total, {k, 1, numberOfTerms - digits}]; Take[sequence, numberOfTerms])
Formula
G.f. for row n = 0: 1;
G.f. for row n = 1: 1/(1 - x);
G.f. for row n = 2: (1 + x)/(1 - x);
G.f. for row n = 3: (1 + x)/(1 - x - x^2);
G.f. for row n = 4: (1 + x + 2x^2)/(1 - x);
G.f. for row n = 5: (1 + x + 2x^2)/(1 - x - x^3);
G.f. for row n = 6: (1 + x + x^2)/(1 - x - x^2);
G.f. for row n = 7: (1 + x + x^2)/(1 - x - x^2 - x^3);
G.f. for row n = 8: (1 + x + 2 x^2 + 4 x^3)/(1 - x);
G.f. for row n = 9: (1 + x + 2x^2 + 4x^3)/(1 - x - x^4).