

A016098


Number of crossing set partitions of {1,2,...,n}.


56



0, 0, 0, 0, 1, 10, 71, 448, 2710, 16285, 99179, 619784, 4005585, 26901537, 188224882, 1373263700, 10444784477, 82735225014, 681599167459, 5830974941867, 51717594114952, 474845349889731, 4506624255883683, 44151662795470696, 445957579390657965
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

A partition p of the set N_n = {1,2,...,n}, whose elements are arranged in their natural order, is crossing if there exist four numbers 1 <= i < k < j < l <= n such that i and j are in the same block, k and l are in the same block, but i,j and k,l belong to two different blocks. Noncrossing partitions are also called "planar rhyme schemes".  Peter Luschny, Apr 28 2011
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions:
1. No two colors are chosen the same positive number of times.
2. Among colors chosen at least once, there exists at least one pair of colors (c, d) such that color c is chosen more times than color d, but color d appears more times in the original set than color c.
If the second requirement is removed, the number of acceptable ways to choose equals A000110(n+1). The number of ways that meet the first requirement, but fail to meet the second, equals A000108(n+1). See related comment for A085082.  Matthew Vandermast, Nov 22 2010


REFERENCES

In the May 1978 Scientific American, Martin Gardner indicates that these are the "crossing" cases discussed by Jo Anne Growney (1970).  comment from Alford Arnold.


LINKS

T. D. Noe, Table of n, a(n) for n = 0..100
H. W. Becker, Planar rhyme schemes, in The October meeting in Washington, Bull. Amer. Math. Soc. 58 (1952) p. 39.
G. Kreweras, Sur les partitions non croisees d'un cycle, (French) Discrete Math. 1 (1972), no. 4, 333350. MR0309747 (46 #8852).
Wikipedia, Noncrossing partition


FORMULA

a(n) = A000110(n)  A000108(n).
a(n) = Sum_{k=0..n} S2(n,k)  binomial(2*n,n)/(n+1); S2(n,k) Stirling numbers of the second kind.
E.g.f.: exp(exp(x)1)  (BesselI(0,2*x)  BesselI(1,2*x))*exp(2*x).  Ilya Gutkovskiy, Aug 31 2016


EXAMPLE

1324 is the only crossing partition of {1,2,3,4}.
G.f. = x^4 + 10*x^5 + 71*x^6 + 448*x^7 + 2710*x^8 + 16285*x^9 + ...
From Gus Wiseman, Feb 15 2019: (Start)
The a(5) = 10 crossing set partitions:
{{1,2,4},{3,5}}
{{1,3},{2,4,5}}
{{1,3,4},{2,5}}
{{1,3,5},{2,4}}
{{1,4},{2,3,5}}
{{1},{2,4},{3,5}}
{{1,3},{2,4},{5}}
{{1,3},{2,5},{4}}
{{1,4},{2},{3,5}}
{{1,4},{2,5},{3}}
(End)


MAPLE

A016098 := n > combinat[bell](n)  binomial(2*n, n)/(n+1):
seq(A016098(n), n=0..22); # Peter Luschny, Apr 28 2011


MATHEMATICA

Table[Sum[StirlingS2[n, k], {k, 0, n}]  Binomial[2*n, n]/(n + 1), {n, 0, 25}] (* T. D. Noe, May 29 2012 *)
Table[BellB[n]  CatalanNumber[n], {n, 0, 40}] (* Vincenzo Librandi, Aug 31 2016 *)
sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<tz<x<t<y];
Table[Length[Select[sps[Range[n]], croXQ]], {n, 0, 10}] (* Gus Wiseman, Feb 17 2019 *)


PROG

(MuPAD) combinat::bell(n)combinat::catalan(n) $ n = 0..26 // Zerinvary Lajos, May 10 2008
(Sage) [bell_number(i)catalan_number(i) for i in range(23)] # Zerinvary Lajos, Mar 14 2009
(MAGMA) [Bell(n)Catalan(n): n in [0..25]]; // Vincenzo Librandi, Aug 31 2016


CROSSREFS

Cf. A000108, A000110, A001006, A001263, A080107, A125181, A134264, A194560, A306417, A306437.
Sequence in context: A016218 A026772 A224292 * A129275 A049672 A221548
Adjacent sequences: A016095 A016096 A016097 * A016099 A016100 A016101


KEYWORD

nonn


AUTHOR

Robert G. Wilson v


EXTENSIONS

Offset corrected by Matthew Vandermast, Nov 22 2010
New name from Peter Luschny, Apr 28 2011


STATUS

approved



