login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A016098 Number of crossing set partitions of {1,2,...,n}. 11
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.

H. W. Becker, Planar rhyme schemes, Bull. Amer. Math. Soc. 58 (1952) 39.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..100

G. Kreweras, Sur les partitions non croisees d'un cycle, (French) Discrete Math. 1 (1972), no. 4, 333-350. 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

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 + ...

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 *)

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

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 by Peter Luschny, Apr 28 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 27 22:57 EDT 2017. Contains 287210 sequences.