cp's OEIS Frontend

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

%I A108307 #72 Dec 05 2022 08:43:56
%S A108307 1,1,2,5,15,51,191,772,3320,15032,71084,348889,1768483,9220655,
%T A108307 49286863,269346822,1501400222,8519796094,49133373040,287544553912,
%U A108307 1705548000296,10241669069576,62201517142632,381749896129920,2365758616886432,14793705539872672
%N A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).
%C A108307 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 A108307 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 A108307 From _Eric M. Schmidt_, Jul 17 2017: (Start)
%C A108307 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 A108307 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 A108307 (End)
%C A108307 The second of the above-mentioned conjectures is proved in Zhicong Lin's paper. - _Eric M. Schmidt_, Nov 25 2017
%H A108307 Alois P. Heinz, <a href="/A108307/b108307.txt">Table of n, a(n) for n = 0..1000</a>
%H A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 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 A108307 a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - _Vaclav Kotesovec_, Aug 16 2013
%F A108307 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 A108307 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 A108307 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 A108307 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 A108307 Cf. A124303, A073525, A007317.
%Y A108307 Cf. A000110, A000108.
%K A108307 easy,nonn
%O A108307 0,3
%A A108307 _Mireille Bousquet-Mélou_, Jun 29 2005
%E A108307 Edited by _N. J. A. Sloane_ at the suggestion of _Franklin T. Adams-Watters_, Apr 27 2008