A119551 Number of ordered finite sequences a_1 <= a_2 <= ... <= a_n of length n of positive integers less than or equal to n whose product is n! and whose sum is n * (n + 1) / 2.

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 6, 6, 22, 22, 60, 159, 377, 377, 1007, 1007, 2867, 8147, 22403, 22403, 67808, 176128, 495053, 1362240, 4210266, 4210266, 14223808, 14223808, 42235255, 129279396, 370630653, 1178215490

Offset

0,10

Comments

a(n) is also the number of lattice points in a sequence of polytopes. Given n, define a vector x(k) = #{j : a_j = k} and define a matrix A with n columns as follows: first row all 1 (gives length of a_j); second row 1,2,...,n (sum of a_j); finally one row for each prime p <= n with entries A(row p, column k) = maximum exponent of p that divides k, e.g., A(p=2,k=8)=3 because 2^3|8 (this gives factorization of product of a_j). Then a(n) is the number of nonnegative integer lattice points in the polytope A*x = A*(1,1,1...)T. - Martin Fuller, Feb 12 2023

Links

Martin Fuller, Table of n, a(n) for n = 0..61

Formula

a(p) = a(p-1) for prime p. - Alois P. Heinz, Jul 05 2022

Example

a(9) = 2 because the sequences (1, 2, 3, 4, 5, 6, 7, 8, 9) and (1, 2, 4, 4, 4, 5, 7, 9, 9) both add up to 45 and multiply up to 9!.

Mathematica

a[n_] := a[n] = Module[{b}, b[c_, s_, p_, m_] := b[c, s, p, m] = Module[{x}, If[c <= 0 || m <= 1 || s <= c || s > m*c, Boole[ c == s && p == 1], x = IntegerExponent[p, m]; Sum[b[c - i, s - m*i, p/m^i, m - 1], {i, x*Boole@PrimeQ[m], x} ]]]; b[n, n*(n + 1)/2, n!, n]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 32}] (* Jean-François Alcover, Jul 05 2022, after Martin Fuller *)

Prog

(PARI) a(n) = (b(c, s, p, m) = local(x); if(c<=0||m<=1||s<=c||s>m*c, c==s&&p==1, x=valuation(p, m); sum(i=x*isprime(m), x, b(c-i, s-m*i, p/m^i, m-1)))); b(n, n*(n+1)/2, n!, n) \\ Martin Fuller, Jun 26 2006

Crossrefs

Cf. A000040, A000142, A000217, A076822 without restriction on product, A120690 without restriction on sum.

Sequence in context: A368001 A258702 A320916 * A100634 A242527 A304680

Adjacent sequences: A119548 A119549 A119550 * A119552 A119553 A119554

Keyword

nonn,nice

Author

Jens Voß, May 30 2006

Extensions

a(18) and a(19) from John W. Layman, Jun 08 2006

More terms from Martin Fuller, Jun 26 2006

a(0)=1 prepended by Alois P. Heinz, Jul 05 2022

a(36)-a(61) from Martin Fuller, Feb 12 2023

Status

approved