|
|
A261665
|
|
Triangle read by rows: T(n,k) = number of k-classes of permutations of n letters avoiding the pattern 132 (n>=1, 0 <= k <= n-1).
|
|
1
|
|
|
1, 2, 2, 4, 5, 5, 9, 12, 14, 14, 21, 30, 37, 42, 42, 51, 76, 99, 118, 132, 132, 127, 196, 265, 331, 387, 429, 429, 323, 512, 714, 922, 1124, 1298, 1430, 1430, 835, 1353, 1934, 2568, 3227, 3872, 4433, 4862, 4862, 2188, 3610, 5268, 7156, 9225, 11384, 13507, 15366, 16796, 16796
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
See Baril et al. (2014) for precise definition.
Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108).
|
|
LINKS
|
|
|
FORMULA
|
The proof of Theorem 3.1 in Baril et al. (2014) gives a recurrence for the numbers T(n,k).
|
|
EXAMPLE
|
1
2 2
4 5 5
9 12 14 14
21 30 37 42 42
51 76 99 118 132 132
127 196 265 331 387 429 429
323 512 714 922 1124 1298 1430 1430
835 1353 1934 2568 3227 3872 4433 4862 4862
2188 3610 5268 7156 9225 11384 13507 15366 16796 16796
|
|
MAPLE
|
option remember;
if n = k then
elif k < 0 or n <=k then
0 ;
else
procname(n-1, k+1)+add(procname(n-1-i, k-i)*A000108(i), i=0..k) ;
end if;
|
|
MATHEMATICA
|
T[n_, k_] := T[n, k] = If[n == k, CatalanNumber[n], If[k < 0 || n <= k, 0, T[n-1, k+1] + Sum[T[n-1-i, k-i] CatalanNumber[i], {i, 0, k}]]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|