A157612 Number of factorizations of n! into distinct factors.

1, 1, 1, 2, 5, 16, 57, 253, 1060, 5285, 28762, 191263, 1052276, 8028450, 56576192, 424900240, 2584010916, 24952953943, 178322999025, 1886474434192, 15307571683248, 143131274598786, 1423606577935925, 17668243239613767, 137205093278725072, 1399239022852163764, 15774656316828338767

Offset

0,4

Comments

The number of factorizations of (n+1)! into k distinct factors can be arranged into the following triangle:

2! 1;

3! 1, 1;

4! 1, 3, 1;

5! 1, 7, 7, 1;

...

Links

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

Formula

a(n) = A045778(A000142(n)).

Example

3! = 6 = 2*3.
a(3) = 2 because there are 2 factorizations of 3!.
4! = 24 = 2*12 = 3*8 = 4*6 = 2*3*4.
a(4) = 5 because there are 5 factorizations of 4!.
5! = 120 (1)
5! = 2*60 = 3*40 = 4*30 = 5*24 = 6*20 = 8*15 = 10*12 (7)
5! = 2*3*20 = 2*4*15 = 2*5*12 = 2*6*10 = 3*4*10 = 3*5*8 = 4*5*6 (7)
5! = 2*3*4*5 (1)
a(5) = 16 because there are 16 factorizations of 5!.

Maple

with(numtheory):
b:= proc(n, k) option remember;
      `if`(n>k, 0, 1) +`if`(isprime(n), 0,
      add(`if`(d>k, 0, b(n/d, d-1)), d=divisors(n) minus {1, n}))
    end:
a:= n-> b(n!$2):
seq(a(n), n=0..12);  # Alois P. Heinz, May 26 2013

Mathematica

b[n_, k_] := b[n, k] = If[n>k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d>k, 0, b[n/d, d-1]], {d, Divisors[n] ~Complement~ {1, n}}]];
a[n_] := b[n!, n!];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)

Prog

(PARI) \\ See A318286 for count.
a(n)={if(n<=1, 1, count(factor(n!)[, 2]))} \\ Andrew Howroyd, Feb 01 2020

Crossrefs

Cf. A076716, A157017, A157229, A318286. See A157836 for continuation of triangle.

Sequence in context: A357580 A192635 A009225 * A348103 A184943 A286946

Adjacent sequences: A157609 A157610 A157611 * A157613 A157614 A157615

Keyword

nonn

Author

Jaume Oliver Lafont, Mar 03 2009

Extensions

a(8)-a(12) from Ray Chandler, Mar 07 2009

a(13)-a(17) from Alois P. Heinz, May 26 2013

a(18)-a(19) from Alois P. Heinz, Jan 10 2015

a(20)-a(26) from Andrew Howroyd, Feb 01 2020

Status

approved