

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

Table of n, a(n) for n=1..76.
C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.


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

Sequence in context: A121529 A304429 A006370 * A108759 A158824 A039806
Adjacent sequences: A262367 A262368 A262369 * A262371 A262372 A262373


KEYWORD

nonn,tabf


AUTHOR

Christian Bean, Oct 09 2015


STATUS

approved



