|
|
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
In the May 1978 Scientific American, Martin Gardner mentions Lady Murasaki's The Tale of Genji in which chapter heads illustrate A000110(5) = 52. These are the "crossing" cases mentioned there as being discussed by JoAnne Growney's 1970 thesis. - Alford Arnold, expanded by Charles R Greathouse IV, Jun 21 2021
|
|
REFERENCES
|
JoAnne (Simpson) Growney, Structure Inherent in a Free Groupoid, PhD Dissertation, The University of Oklahoma, 1970.
|
|
LINKS
|
H. W. Becker, Planar rhyme schemes, in The October meeting in Washington, Bull. Amer. Math. Soc. 58 (1952) p. 39.
|
|
FORMULA
|
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
|
13|24 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 + ...
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):
|
|
MATHEMATICA
|
Table[Sum[StirlingS2[n, k], {k, 0, n}] - Binomial[2*n, n]/(n + 1), {n, 0, 25}] (* T. D. Noe, May 29 2012 *)
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<t||z<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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|