A369324 Array read by ascending antidiagonals: A(n,k) is the number of words of length n on an alphabet [k], avoiding 120 and 210, and sortable by a stack of depth 2, where k >= 0.

0, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 8, 9, 4, 1, 0, 1, 16, 25, 16, 5, 1, 0, 1, 32, 65, 56, 25, 6, 1, 0, 1, 64, 161, 176, 105, 36, 7, 1, 0, 1, 128, 385, 512, 385, 176, 49, 8, 1, 0, 1, 256, 897, 1408, 1281, 736, 273, 64, 9, 1, 0, 1, 512, 2049, 3712, 3969, 2752, 1281, 400, 81, 10, 1

Offset

0,9

Links

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

Toufik Mansour, Howard Skogman, and Rebecca Smith, Sorting inversion sequences, arXiv:2401.06662 [math.CO], 2024. See Theorem 3.18 at page 10.

Formula

A(n,k) = A000035(k) + 2^n*Sum_{i=0..floor((k-2)/2)} binomial(n + k - 3 - 2*i, n - 1).

Sum_{k=0..n} A(n-k,k) = A164039(n-1).

Example

The array begins:
  0, 1,  1,   1,   1,    1, ...
  0, 1,  2,   3,   4,    5, ...
  0, 1,  4,   9,  16,   25, ...
  0, 1,  8,  25,  56,  105, ...
  0, 1, 16,  65, 176,  385, ...
  0, 1, 32, 161, 512, 1281, ...
  ...

Mathematica

A[n_, k_]:=(1-(-1)^k)/2+2^n Sum[Binomial[n+k-3-2i, n-1], {i, 0, Floor[(k-2)/2]}]; Table[A[n-k, k], {n, 0, 11}, {k, 0, n}]//Flatten

Crossrefs

Cf. A000004 (k=0), A000012 (k=1), A000079 (k=2), A002064 (k=3), A340257 (k=4).

Cf. A000290 (n=2), A001477 (n=1), A057427 (n=0), A131423 (n=3), A164039.

Cf. A000035, A369325 (main diagonal), A369326.

Sequence in context: A088455 A361390 A369326 * A004248 A034373 A238889

Adjacent sequences: A369321 A369322 A369323 * A369325 A369326 A369327

Keyword

nonn,tabl

Author

Stefano Spezia, Jan 20 2024

Status

approved