A035310 Let f(n) = number of ways to factor n = A001055(n); a(n) = sum of f(k) over all terms k in A025487 that have n factors.

1, 4, 12, 47, 170, 750, 3255, 16010, 81199, 448156, 2579626, 15913058, 102488024, 698976419, 4976098729, 37195337408, 289517846210, 2352125666883, 19841666995265, 173888579505200, 1577888354510786, 14820132616197925, 143746389756336173, 1438846957477988926

Offset: 1

Author

Alford Arnold

Keywords

• nonn
• nice

Comments

Ways of partitioning an n-multiset with multiplicities some partition of n.

Number of multiset partitions of strongly normal multisets of size n, where a finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities. The (weakly) normal version is A255906. - Gus Wiseman, Dec 31 2019

Examples

			a(3) = 12 because there are 3 terms in A025487 with 3 factors, namely 8, 12, 30; and f(8)=3, f(12)=4, f(30)=5 and 3+4+5 = 12.
From _Gus Wiseman_, Dec 31 2019: (Start)
The a(1) = 1 through a(3) = 12 multiset partitions of strongly normal multisets:
  {{1}}  {{1,1}}    {{1,1,1}}
         {{1,2}}    {{1,1,2}}
         {{1},{1}}  {{1,2,3}}
         {{1},{2}}  {{1},{1,1}}
                    {{1},{1,2}}
                    {{1},{2,3}}
                    {{2},{1,1}}
                    {{2},{1,3}}
                    {{3},{1,2}}
                    {{1},{1},{1}}
                    {{1},{1},{2}}
                    {{1},{2},{3}}
(End)
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50

Crossrefs

Cf. A025487, A000041, A000110, A035098, A080688.

Sequence A035341 counts the ordered cases. Tables A093936 and A095705 distribute the values; e.g. 81199 = 30 + 536 + 3036 + 6181 + 10726 + 11913 + 14548 + 13082 + 21147.

Cf. A035341, A093936, A095705.

Row sums of A317449.

The uniform case is A317584.

The case with empty intersection is A317755.

The strict case is A317775.

The constant case is A047968.

The set-system case is A318402.

The case of strict parts is A330783.

Multiset partitions of integer partitions are A001970.

Unlabeled multiset partitions are A007716.

Cf. A001055, A255906, A269134, A316652, A317654, A318284, A330467, A330471, A330475, A330675.

Programs

Maple

with(numtheory):
g:= proc(n, k) option remember;
      `if`(n>k, 0, 1) +`if`(isprime(n), 0,
      add(`if`(d>k, 0, g(n/d, d)), d=divisors(n) minus {1, n}))
    end:
b:= proc(n, i, l)
      `if`(n=0, g(mul(ithprime(t)^l[t], t=1..nops(l))$2),
      `if`(i<1, 0, add(b(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=1..10);  # Alois P. Heinz, May 26 2013

Mathematica

g[n_, k_] := g[n, k] = If[n > k, 0, 1] + If[PrimeQ[n], 0, Sum[If[d > k, 0, g[n/d, d]], {d, Divisors[n] ~Complement~ {1, n}}]]; b[n_, i_, l_] := If[n == 0, g[p = Product[Prime[t]^l[[t]], {t, 1, Length[l]}], p], If[i < 1, 0, Sum[b[n - i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_] := b[n, n, {}]; Table[Print[an = a[n]]; an, {n, 1, 13}] (* Jean-François Alcover, Dec 12 2013, after Alois P. Heinz *)

PARI

EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
D(p, n)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); my(u=EulerT(v)); Vec(1/prod(k=1, n, 1 - u[k]*x^k + O(x*x^n))-1, -n)/prod(i=1, #v, i^v[i]*v[i]!)}
seq(n)={my(s=0); forpart(p=n, s+=D(p,n)); s} \\ Andrew Howroyd, Dec 30 2020

Python

from sympy.core.cache import cacheit
from sympy import divisors, isprime, prime
from operator import mul
@cacheit
def g(n, k):
    return (0 if n > k else 1) + (0 if isprime(n) else sum(g(n//d, d) for d in divisors(n)[1:-1] if d <= k))
@cacheit
def b(n, i, l):
    if n==0:
        p = reduce(mul, (prime(t + 1)**l[t] for t in range(len(l))))
        return g(p, p)
    else:
        return 0 if i<1 else sum([b(n - i*j, i - 1, l + [i]*j) for j in range(n//i + 1)])
def a(n):
    return b(n, n, [])
for n in range(1, 11): print(a(n)) # Indranil Ghosh, Aug 19 2017, after Maple code

Extensions

More terms from Erich Friedman.

81199 from Alford Arnold, Mar 04 2008

a(10) from Alford Arnold, Mar 31 2008

a(10) corrected by Alford Arnold, Aug 07 2008

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

a(14) from Alois P. Heinz, Sep 27 2014

a(15) from Alois P. Heinz, Jan 10 2015

Terms a(16) and beyond from Andrew Howroyd, Dec 30 2020