A294220 Number A(n,k) of ascent sequences of length n where no letter multiplicity is larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 10, 1, 0, 1, 1, 2, 5, 14, 27, 1, 0, 1, 1, 2, 5, 15, 47, 83, 1, 0, 1, 1, 2, 5, 15, 52, 180, 277, 1, 0, 1, 1, 2, 5, 15, 53, 210, 773, 1015, 1, 0, 1, 1, 2, 5, 15, 53, 216, 964, 3701, 4007, 1, 0

Offset

0,13

Links

Alois P. Heinz, Antidiagonals n = 0..20, flattened

P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv:1109.3641, 2011

Formula

A(n,k) = Sum_{j=0..k} A294219(n,j).

A(n,k) = A(n,n) = A022493(n) for k >= n.

Example

A(4,2) = 10: 0123, 0011, 0012, 0101, 0102, 0110, 0112, 0120, 0121, 0122.
Square array A(n,k) begins:
  1, 1,    1,    1,    1,    1,    1,    1,    1, ...
  0, 1,    1,    1,    1,    1,    1,    1,    1, ...
  0, 1,    2,    2,    2,    2,    2,    2,    2, ...
  0, 1,    4,    5,    5,    5,    5,    5,    5, ...
  0, 1,   10,   14,   15,   15,   15,   15,   15, ...
  0, 1,   27,   47,   52,   53,   53,   53,   53, ...
  0, 1,   83,  180,  210,  216,  217,  217,  217, ...
  0, 1,  277,  773,  964, 1006, 1013, 1014, 1014, ...
  0, 1, 1015, 3701, 4960, 5270, 5326, 5334, 5335, ...

Maple

b:= proc(n, i, t, p, k) option remember; `if`(n=0, 1,
      add(`if`(coeff(p, x, j)=k, 0, b(n-1, j, t+
          `if`(j>i, 1, 0), p+x^j, k)), j=1..t+1))
    end:
A:= (n, k)-> b(n, 0$3, min(n, k)):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[n_, i_, t_, p_, k_] := b[n, i, t, p, k] = If[n == 0, 1, Sum[ If[ Coefficient[p, x, j] == k, 0, b[n-1, j, t + If[j>i, 1, 0], p + x^j, k]], {j, 1, t+1}]];
A[n_, k_] := b[n, 0, 0, 0, Min[n, k]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 11}] // Flatten (* Jean-François Alcover, Aug 05 2018, translated from Maple *)

Crossrefs

Columns k=0-3 give: A000007, A000012, A202058, A317784.

Main diagonal gives A022493.

Cf. A294219.

Sequence in context: A080934 A320955 A288942 * A214015 A137560 A201093

Adjacent sequences: A294217 A294218 A294219 * A294221 A294222 A294223

Keyword

nonn,tabl

Author

Alois P. Heinz, Oct 25 2017

Status

approved