

A108307


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


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Also the number of 2regular 3noncrossing partitions. There is a bijection from 2regular 3noncrossing partitions of n to enhanced partition of n1.  Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 30 2007
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(n1),a(n2)) + 1 for n > 2.  Franklin T. AdamsWatters, May 27 2008
From Eric M. Schmidt, Jul 17 2017: (Start)
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]
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]
(End)
The second of the abovementioned conjectures is proved in Zhicong Lin's paper.  Eric M. Schmidt, Nov 25 2017


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini, Simone Rinaldi, Enumerating five families of patternavoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
M. BousquetMélou and G. Xin, On partitions avoiding 3crossings, arXiv:math/0506551 [math.CO], 20052006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to knonnesting 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 2regular knoncrossing partitions, arXiv:0710.5014 [math.CO], 2007.
Juan B. Gil, Jordan O. Tirrell, A simple bijection for classical and enhanced knoncrossing partitions, arXiv:1806.09065 [math.CO], 2018.
Zhicong Lin, Restricted inversion sequences and enhanced 3noncrossing 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.
Yan, Sherry H. F. Ascent sequences and 3nonnesting set partitions, Eur. J. Comb. 39, 8094 (2014), remark 3.6.


FORMULA

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^415*x^37*x^211*x1)/(6*x^5)+(224*x^360*x^2+45*x+5) * hypergeom([1/3, 2/3],[2],27*x^2/(12*x)^3) / (30*x^5*(2*x1))+(32*x^2+64*x+5) * hypergeom([2/3, 4/3],[3],27*x^2/(12*x)^3)/(5*x^3*(2*x1)^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


EXAMPLE

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


MAPLE

a:= proc(n) option remember; if n<=1 then 1 elif n=2 then 2 else (8*(n+1) *(n1) *a(n2)+ (7*(n2)^2 +53*(n2) +88) *a(n1))/(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)*(n1)*a[n2]+(7*(n2)^2+53*(n2)+88)*a[n1])/(n+6)/(n+5)]]; Table[a[n], {n, 0, 20}] (* JeanFrançois Alcover, Mar 30 2015, after Alois P. Heinz *)


CROSSREFS

Cf. A124303, A073525, A007317.
Cf. A000110, A000108.
Sequence in context: A153197 A299968 A279556 * A275605 A193296 A304454
Adjacent sequences: A108304 A108305 A108306 * A108308 A108309 A108310


KEYWORD

easy,nonn


AUTHOR

Mireille BousquetMélou, Jun 29 2005


EXTENSIONS

Edited by N. J. A. Sloane at the suggestion of Franklin T. AdamsWatters, Apr 27 2008


STATUS

approved



