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,8

Links

Table of n, a(n) for n=0..83.

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).

Example

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.

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])

Crossrefs

Cf. A030190, A070939, A209972.

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

Sequence in context: A239287 A305258 A053616 * A094718 A076191 A362955

Adjacent sequences: A365743 A365744 A365745 * A365747 A365748 A365749

Keyword

nonn,tabl,base

Author

Peter Kagey, Sep 17 2023

Status

approved