login
This site is supported by donations to The OEIS Foundation.

 

Logo


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: A209385 A121529 A006370 * A108759 A158824 A039806

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 23 15:54 EDT 2017. Contains 292361 sequences.