|
| |
|
|
A108307
|
|
Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).
|
|
5
|
|
|
|
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 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
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
|
|
|
REFERENCES
|
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, Arxiv preprint arXiv:1108.5615, 2011
|
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..350
M. Bousquet-Melou and G. Xin, On partitions avoiding 3-crossings, math.CO/0506551.
Chen, W., Deng, E., Du, R., Stanley, R. P. and Yan, C., Crossings and nestings of matchings and partitions, math.CO/0501230
Emma Y. Jin, Jing Qin and Christian M. Reidys, On 2-regular k-noncrossing partitions, math.CO/07105014.
|
|
|
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^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
|
|
|
EXAMPLE
|
There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting
|
|
|
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
|
|
|
CROSSREFS
|
Cf. A124303, A073525, A007317.
Cf. A000110, A000108.
Sequence in context: A007317 A181768 A153197 * A193296 A117426 A001681
Adjacent sequences: A108304 A108305 A108306 * A108308 A108309 A108310
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
Mireille Bousquet-Mélou, Jun 29 2005
|
|
|
EXTENSIONS
|
Edited by N. J. A. Sloane at the suggestion of Franklin T. Adams-Watters, Apr 27 2008
|
|
|
STATUS
|
approved
|
| |
|
|
