|
|
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.
|
|
21
|
|
|
1, 4, 12, 47, 170, 750, 3255, 16010, 81199, 448156, 2579626, 15913058, 102488024, 698976419, 4976098729, 37195337408, 289517846210, 2352125666883, 19841666995265, 173888579505200, 1577888354510786, 14820132616197925, 143746389756336173, 1438846957477988926
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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
|
|
LINKS
|
|
|
EXAMPLE
|
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.
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)
|
|
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, []):
|
|
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 *)
|
|
PROG
|
(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
(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
|
|
CROSSREFS
|
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.
The case with empty intersection is A317755.
The case of strict parts is A330783.
Multiset partitions of integer partitions are A001970.
Unlabeled multiset partitions are A007716.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|