A306437 -id:A306437 - cp's OEIS frontend

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

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

Offset: 0

Robert G. Wilson v

nonn

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

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

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

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.
Martin Gardner, Mathematical Games, Scientific American (May 1978), pp. 24-32.
G. Kreweras, Sur les partitions non croisées d'un cycle, (French) Discrete Math. 1 (1972), no. 4, 333-350. MR0309747 (46 #8852).
Wikipedia, Noncrossing partition

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

[Bell(n)-Catalan(n): n in [0..25]]; // Vincenzo Librandi, Aug 31 2016

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

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_,_},_}/;xGus Wiseman, Feb 17 2019 *)

combinat::bell(n)-combinat::catalan(n) $ n = 0..26 // Zerinvary Lajos, May 10 2008

[bell_number(i)-catalan_number(i) for i in range(23)] # Zerinvary Lajos, Mar 14 2009

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

Offset corrected by Matthew Vandermast, Nov 22 2010

New name from Peter Luschny, Apr 28 2011

A306438 Number of non-crossing set partitions whose block sizes are the prime indices of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 2, 4, 1, 6, 1, 5, 5, 1, 1, 10, 1, 10, 6, 6, 1, 10, 3, 7, 5, 15, 1, 30, 1, 1, 7, 8, 7, 30, 1, 9, 8, 20, 1, 42, 1, 21, 21, 10, 1, 15, 4, 21, 9, 28, 1, 35, 8, 35, 10, 11, 1, 105, 1, 12, 28, 1, 9, 56, 1, 36, 11, 56, 1, 70, 1, 13, 28, 45, 9

Offset: 1

Gus Wiseman, Feb 15 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(18) = 10 non-crossing set partitions of type (2, 2, 1) are:
  {{1},{2,3},{4,5}}
  {{1},{2,5},{3,4}}
  {{1,2},{3},{4,5}}
  {{1,2},{3,4},{5}}
  {{1,2},{3,5},{4}}
  {{1,3},{2},{4,5}}
  {{1,4},{2,3},{5}}
  {{1,5},{2},{3,4}}
  {{1,5},{2,3},{4}}
  {{1,5},{2,4},{3}}
Missing from this list are the following crossing set partitions:
  {{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}}

Germain Kreweras, Sur les partitions non croisées d'un cycle, Discrete Math. 1 333-350 (1972).
Wikipedia, Noncrossing partition.

Other orderings are A125181 and A134264.

Cf. A000041, A000108, A000110, A000670, A001263, A001764, A008480, A056239, A112798, A124794, A306437.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[If[n==1,1,With[{y=primeMS[n]},Binomial[Total[y],Length[y]-1]*(Length[y]-1)!/Product[Count[y,i]!,{i,Max@@y}]]],{n,80}]

a(n) = falling(m, k - 1)/Product_i (y)_i! where m is the sum of parts (A056239(n)), k is the number of parts (A001222(n)), y is the integer partition with Heinz number n (row n of A296150), (y)_i is the number of i's in y, and falling(x, y) is the falling factorial x(x - 1)(x - 2) ... (x - y + 1) [Kreweras].

Equivalently, a(n) = falling(A056239(n), A001222(n) - 1)/A112624(n).

A194560 G.f.: Sum_{n>=1} G_n(x)^n where G_n(x) = x + x*G_n(x)^n.

Original entry on oeis.org

1, 2, 2, 4, 2, 10, 2, 20, 14, 49, 2, 217, 2, 438, 310, 1580, 2, 6352, 2, 18062, 7824, 58799, 2, 258971, 2532, 742915, 246794, 2729095, 2, 11154954, 2, 35779660, 8414818, 129644809, 242354, 531132915, 2, 1767263211, 300830821, 6593815523, 2, 26289925026, 2, 91708135773

Offset: 1

Paul D. Hanna, Aug 28 2011

nonn

Number of Dyck n-paths with all ascents of equal length. - David Scambler, Nov 17 2011
From Gus Wiseman, Feb 15 2019: (Start)
Also the number of uniform (all blocks have the same size) non-crossing set partitions of {1,...,n}. For example, the a(3) = 2 through a(6) = 10 uniform non-crossing set partitions are:
  {{123}}      {{1234}}        {{12345}}          {{123456}}
  {{1}{2}{3}}  {{12}{34}}      {{1}{2}{3}{4}{5}}  {{123}{456}}
               {{14}{23}}                         {{126}{345}}
               {{1}{2}{3}{4}}                     {{156}{234}}
                                                  {{12}{34}{56}}
                                                  {{12}{36}{45}}
                                                  {{14}{23}{56}}
                                                  {{16}{23}{45}}
                                                  {{16}{25}{34}}
                                                  {{1}{2}{3}{4}{5}{6}}
(End)

			G.f.: A(x) = x + 2*x^2 + 2*x^3 + 4*x^4 + 2*x^5 + 10*x^6 + 2*x^7 + ...
where
A(x) = G_1(x) + G_2(x)^2 + G_3(x)^3 + G_4(x)^4 + G_5(x)^5 + ...
and G_n(x) = x + x*G_n(x)^n is given by:
G_n(x) = Sum_{k>=0} C(n*k+1,k)/(n*k+1)*x^(n*k+1),
G_n(x)^n = Sum_{k>=1} C(n*k,k)/(n*k-k+1)*x^(n*k);
the first few expansions of G_n(x)^n begin:
G_1(x) = x + x^2 + x^3 + x^4 + x^5 + ...
G_2(x)^2 = x^2 + 2*x^4 + 5*x^6 + 14*x^8 + ... + A000108(n)*x^(2*n) + ...
G_3(x)^3 = x^3 + 3*x^6 + 12*x^9 + 55*x^12 + ... + A001764(n)*x^(3*n) + ...
G_4(x)^4 = x^4 + 4*x^8 + 22*x^12 + 140*x^16 + ... + A002293(n)*x^(4*n) + ...
G_5(x)^5 = x^5 + 5*x^10 + 35*x^15 + 285*x^20 + ... + A002294(n)*x^(5*n) + ...

Paul D. Hanna, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Dyck Path.
Wikipedia, Noncrossing partition.

Row sums of A306437.

Cf. A000108, A001263, A001764, A016098, A038041, A061095, A125181, A134264, A194558, A306418, A306438.

Table[Sum[Binomial[n,d]/(n-d+1),{d,Divisors[n]}],{n,20}] (* Gus Wiseman, Feb 15 2019 *)

{a(n)=if(n<1,0,sumdiv(n,d,binomial(n,d)/(n-d+1)))}

{a(n)=polcoeff(sum(m=1,n,serreverse(x/(1+x^m+x*O(x^n)))^m),n)}

a(n) = Sum_{d|n} C(n,d)/(n-d+1).

G.f.: Sum_{n>=1} Series_Reversion( x/(1+x^n) )^n.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

MuPAD

Sage

Formula

Extensions

A306438 Number of non-crossing set partitions whose block sizes are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A194560 G.f.: Sum_{n>=1} G_n(x)^n where G_n(x) = x + x*G_n(x)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula