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

Author

Jaume Oliver Lafont, Mar 03 2009

Keywords

• nonn

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;

...

Examples

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

Crossrefs

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

Programs

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 *)

PARI

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

Formula

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

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