OFFSET
1,6
COMMENTS
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.
LINKS
Germain Kreweras, Sur les partitions non croisées d'un cycle, Discrete Math. 1 333-350 (1972).
Wikipedia, Noncrossing partition.
FORMULA
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].
EXAMPLE
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}}
MATHEMATICA
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}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 15 2019
STATUS
approved