

A273821


Triangle read by rows: T(n,k) is the number of 123avoiding permutations p of [n] (A000108) such that k is maximal with the property that the k largest entries of p, taken in order, avoid 132.


0



1, 0, 2, 0, 1, 4, 0, 3, 3, 8, 0, 9, 10, 7, 16, 0, 28, 32, 25, 15, 32, 0, 90, 104, 84, 56, 31, 64, 0, 297, 345, 283, 195, 119, 63, 128, 0, 1001, 1166, 965, 676, 425, 246, 127, 256, 0, 3432, 4004, 3333, 2359, 1506, 894, 501, 255, 512
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

It appears that each column, other than the first, has asymptotic growth rate of 4.


LINKS

Table of n, a(n) for n=1..55.


FORMULA

G.f.: Sum_{n>=1, 1<=k<=n} T(n,k) x^n y^k = C(x)  1 + ((1  y) (1  x y) (1  (1  x y)C(x)))/((1  2 x y) (1  y + x y^2) ) where C(x) = 1 + x + 2x^2 + 5x^3 + ... is the g.f. for the Catalan numbers A000108 (conjectured).


EXAMPLE

For example, for the 123avoiding permutation p = 42513, the 3 largest entries, 453, avoid 132 but the 4 largest entries, 4253, do not, and so p is counted by T(5,3).
Triangle begins:
1
0 2
0 1 4
0 3 3 8
0 9 10 7 16
0, 28, 32, 25, 15, 32
...


MATHEMATICA

Map[Rest, Rest[Map[CoefficientList[#, y] &, CoefficientList[ Normal[Series[ c  1 + ((1  y) (1  x y) (1  (1  x y) c ))/((1  2 x y) (1  y + x y^2)) /. {c :> (1  Sqrt[1  4 x])/(2 x)}, {x, 0, 10}, {y, 0, 10}]], x]]]]
u[1, 1] = 1; u[2, 2] = 2;
u[n_, 1] /; n > 1 := 0; u[n_, k_] /; n < 1  k < 1  k > n := 0;
u[n_, k_] /; n >= 3 && 2 <= k <= n := u[n, k] = 3 u[n  1, k  1]  2 u[n  2, k  2] + u[n, k + 1]  2 u[n  1, k] + If[k == 2, CatalanNumber[n  2], 0];
Table[u[n, k], {n, 10}, {k, n}]


CROSSREFS

Except for the initial term, column 2 is A000245, column 3 is A071718, and row sums are A000108.
Sequence in context: A261251 A039991 A081265 * A108643 A133838 A182138
Adjacent sequences: A273818 A273819 A273820 * A273822 A273823 A273824


KEYWORD

nonn,tabl


AUTHOR

David Callan, May 31 2016


STATUS

approved



