A108304 Number of set partitions of {1, ..., n} that avoid 3-crossings.

1, 1, 2, 5, 15, 52, 202, 859, 3930, 19095, 97566, 520257, 2877834, 16434105, 96505490, 580864901, 3573876308, 22426075431, 143242527870, 929759705415, 6123822269373, 40877248201308, 276229252359846, 1887840181793185, 13037523684646810, 90913254352507057

Offset

0,3

Comments

There is also a sum-formula for a(n). See Bousquet-Mélou and Xin.

Also partitions avoiding a certain pattern (see J. Bloom and S. Elizalde). - N. J. A. Sloane, Jan 02 2013

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Jonathan Bloom and Sergi Elizalde, Pattern avoidance in matchings and partitions, arXiv preprint arXiv:1211.3442 [math.CO], 2012.

Alin Bostan, Jordan Tirrell, Bruce W. Westbury, Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019.

Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On some combinatorial sequences associated to invariant theory, arXiv:2110.13753 [math.CO], 2021.

M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.

Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.

Wei Chen, Enumeration of Set Partitions Refined by Crossing and Nesting Numbers, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014.

W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.

Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.

P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.

Juan B. Gil, Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.

Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.

Zhicong Lin, Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.

T. Mansour and M. Shattuck, Some enumerative results related to ascent sequences, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - N. J. A. Sloane, Dec 22 2012

Marni Mishna and Lily Yen, Set partitions with no k-nesting, arXiv preprint arXiv:1106.5036 [math.CO], 2011.

Formula

Recurrence: (9*n^2+27*n) * a(n) + (-10*n^2-64*n-84) * a(n+1) + (n^2+13*n+42) * a(n+2) = 0.

a(n) = (-18*(n+1)*(4*n^5+73*n^4+530*n^3+1928*n^2+3654*n+2916)*A002893(n)+(8*n^6+17156*n^2+6084*n^3+17496+27612*n+1358*n^4+162*n^5) *A002893(n+1))/ (3*n*(n+2)^2*(n+3)^2*(n+4)^2*(n+5)). - Mark van Hoeij, Nov 05 2011

G.f.: (1+7*x-20*x^2+30*x^3-18*x^4-(3*x+1)^2*(x-1)^2*hypergeom([-2/3, -1/3],[2],27*x*(x-1)^2/(3*x+1)^3))/(6*x^4). - Mark van Hoeij, Nov 05 2011

a(n) ~ 5 * sqrt(3) * 3^(2*n+9) / (32*Pi*n^7), Bousquet-Mélou and Xin, 2006. - Vaclav Kotesovec, Aug 23 2014

Example

There are 203 partitions of 6 elements, but a(6)=202 because the partition (1,4)(2,5)(3,6) has a 3-crossing.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + 52*x^5 + 202*x^6 + 859*x^7 + ...

Mathematica

a[0] = a[1] = 1; a[n_] := a[n] = (2*(5*n^2 + 12*n - 2)*a[n-1] + 9*(-n^2 + n + 2)*a[n-2])/((n+4)*(n+5)); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2015 *)

Prog

(PARI)
v = vector(66, n, n);
for (n=1, #v-2, v[n+2] = ((10*n^2+64*n+84)*v[n+1]-(9*n^2+27*n)*v[n]) / (n^2+13*n+42) );
vector(#v+1, n, if(n==1, 1, v[n-1])) \\ Joerg Arndt, Sep 01 2012

Crossrefs

Sequence in context: A140980 A287254 A220912 * A220913 A287666 A158829

Adjacent sequences: A108301 A108302 A108303 * A108305 A108306 A108307

Keyword

easy,nonn

Author

Mireille Bousquet-Mélou, Jun 29 2005

Extensions

More terms added by Joerg Arndt, Sep 01 2012

Status

approved