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
Examples
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, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..20, flattened
- P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv:1109.3641, 2011
Crossrefs
Programs
-
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 *)