

A262370


Triangle read by rows in which T(n,k) is the number of permutations avoiding 132 of length n with an independent set of size k in its coregraph.


0



1, 1, 1, 1, 1, 4, 1, 10, 3, 1, 20, 20, 1, 1, 35, 77, 19, 1, 56, 224, 139, 9, 1, 84, 546, 656, 141, 2, 1, 120, 1176, 2375, 1104, 86, 1, 165, 2310, 7172, 5937, 1181, 30, 1, 220, 4224, 18953, 24959, 9594, 830, 5, 1, 286, 7293, 45188, 87893, 56358, 10613, 380, 1, 364, 12012, 99242, 270452, 264012, 88472, 8240, 105, 1, 455, 19019, 203775, 747877, 1044085, 554395, 100339, 4480, 14
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,6


COMMENTS

If we consider constructing permutations avoiding 132 in terms of independent sets of coregraphs then this is the number of permutations avoiding 132 of length n using an independent set of size k. If we consider the staircase grid formed by the lefttoright minima, every rectangular region of boxes is increasing. Furthermore, for permutations avoiding 132, the presence of points in a box may constrain other boxes to be empty. To capture these constraints we create the coregraph by placing a vertex for every box and an edge between boxes that exclude one another. Therefore every permutation avoiding 132 can be uniquely built by a weighted independent set in the coregraph.


LINKS



FORMULA

a(n,k) = Sum_{j=0..n} I(j,k) * C(nj1, k1) for k > 0 and a(n,0) = 1
where I(n,k) = Sum_{j=0..n1} C(n, kj) * C(n, j+1) * C(n1+j, n1) / n = A278390(n,k).
G.f: Let F = F(x,y) be the generating function satisfying F = 1 + x*F +x*y*F^2/(1y*(F1)); then the generating function for this sequence is F(x,x*y/(1x)).


EXAMPLE

Triangle starts:
1;
1;
1, 1;
1, 4;
1, 10, 3;
1, 20, 20, 1;
1, 35, 77, 19;
1, 56, 224, 139, 9;
...


MATHEMATICA

m = 14; Clear[b]; b[_, 0] = 1; b[0, _] = 0; b[1, 1] = 1; b[n_, k_] /; (k > 2n1) = 0; F = Sum[b[n, k]*x^n*y^k, {n, 0, m}, {k, 0, m}]; s = Series[F  (1+x*F + x*y*(F^2/(1y*(F1)))), {x, 0, m1}, {y, 0, m1}]; eq = And @@ Thread[Flatten[CoefficientList[s, {x, y}]] == 0]; sol = NSolve[eq]; F = F /. sol[[1]] /. y > x*(y/(1x)); s = Series[F, {x, 0, m}, {y, 0, m}]; DeleteCases[#, 0]& /@ CoefficientList[s, {x, y}] // Floor // Flatten (* JeanFrançois Alcover, Dec 31 2015 *)


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



