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
Examples
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 + ...
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.
Programs
-
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 *) -
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
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
Extensions
More terms added by Joerg Arndt, Sep 01 2012
Comments