A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).
1, 1, 2, 5, 15, 51, 191, 772, 3320, 15032, 71084, 348889, 1768483, 9220655, 49286863, 269346822, 1501400222, 8519796094, 49133373040, 287544553912, 1705548000296, 10241669069576, 62201517142632, 381749896129920, 2365758616886432, 14793705539872672
Offset: 0
Examples
There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
- Alin Bostan, Jordan Tirrell, Bruce W. Westbury and 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.
- W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
- Emma Y. Jin, Jing Qin and Christian M. Reidys, On 2-regular k-noncrossing partitions, arXiv:0710.5014 [math.CO], 2007.
- Juan B. Gil and 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.
- Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
- Sherry H. F. Yan, Ascent sequences and 3-nonnesting set partitions, Eur. J. Comb. 39, 80-94 (2014), remark 3.6.
Programs
-
Maple
a:= proc(n) option remember; if n<=1 then 1 elif n=2 then 2 else (8*(n+1) *(n-1) *a(n-2)+ (7*(n-2)^2 +53*(n-2) +88) *a(n-1))/(n+6)/(n+5) fi end: seq(a(n), n=0..20); # Alois P. Heinz, Sep 05 2008
-
Mathematica
a[n_] := a[n] = If[n <= 1, 1, If[n==2, 2, (8*(n+1)*(n-1)*a[n-2]+(7*(n-2)^2+53*(n-2)+88)*a[n-1])/(n+6)/(n+5)]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)
Formula
D-finite with recurrence: 8*(n+3)*(n+1)*a(n)+(7*n^2+53*n+88)*a(n+1)-(n+8)*(n+7)*a(n+2)=0. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 26 2007
G.f.: -(6*x^4-15*x^3-7*x^2-11*x-1)/(6*x^5)+(224*x^3-60*x^2+45*x+5) * hypergeom([1/3, 2/3],[2],27*x^2/(1-2*x)^3) / (30*x^5*(2*x-1))+(32*x^2+64*x+5) * hypergeom([2/3, 4/3],[3],27*x^2/(1-2*x)^3)/(5*x^3*(2*x-1)^2). - Mark van Hoeij, Oct 24 2011
a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - Vaclav Kotesovec, Aug 16 2013
G.f.: (-6*x^4+15*x^3+7*x^2+11*x+1)/(6*x^5)-(1-8*x)^(4/3)*(1+x)^(2/3)*hypergeom([-2/3, 7/3],[2],-27*x/((1+x)*(-1+8*x)^2))/(6*x^5). - Mark van Hoeij, Jul 26 2021
Extensions
Edited by N. J. A. Sloane at the suggestion of Franklin T. Adams-Watters, Apr 27 2008
Comments