A016098 - OEIS

%I #64 Sep 08 2022 08:44:40

%S 0,0,0,0,1,10,71,448,2710,16285,99179,619784,4005585,26901537,

%T 188224882,1373263700,10444784477,82735225014,681599167459,

%U 5830974941867,51717594114952,474845349889731,4506624255883683,44151662795470696,445957579390657965

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

%C 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

%C 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:

%C 1. No two colors are chosen the same positive number of times.

%C 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.

%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

%C 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

%D JoAnne (Simpson) Growney, Structure Inherent in a Free Groupoid, PhD Dissertation, The University of Oklahoma, 1970.

%H T. D. Noe, <a href="/A016098/b016098.txt">Table of n, a(n) for n = 0..100</a>

%H H. W. Becker, <a href="https://doi.org/10.1090/S0002-9904-1952-09547-1">Planar rhyme schemes</a>, in The October meeting in Washington, Bull. Amer. Math. Soc. 58 (1952) p. 39.

%H Martin Gardner, <a href="https://www.jstor.org/stable/24955724">Mathematical Games</a>, Scientific American (May 1978), pp. 24-32.

%H G. Kreweras, <a href="http://dx.doi.org/10.1016/0012-365X(72)90041-6">Sur les partitions non croisées d'un cycle</a>, (French) Discrete Math. 1 (1972), no. 4, 333-350. MR0309747 (46 #8852).

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Noncrossing_partition">Noncrossing partition</a>

%F a(n) = A000110(n) - A000108(n).

%F a(n) = Sum_{k=0..n} S2(n,k) - binomial(2*n,n)/(n+1); S2(n,k) Stirling numbers of the second kind.

%F E.g.f.: exp(exp(x)-1) - (BesselI(0,2*x) - BesselI(1,2*x))*exp(2*x). - _Ilya Gutkovskiy_, Aug 31 2016

%e 13|24 is the only crossing partition of {1,2,3,4}.

%e G.f. = x^4 + 10*x^5 + 71*x^6 + 448*x^7 + 2710*x^8 + 16285*x^9 + ...

%e From _Gus Wiseman_, Feb 15 2019: (Start)

%e The a(5) = 10 crossing set partitions:

%e   {{1,2,4},{3,5}}

%e   {{1,3},{2,4,5}}

%e   {{1,3,4},{2,5}}

%e   {{1,3,5},{2,4}}

%e   {{1,4},{2,3,5}}

%e   {{1},{2,4},{3,5}}

%e   {{1,3},{2,4},{5}}

%e   {{1,3},{2,5},{4}}

%e   {{1,4},{2},{3,5}}

%e   {{1,4},{2,5},{3}}

%e (End)

%p A016098 := n -> combinat[bell](n) - binomial(2*n,n)/(n+1):

%p seq(A016098(n),n=0..22); # _Peter Luschny_, Apr 28 2011

%t Table[Sum[StirlingS2[n, k], {k, 0, n}] - Binomial[2*n, n]/(n + 1), {n, 0, 25}] (* _T. D. Noe_, May 29 2012 *)

%t Table[BellB[n] - CatalanNumber[n], {n, 0, 40}] (* _Vincenzo Librandi_, Aug 31 2016 *)

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t croXQ[stn_]:=MatchQ[stn,{___,{___,x_,___,y_,___},___,{___,z_,___,t_,___},___}/;x<z<y<t||z<x<t<y];

%t Table[Length[Select[sps[Range[n]],croXQ]],{n,0,10}] (* _Gus Wiseman_, Feb 17 2019 *)

%o (MuPAD) combinat::bell(n)-combinat::catalan(n) $ n = 0..26 // _Zerinvary Lajos_, May 10 2008

%o (Sage) [bell_number(i)-catalan_number(i) for i in range(23)] # _Zerinvary Lajos_, Mar 14 2009

%o (Magma) [Bell(n)-Catalan(n): n in [0..25]]; // _Vincenzo Librandi_, Aug 31 2016

%Y Cf. A000108, A000110, A001006, A001263, A080107, A125181, A134264, A194560, A306417, A306437.

%K nonn

%O 0,6

%A _Robert G. Wilson v_

%E Offset corrected by _Matthew Vandermast_, Nov 22 2010

%E New name from _Peter Luschny_, Apr 28 2011