|
|
A306438
|
|
Number of non-crossing set partitions whose block sizes are the prime indices of n.
|
|
16
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
Cf. A000041, A000108, A000110, A000670, A001263, A001764, A008480, A056239, A112798, A124794, A306437.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|