login
Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).
6

%I #72 Dec 05 2022 08:43:56

%S 1,1,2,5,15,51,191,772,3320,15032,71084,348889,1768483,9220655,

%T 49286863,269346822,1501400222,8519796094,49133373040,287544553912,

%U 1705548000296,10241669069576,62201517142632,381749896129920,2365758616886432,14793705539872672

%N Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

%C Also the number of 2-regular 3-noncrossing partitions. There is a bijection from 2-regular 3-noncrossing partitions of n to enhanced partition of n-1. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 30 2007

%C It appears that this is the number of sequences of length n, starting with a(1) = 1 and 1 <= a(2) <= 2, with 1 <= a(n) <= max(a(n-1),a(n-2)) + 1 for n > 2. - _Franklin T. Adams-Watters_, May 27 2008

%C From _Eric M. Schmidt_, Jul 17 2017: (Start)

%C Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) <= e(k) and e(i) >= e(k). [Martinez and Savage, 2.16]

%C Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) >= e(k). [Martinez and Savage, 2.16]

%C (End)

%C The second of the above-mentioned conjectures is proved in Zhicong Lin's paper. - _Eric M. Schmidt_, Nov 25 2017

%H Alois P. Heinz, <a href="/A108307/b108307.txt">Table of n, a(n) for n = 0..1000</a>

%H Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, <a href="https://arxiv.org/abs/1808.04114">Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers</a>, arXiv:1808.04114 [math.CO], 2018.

%H Alin Bostan, Jordan Tirrell, Bruce W. Westbury and 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 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 Emma Y. Jin, Jing Qin and Christian M. Reidys, <a href="https://arxiv.org/abs/0710.5014">On 2-regular k-noncrossing partitions</a>, arXiv:0710.5014 [math.CO], 2007.

%H Juan B. Gil and 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 Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.

%H Sherry H. F. Yan, <a href="https://doi.org/10.1016/j.ejc.2013.12.007">Ascent sequences and 3-nonnesting set partitions</a>, Eur. J. Comb. 39, 80-94 (2014), remark 3.6.

%F 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

%F 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

%F a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - _Vaclav Kotesovec_, Aug 16 2013

%F 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

%e There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting.

%p 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

%t 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_ *)

%Y Cf. A124303, A073525, A007317.

%Y Cf. A000110, A000108.

%K easy,nonn

%O 0,3

%A _Mireille Bousquet-Mélou_, Jun 29 2005

%E Edited by _N. J. A. Sloane_ at the suggestion of _Franklin T. Adams-Watters_, Apr 27 2008