login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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
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

Table of n, a(n) for n=1..77.

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

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

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

Other orderings are A125181 and A134264.

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

Sequence in context: A065836 A078712 A287218 * A221978 A035254 A143934

Adjacent sequences:  A306435 A306436 A306437 * A306439 A306440 A306441

KEYWORD

nonn

AUTHOR

Gus Wiseman, Feb 15 2019

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 00:03 EDT 2021. Contains 342877 sequences. (Running on oeis4.)