login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306438 Number of non-crossing set partitions whose block sizes are the prime indices of n. 16

%I #10 Feb 15 2019 23:43:48

%S 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,

%T 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,

%U 105,1,12,28,1,9,56,1,36,11,56,1,70,1,13,28,45,9

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

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

%H Germain Kreweras, <a href="https://doi.org/10.1016/0012-365X(72)90041-6">Sur les partitions non croisées d'un cycle</a>, Discrete Math. 1 333-350 (1972).

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

%F 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].

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

%e The a(18) = 10 non-crossing set partitions of type (2, 2, 1) are:

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

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

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

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

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

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

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

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

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

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

%e Missing from this list are the following crossing set partitions:

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

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t 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}]

%Y Other orderings are A125181 and A134264.

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

%K nonn

%O 1,6

%A _Gus Wiseman_, Feb 15 2019

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 20:05 EDT 2024. Contains 371254 sequences. (Running on oeis4.)