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

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

Author

Gus Wiseman, Feb 15 2019

Keywords

• nonn

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.

Examples

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

Links

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

Crossrefs

Other orderings are A125181 and A134264.

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

Programs

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

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

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