cp's OEIS Frontend

A157612 Number of factorizations of n! into distinct factors.

%I A157612 #19 Feb 01 2020 22:34:50
%S A157612 1,1,1,2,5,16,57,253,1060,5285,28762,191263,1052276,8028450,56576192,
%T A157612 424900240,2584010916,24952953943,178322999025,1886474434192,
%U A157612 15307571683248,143131274598786,1423606577935925,17668243239613767,137205093278725072,1399239022852163764,15774656316828338767
%N A157612 Number of factorizations of n! into distinct factors.
%C A157612 The number of factorizations of (n+1)! into k distinct factors can be arranged into the following triangle:
%C A157612 2! 1;
%C A157612 3! 1, 1;
%C A157612 4! 1, 3, 1;
%C A157612 5! 1, 7, 7, 1;
%C A157612 ...
%F A157612 a(n) = A045778(A000142(n)).
%e A157612 3! = 6 = 2*3.
%e A157612 a(3) = 2 because there are 2 factorizations of 3!.
%e A157612 4! = 24 = 2*12 = 3*8 = 4*6 = 2*3*4.
%e A157612 a(4) = 5 because there are 5 factorizations of 4!.
%e A157612 5! = 120 (1)
%e A157612 5! = 2*60 = 3*40 = 4*30 = 5*24 = 6*20 = 8*15 = 10*12 (7)
%e A157612 5! = 2*3*20 = 2*4*15 = 2*5*12 = 2*6*10 = 3*4*10 = 3*5*8 = 4*5*6 (7)
%e A157612 5! = 2*3*4*5 (1)
%e A157612 a(5) = 16 because there are 16 factorizations of 5!.
%p A157612 with(numtheory):
%p A157612 b:= proc(n, k) option remember;
%p A157612       `if`(n>k, 0, 1) +`if`(isprime(n), 0,
%p A157612       add(`if`(d>k, 0, b(n/d, d-1)), d=divisors(n) minus {1, n}))
%p A157612     end:
%p A157612 a:= n-> b(n!$2):
%p A157612 seq(a(n), n=0..12);  # _Alois P. Heinz_, May 26 2013
%t A157612 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}}]];
%t A157612 a[n_] := b[n!, n!];
%t A157612 Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 16}] (* _Jean-François Alcover_, Mar 21 2017, after _Alois P. Heinz_ *)
%o A157612 (PARI) \\ See A318286 for count.
%o A157612 a(n)={if(n<=1, 1, count(factor(n!)[,2]))} \\ _Andrew Howroyd_, Feb 01 2020
%Y A157612 Cf. A076716, A157017, A157229, A318286. See A157836 for continuation of triangle.
%K A157612 nonn
%O A157612 0,4
%A A157612 _Jaume Oliver Lafont_, Mar 03 2009
%E A157612 a(8)-a(12) from _Ray Chandler_, Mar 07 2009
%E A157612 a(13)-a(17) from _Alois P. Heinz_, May 26 2013
%E A157612 a(18)-a(19) from _Alois P. Heinz_, Jan 10 2015
%E A157612 a(20)-a(26) from _Andrew Howroyd_, Feb 01 2020