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!)
A338681 The number of factorizations of an n-element set. (Defined below in Comments.) 0
1, 1, 1, 4, 1, 61, 1, 1681, 5041, 15121, 1, 13638241, 1, 8648641, 1816214401, 181880899201, 1, 45951781075201, 1, 3379365788198401, 1689515283456001, 14079294028801, 1, 4454857103544668620801, 538583682060103680001, 32382376266240001 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

A factorization of a set S is a set B of nontrivial partitions of S such that for each way of choosing one part from each partition in B, there exists a unique element of S in the intersection of the chosen parts.

A factorization of a set can be thought of as a multiplicative analog of a set partition, so this sequence can be thought of as a multiplicative analog of the Bell numbers (A000110).

a(p)=1 for p prime.

For all positive integers k, a(n) = 1 (mod k) for all sufficiently large n.

LINKS

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

FORMULA

Let T_n be the set of all lists a_1b_1...a_kb_k of positive integers, where k >= 0, n = a_1^b_1*...*a_k^b_k, and for all j, a_j >= 2 and a_j > a_{j+1}. (Note that T_n can be thought of as the set of multiplicative partitions of n, so |T_n| = A001055(n).) Then A(n) equals the sum over all a_1b_1...a_kb_k in T_n of n!/Product_{j=1..k} ((a_j!^b_j)*b^j!).

a(n) = n!*R(n,0) where R(1,k) = 1/k! and R(n,k) = Sum_{d|n, d>1} R(n/d, k+1)/d!. - Andrew Howroyd, May 11 2021

EXAMPLE

For n = 4, the four factorizations of {0,1,2,3} are {{{0},{1},{2},{3}}}, {{{0,1},{2,3}},{{0,2},{1,3}}}, {{{0,1},{2,3}},{{0,3},{1,2}}}, and {{{0,2},{1,3}},{{0,3},{1,2}}}.

a(6) = 61 because there is 1 solution {{{0},{1},{2},{3},{4],{5}}} and 60 = 10 * 6 of the form {{{a,b,c}, {d,e,f}}, {{a,d},{b,e},{c,f}}}.

MATHEMATICA

R[n_, k_] := R[n, k] = If[n == 1, 1/k!, Sum[If[d > 1, R[n/d, k+1]/d!, 0], {d, Divisors[n]}]];

a[n_] := n! R[n, 0];

Array[a, 26] (* Jean-Fran├žois Alcover, May 29 2021, after Andrew Howroyd *)

PROG

(PARI)

R(n, k)={if(n==1, 1/k!, sumdiv(n, d, if(d>1, self()(n/d, k+1)/d! )))}

a(n)={n!*R(n, 0)} \\ Andrew Howroyd, May 11 2021

CROSSREFS

Sequence in context: A316159 A113112 A278578 * A069740 A173008 A298828

Adjacent sequences:  A338678 A338679 A338680 * A338682 A338683 A338684

KEYWORD

nonn

AUTHOR

Scott Garrabrant, Apr 30 2021

STATUS

approved

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 July 2 07:08 EDT 2022. Contains 354985 sequences. (Running on oeis4.)