|
%I #126 Nov 21 2016 03:54:51
%S 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,
%T 141,2,1,120,1176,2375,1104,86,1,165,2310,7172,5937,1181,30,1,220,
%U 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
%N 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.
%C 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.
%H C. Bean, M. Tannock and H. Ulfarsson, <a href="http://arxiv.org/abs/1512.08155">Pattern avoiding permutations and independent sets in graphs</a>, arXiv:1512.08155 [math.CO], 2015.
%F a(n,k) = Sum_{j=0..n} I(j,k) * C(n-j-1, k-1) for k > 0 and a(n,0) = 1
%F 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).
%F 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)).
%e Triangle starts:
%e 1;
%e 1;
%e 1, 1;
%e 1, 4;
%e 1, 10, 3;
%e 1, 20, 20, 1;
%e 1, 35, 77, 19;
%e 1, 56, 224, 139, 9;
%e ...
%t 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 *)
%K nonn,tabf
%O 1,6
%A _Christian Bean_, Oct 09 2015
|
