%I #81 Nov 04 2021 04:09:26
%S 1,1,2,5,15,52,202,859,3930,19095,97566,520257,2877834,16434105,
%T 96505490,580864901,3573876308,22426075431,143242527870,929759705415,
%U 6123822269373,40877248201308,276229252359846,1887840181793185,13037523684646810,90913254352507057
%N Number of set partitions of {1, ..., n} that avoid 3-crossings.
%C There is also a sum-formula for a(n). See Bousquet-Mélou and Xin.
%C Also partitions avoiding a certain pattern (see J. Bloom and S. Elizalde). - _N. J. A. Sloane_, Jan 02 2013
%H Alois P. Heinz, <a href="/A108304/b108304.txt">Table of n, a(n) for n = 0..1000</a>
%H Jonathan Bloom and Sergi Elizalde, <a href="http://arxiv.org/abs/1211.3442">Pattern avoidance in matchings and partitions</a>, arXiv preprint arXiv:1211.3442 [math.CO], 2012.
%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury, Yi Zhang, <a href="https://arxiv.org/abs/1911.10288">On sequences associated to the invariant theory of rank two simple Lie algebras</a>, arXiv:1911.10288 [math.CO], 2019.
%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, <a href="https://arxiv.org/abs/2110.13753">On some combinatorial sequences associated to invariant theory</a>, arXiv:2110.13753 [math.CO], 2021.
%H M. Bousquet-Mélou and G. Xin, <a href="https://arxiv.org/abs/math/0506551">On partitions avoiding 3-crossings</a>, arXiv:math/0506551 [math.CO], 2005-2006.
%H Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, <a href="http://arxiv.org/abs/1108.5615">A generating tree approach to k-nonnesting partitions and permutations</a>, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
%H Wei Chen, <a href="http://summit.sfu.ca/item/14626">Enumeration of Set Partitions Refined by Crossing and Nesting Numbers</a>, MS Thesis, Department of Mathematics. Simon Fraser University, Fall 2014.
%H W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, <a href="https://arxiv.org/abs/math/0501230">Crossings and nestings of matchings and partitions</a>, arXiv:math/0501230 [math.CO], 2005.
%H Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, <a href="https://arxiv.org/abs/2111.01279">Pattern-avoiding ascent sequences of length 3</a>, arXiv:2111.01279 [math.CO], Nov 01 2021.
%H P. Duncan and Einar Steingrimsson, <a href="http://arxiv.org/abs/1109.3641">Pattern avoidance in ascent sequences</a>, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
%H Juan B. Gil, Jordan O. Tirrell, <a href="https://arxiv.org/abs/1806.09065">A simple bijection for classical and enhanced k-noncrossing partitions</a>, arXiv:1806.09065 [math.CO], 2018.
%H Zhicong Lin, <a href="https://arxiv.org/abs/1706.07213">Restricted inversion sequences and enhanced 3-noncrossing partitions</a>, arXiv:1706.07213 [math.CO], 2017.
%H Zhicong Lin, Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.amc.2019.124672">Vincular patterns in inversion sequences</a>, Applied Mathematics and Computation (2020), Vol. 364, 124672.
%H T. Mansour and M. Shattuck, <a href="http://arxiv.org/abs/1207.3755">Some enumerative results related to ascent sequences</a>, arXiv preprint arXiv:1207.3755 [math.CO], 2012. - _N. J. A. Sloane_, Dec 22 2012
%H Marni Mishna and Lily Yen, <a href="http://arxiv.org/abs/1106.5036">Set partitions with no k-nesting</a>, arXiv preprint arXiv:1106.5036 [math.CO], 2011.
%F 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.
%F 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
%F 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
%F a(n) ~ 5 * sqrt(3) * 3^(2*n+9) / (32*Pi*n^7), Bousquet-Mélou and Xin, 2006. - _Vaclav Kotesovec_, Aug 23 2014
%e There are 203 partitions of 6 elements, but a(6)=202 because the partition (1,4)(2,5)(3,6) has a 3-crossing.
%e G.f. = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + 52*x^5 + 202*x^6 + 859*x^7 + ...
%t 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 *)
%o (PARI)
%o v = vector(66,n,n);
%o 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) );
%o vector(#v+1,n, if(n==1,1,v[n-1])) \\ _Joerg Arndt_, Sep 01 2012
%K easy,nonn
%O 0,3
%A _Mireille Bousquet-Mélou_, Jun 29 2005
%E More terms added by _Joerg Arndt_, Sep 01 2012