The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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. 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(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)). 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 > 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 *) CROSSREFS Sequence in context: A304429 A347115 A006370 * A108759 A158824 A348074 Adjacent sequences: A262367 A262368 A262369 * A262371 A262372 A262373 KEYWORD nonn,tabf AUTHOR Christian Bean, Oct 09 2015 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified April 25 01:35 EDT 2024. Contains 371964 sequences. (Running on oeis4.)