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.

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

Offset: 1

Author

Christian Bean, Oct 09 2015

Keywords

• nonn
• tabf

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 left-to-right 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.

Examples

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

Links

• C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.

Programs

Mathematica

m = 14; Clear[b]; b[, 0] = 1; b[0, ] = 0; b[1, 1] = 1; b[n_, k_] /; (k > 2n-1) = 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/(1-y*(F-1)))), {x, 0, m-1}, {y, 0, m-1}]; eq = And @@ Thread[Flatten[CoefficientList[s, {x, y}]] == 0]; sol = NSolve[eq]; F = F /. sol[[1]] /. y -> x*(y/(1-x)); s = Series[F, {x, 0, m}, {y, 0, m}]; DeleteCases[#, 0]& /@ CoefficientList[s, {x, y}] // Floor // Flatten (* Jean-François Alcover, Dec 31 2015 *)

Formula

a(n,k) = Sum_{j=0..n} I(j,k) * C(n-j-1, k-1) for k > 0 and a(n,0) = 1

where I(n,k) = Sum_{j=0..n-1} C(n, k-j) * C(n, j+1) * C(n-1+j, n-1) / n = A278390(n,k).

G.f: Let F = F(x,y) be the generating function satisfying F = 1 + x*F +x*y*F^2/(1-y*(F-1)); then the generating function for this sequence is F(x,x*y/(1-x)).