cp's OEIS Frontend

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.

%I A035310 #44 Mar 17 2021 04:18:54
%S A035310 1,4,12,47,170,750,3255,16010,81199,448156,2579626,15913058,102488024,
%T A035310 698976419,4976098729,37195337408,289517846210,2352125666883,
%U A035310 19841666995265,173888579505200,1577888354510786,14820132616197925,143746389756336173,1438846957477988926
%N 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.
%C A035310 Ways of partitioning an n-multiset with multiplicities some partition of n.
%C A035310 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 A035310 Andrew Howroyd, <a href="/A035310/b035310.txt">Table of n, a(n) for n = 1..50</a>
%e A035310 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 A035310 From _Gus Wiseman_, Dec 31 2019: (Start)
%e A035310 The a(1) = 1 through a(3) = 12 multiset partitions of strongly normal multisets:
%e A035310   {{1}}  {{1,1}}    {{1,1,1}}
%e A035310          {{1,2}}    {{1,1,2}}
%e A035310          {{1},{1}}  {{1,2,3}}
%e A035310          {{1},{2}}  {{1},{1,1}}
%e A035310                     {{1},{1,2}}
%e A035310                     {{1},{2,3}}
%e A035310                     {{2},{1,1}}
%e A035310                     {{2},{1,3}}
%e A035310                     {{3},{1,2}}
%e A035310                     {{1},{1},{1}}
%e A035310                     {{1},{1},{2}}
%e A035310                     {{1},{2},{3}}
%e A035310 (End)
%p A035310 with(numtheory):
%p A035310 g:= proc(n, k) option remember;
%p A035310       `if`(n>k, 0, 1) +`if`(isprime(n), 0,
%p A035310       add(`if`(d>k, 0, g(n/d, d)), d=divisors(n) minus {1, n}))
%p A035310     end:
%p A035310 b:= proc(n, i, l)
%p A035310       `if`(n=0, g(mul(ithprime(t)^l[t], t=1..nops(l))$2),
%p A035310       `if`(i<1, 0, add(b(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
%p A035310     end:
%p A035310 a:= n-> b(n$2, []):
%p A035310 seq(a(n), n=1..10);  # _Alois P. Heinz_, May 26 2013
%t A035310 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 A035310 (Python)
%o A035310 from sympy.core.cache import cacheit
%o A035310 from sympy import divisors, isprime, prime
%o A035310 from operator import mul
%o A035310 @cacheit
%o A035310 def g(n, k):
%o A035310     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 A035310 @cacheit
%o A035310 def b(n, i, l):
%o A035310     if n==0:
%o A035310         p = reduce(mul, (prime(t + 1)**l[t] for t in range(len(l))))
%o A035310         return g(p, p)
%o A035310     else:
%o A035310         return 0 if i<1 else sum([b(n - i*j, i - 1, l + [i]*j) for j in range(n//i + 1)])
%o A035310 def a(n):
%o A035310     return b(n, n, [])
%o A035310 for n in range(1, 11): print(a(n)) # _Indranil Ghosh_, Aug 19 2017, after Maple code
%o A035310 (PARI)
%o A035310 EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
%o A035310 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 A035310 seq(n)={my(s=0); forpart(p=n, s+=D(p,n)); s} \\ _Andrew Howroyd_, Dec 30 2020
%Y A035310 Cf. A025487, A000041, A000110, A035098, A080688.
%Y A035310 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 A035310 Cf. A035341, A093936, A095705.
%Y A035310 Row sums of A317449.
%Y A035310 The uniform case is A317584.
%Y A035310 The case with empty intersection is A317755.
%Y A035310 The strict case is A317775.
%Y A035310 The constant case is A047968.
%Y A035310 The set-system case is A318402.
%Y A035310 The case of strict parts is A330783.
%Y A035310 Multiset partitions of integer partitions are A001970.
%Y A035310 Unlabeled multiset partitions are A007716.
%Y A035310 Cf. A001055, A255906, A269134, A316652, A317654, A318284, A330467, A330471, A330475, A330675.
%K A035310 nonn,nice
%O A035310 1,2
%A A035310 _Alford Arnold_
%E A035310 More terms from _Erich Friedman_.
%E A035310 81199 from _Alford Arnold_, Mar 04 2008
%E A035310 a(10) from _Alford Arnold_, Mar 31 2008
%E A035310 a(10) corrected by _Alford Arnold_, Aug 07 2008
%E A035310 a(11)-a(13) from _Alois P. Heinz_, May 26 2013
%E A035310 a(14) from _Alois P. Heinz_, Sep 27 2014
%E A035310 a(15) from _Alois P. Heinz_, Jan 10 2015
%E A035310 Terms a(16) and beyond from _Andrew Howroyd_, Dec 30 2020