login
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.
21

%I #44 Mar 17 2021 04:18:54

%S 1,4,12,47,170,750,3255,16010,81199,448156,2579626,15913058,102488024,

%T 698976419,4976098729,37195337408,289517846210,2352125666883,

%U 19841666995265,173888579505200,1577888354510786,14820132616197925,143746389756336173,1438846957477988926

%N 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.

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

%C 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

%H Andrew Howroyd, <a href="/A035310/b035310.txt">Table of n, a(n) for n = 1..50</a>

%e 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.

%e From _Gus Wiseman_, Dec 31 2019: (Start)

%e The a(1) = 1 through a(3) = 12 multiset partitions of strongly normal multisets:

%e {{1}} {{1,1}} {{1,1,1}}

%e {{1,2}} {{1,1,2}}

%e {{1},{1}} {{1,2,3}}

%e {{1},{2}} {{1},{1,1}}

%e {{1},{1,2}}

%e {{1},{2,3}}

%e {{2},{1,1}}

%e {{2},{1,3}}

%e {{3},{1,2}}

%e {{1},{1},{1}}

%e {{1},{1},{2}}

%e {{1},{2},{3}}

%e (End)

%p with(numtheory):

%p g:= proc(n, k) option remember;

%p `if`(n>k, 0, 1) +`if`(isprime(n), 0,

%p add(`if`(d>k, 0, g(n/d, d)), d=divisors(n) minus {1, n}))

%p end:

%p b:= proc(n, i, l)

%p `if`(n=0, g(mul(ithprime(t)^l[t], t=1..nops(l))$2),

%p `if`(i<1, 0, add(b(n-i*j, i-1, [l[], i$j]), j=0..n/i)))

%p end:

%p a:= n-> b(n$2, []):

%p seq(a(n), n=1..10); # _Alois P. Heinz_, May 26 2013

%t 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_ *)

%o (Python)

%o from sympy.core.cache import cacheit

%o from sympy import divisors, isprime, prime

%o from operator import mul

%o @cacheit

%o def g(n, k):

%o 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))

%o @cacheit

%o def b(n, i, l):

%o if n==0:

%o p = reduce(mul, (prime(t + 1)**l[t] for t in range(len(l))))

%o return g(p, p)

%o else:

%o return 0 if i<1 else sum([b(n - i*j, i - 1, l + [i]*j) for j in range(n//i + 1)])

%o def a(n):

%o return b(n, n, [])

%o for n in range(1, 11): print(a(n)) # _Indranil Ghosh_, Aug 19 2017, after Maple code

%o (PARI)

%o EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}

%o 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]!)}

%o seq(n)={my(s=0); forpart(p=n, s+=D(p,n)); s} \\ _Andrew Howroyd_, Dec 30 2020

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

%Y 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.

%Y Cf. A035341, A093936, A095705.

%Y Row sums of A317449.

%Y The uniform case is A317584.

%Y The case with empty intersection is A317755.

%Y The strict case is A317775.

%Y The constant case is A047968.

%Y The set-system case is A318402.

%Y The case of strict parts is A330783.

%Y Multiset partitions of integer partitions are A001970.

%Y Unlabeled multiset partitions are A007716.

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

%K nonn,nice

%O 1,2

%A _Alford Arnold_

%E More terms from _Erich Friedman_.

%E 81199 from _Alford Arnold_, Mar 04 2008

%E a(10) from _Alford Arnold_, Mar 31 2008

%E a(10) corrected by _Alford Arnold_, Aug 07 2008

%E a(11)-a(13) from _Alois P. Heinz_, May 26 2013

%E a(14) from _Alois P. Heinz_, Sep 27 2014

%E a(15) from _Alois P. Heinz_, Jan 10 2015

%E Terms a(16) and beyond from _Andrew Howroyd_, Dec 30 2020