A276024 -id:A276024 - cp's OEIS frontend

A006128 Total number of parts in all partitions of n. Also, sum of largest parts of all partitions of n.

0, 1, 3, 6, 12, 20, 35, 54, 86, 128, 192, 275, 399, 556, 780, 1068, 1463, 1965, 2644, 3498, 4630, 6052, 7899, 10206, 13174, 16851, 21522, 27294, 34545, 43453, 54563, 68135, 84927, 105366, 130462, 160876, 198014, 242812, 297201, 362587, 441546, 536104, 649791, 785437, 947812, 1140945, 1371173, 1644136, 1968379, 2351597, 2805218, 3339869, 3970648, 4712040, 5584141, 6606438, 7805507, 9207637

Offset: 0

N. J. A. Sloane, Colin Mallows

a(n) = degree of Kac determinant at level n as polynomial in the conformal weight (called h). (Cf. C. Itzykson and J.-M. Drouffe, Statistical Field Theory, Vol. 2, p. 533, eq.(98); reference p. 643, Cambridge University Press, (1989).) - Wolfdieter Lang
Also the number of one-element transitions from the integer partitions of n to the partitions of n-1 for labeled parts with the assumption that from any part z > 1 one can take an element of amount 1 in one way only. That means z is composed of z unlabeled parts of amount 1, i.e. z = 1 + 1 + ... + 1. E.g., for n=3 to n=2 we have a(3) = 6 and [111] --> [11], [111] --> [11], [111] --> [11], [12] --> [11], [12] --> [2], [3] --> [2]. For the case of z composed by labeled elements, z = 1_1 + 1_2 + ... + 1_z, see A066186. - Thomas Wieder, May 20 2004
Number of times a derivative of any order (not 0 of course) appears when expanding the n-th derivative of 1/f(x). For instance (1/f(x))'' = (2 f'(x)^2-f(x) f''(x)) / f(x)^3 which makes a(2) = 3 (by counting k times the k-th power of a derivative). - Thomas Baruchel, Nov 07 2005
Starting with offset 1, = the partition triangle A008284 * [1, 2, 3, ...]. - Gary W. Adamson, Feb 13 2008
Starting with offset 1 equals A000041: (1, 1, 2, 3, 5, 7, 11, ...) convolved with A000005: (1, 2, 2, 3, 2, 4, ...). - Gary W. Adamson, Jun 16 2009
Apart from initial 0 row sums of triangle A066633, also the Möbius transform is A085410. - Gary W. Adamson, Mar 21 2011
More generally, the total number of parts >= k in all partitions of n equals the sum of k-th largest parts of all partitions of n. In this case k = 1. Apart from initial 0 the first column of A181187. - Omar E. Pol, Feb 14 2012
Row sums of triangle A221530. - Omar E. Pol, Jan 21 2013
From Omar E. Pol, Feb 04 2021: (Start)
a(n) is also the total number of divisors of all positive integers in a sequence with n blocks where the m-th block consists of A000041(n-m) copies of m, with 1 <= m <= n. The mentioned divisors are also all parts of all partitions of n.
Apart from initial zero this is also as follows:
Convolution of A000005 and A000041.
Convolution of A006218 and A002865.
Convolution of A341062 and A000070.
Row sums of triangles A221531, A245095, A339258, A340525, A340529. (End)
Number of ways to choose a part index of an integer partition of n, i.e., partitions of n with a selected position. Selecting a part value instead of index gives A000070. - Gus Wiseman, Apr 19 2021

			For n = 4 the partitions of 4 are [4], [2, 2], [3, 1], [2, 1, 1], [1, 1, 1, 1]. The total number of parts is 12. On the other hand, the sum of the largest parts of all partitions is 4 + 2 + 3 + 2 + 1 = 12, equaling the total number of parts, so a(4) = 12. - _Omar E. Pol_, Oct 12 2018

S. M. Luthra, On the average number of summands in partitions of n, Proc. Nat. Inst. Sci. India Part. A, 23 (1957), p. 483-498.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Paul Erdős and Joseph Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J. 8, (1941), 335-345.
John A. Ewell, Additive evaluation of the divisor function, Fibonacci Quart. 45 (2007), no. 1, 22-25. See Table 1.
Guo-Niu Han, An explicit expansion formula for the powers of the Euler Product in terms of partition hook lengths, arXiv:0804.1849 [math.CO], 2008; see p.27
I. Kessler and M. Livingston, The expected number of parts in a partition of n, Monatsh. Math. 81 (1976), no. 3, 203-212.
I. Kessler and M. Livingston, The expected number of parts in a partition of n, Monatsh. Math. 81 (1976), no. 3, 203-212.
Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
Vaclav Kotesovec, Graph - The asymptotic ratio
Arnold Knopfmacher and Neville Robbins, Identities for the total number of parts in partitions of integers, Util. Math. 67 (2005), 9-18.
S. M. Luthra, On the average number of summands in partitions of n, Proc. Nat. Inst. Sci. India Part. A, 23 (1957), p. 483-498.
C. L. Mallows & N. J. A. Sloane, Emails, May 1991
C. L. Mallows & N. J. A. Sloane, Emails, Jun. 1991
Ljuben Mutafchiev, On the Largest Part Size and Its Multiplicity of a Random Integer Partition, arXiv:1712.03233 [math.PR], 2017.
Omar E. Pol, Illustration of initial terms
J. Sandor, D. S. Mitrinovic, B. Crstici, Handbook of Number Theory I, Volume 1, Springer, 2005, p. 495.
Eric Weisstein's World of Mathematics, q-Polygamma Function, q-Pochhammer Symbol.
H. S. Wilf, A unified setting for selection algorithms (II), Annals Discrete Math., 2 (1978), 135-148.

Cf. A093694, A008284, A000005, A066633, A085410, A046746, A209423, A285220, A336902, A336903.
Main diagonal of A210485.
Column k=1 of A256193.
The version for normal multisets is A001787.
The unordered version is A001792.
The strict case is A015723.
The version for factorizations is A066637.
A000041 counts partitions.
A000070 counts partitions with a selected part.
A336875 counts compositions with a selected part.
A339564 counts factorizations with a selected factor.
Cf. A066186, A083710, A130689, A264401, A276024, A343341.

List([0..60],n->Length(Flat(Partitions(n)))); # Muniru A Asiru, Oct 12 2018

a006128 = length . concat . ps 1 where
   ps _ 0 = [[]]
   ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]
-- Reinhard Zumkeller, Jul 13 2013

g:= add(n*x^n*mul(1/(1-x^k), k=1..n), n=1..61):
a:= n-> coeff(series(g,x,62),x,n):
seq(a(n), n=0..61);
# second Maple program:
a:= n-> add(combinat[numbpart](n-j)*numtheory[tau](j), j=1..n):
seq(a(n), n=0..61);  # Alois P. Heinz, Aug 23 2019

a[n_] := Sum[DivisorSigma[0, m] PartitionsP[n - m], {m, 1, n}]; Table[ a[n], {n, 0, 41}]
CoefficientList[ Series[ Sum[n*x^n*Product[1/(1 - x^k), {k, n}], {n, 100}], {x, 0, 100}], x]
a[n_] := Plus @@ Max /@ IntegerPartitions@ n; Array[a, 45] (* Robert G. Wilson v, Apr 12 2011 *)
Join[{0}, ((Log[1 - x] + QPolyGamma[1, x])/(Log[x] QPochhammer[x]) + O[x]^60)[[3]]] (* Vladimir Reshetnikov, Nov 17 2016 *)
Length /@ Table[IntegerPartitions[n] // Flatten, {n, 50}] (* Shouvik Datta, Sep 12 2021 *)

f(n)= {local(v,i,k,s,t);v=vector(n,k,0);v[n]=2;t=0;while(v[1]1,i--;s+=i*(v[i]=(n-s)\i));t+=sum(k=1,n,v[k]));t } /* Thomas Baruchel, Nov 07 2005 */

a(n) = sum(m=1, n, numdiv(m)*numbpart(n-m)) \\ Michel Marcus, Jul 13 2013

from sympy import divisor_count, npartitions
def a(n): return sum([divisor_count(m)*npartitions(n - m) for m in range(1, n + 1)]) # Indranil Ghosh, Apr 25 2017

G.f.: Sum_{n>=1} n*x^n / Product_{k=1..n} (1-x^k).
G.f.: Sum_{k>=1} x^k/(1-x^k) / Product_{m>=1} (1-x^m).
a(n) = Sum_{k=1..n} k*A008284(n, k).
a(n) = Sum_{m=1..n} of the number of divisors of m * number of partitions of n-m.
Note that the formula for the above comment is a(n) = Sum_{m=1..n} d(m)*p(n-m) = Sum_{m=1..n} A000005(m)*A000041(n-m), if n >= 1. - Omar E. Pol, Jan 21 2013
Erdős and Lehner show that if u(n) denotes the average largest part in a partition of n, then u(n) ~ constant*sqrt(n)*log n.
a(n) = A066897(n) + A066898(n), n>0. - Reinhard Zumkeller, Mar 09 2012
a(n) = A066186(n) - A196087(n), n >= 1. - Omar E. Pol, Apr 22 2012
a(n) = A194452(n) + A024786(n+1). - Omar E. Pol, May 19 2012
a(n) = A000203(n) + A220477(n). - Omar E. Pol, Jan 17 2013
a(n) = Sum_{m=1..p(n)} A194446(m) = Sum_{m=1..p(n)} A141285(m), where p(n) = A000041(n), n >= 1. - Omar E. Pol, May 12 2013
a(n) = A198381(n) + A026905(n), n >= 1. - Omar E. Pol, Aug 10 2013
a(n) = O(sqrt(n)*log(n)*p(n)), where p(n) is the partition function A000041(n). - Peter Bala, Dec 23 2013
a(n) = Sum_{m=1..n} A006218(m)*A002865(n-m), n >= 1. - Omar E. Pol, Jul 14 2014
From Vaclav Kotesovec, Jun 23 2015: (Start)
Asymptotics (Luthra, 1957): a(n) = p(n) * (C*N^(1/2) + C^2/2) * (log(C*N^(1/2)) + gamma) + (1+C^2)/4 + O(N^(-1/2)*log(N)), where N = n - 1/24, C = sqrt(6)/Pi, gamma is the Euler-Mascheroni constant A001620 and p(n) is the partition function A000041(n).
The formula a(n) = p(n) * (sqrt(3*n/(2*Pi)) * (log(n) + 2*gamma - log(Pi/6)) + O(log(n)^3)) in the abstract of the article by Kessler and Livingston (cited also in the book by Sandor, p. 495) is incorrect!
Right is: a(n) = p(n) * (sqrt(3*n/2)/Pi * (log(n) + 2*gamma - log(Pi^2/6)) + O(log(n)^3))
or a(n) ~ exp(Pi*sqrt(2*n/3)) * (log(6*n/Pi^2) + 2*gamma) / (4*Pi*sqrt(2*n)).
(End)
G.f.: (log(1-x) + psi_x(1))/(log(x) * (x)inf), where psi_q(z) is the q-digamma function, and (q)_inf is the q-Pochhammer symbol (the Euler function). - _Vladimir Reshetnikov, Nov 17 2016
a(n) = Sum_{m=1..n} A341062(m)*A000070(n-m), n >= 1. - Omar E. Pol, Feb 05 2021 2014

A299702 Heinz numbers of knapsack partitions.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 76, 77, 78

Offset: 1

Gus Wiseman, Feb 17 2018

nonn

An integer partition is knapsack if every distinct submultiset has a different sum. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A056239, A108917, A112798, A275972, A276024, A284640, A296150, A299701, A299729.

filter:= proc(n) local F,t,S,i,r;
  F:= map(t -> [numtheory:-pi(t[1]),t[2]], ifactors(n)[2]);
  S:= {0}: r:= 1;
  for t in F do
   S:= map(s -> seq(s + i*t[1],i=0..t[2]),S);
   r:= r*(t[2]+1);
   if nops(S) <> r then return false fi
  od;
  true
end proc:
select(filter, [$1..100]); # Robert Israel, Oct 30 2024

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],UnsameQ@@Plus@@@Union[Rest@Subsets[primeMS[#]]]&]

A301987 Heinz numbers of integer partitions whose product is equal to their sum.

Original entry on oeis.org

2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 30, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 84, 89, 97, 101, 103, 107, 108, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 200, 211, 223, 227, 229, 233, 239, 241, 251

Offset: 1

Gus Wiseman, Mar 30 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			Sequence of reversed integer partitions begins: (1), (2), (3), (4), (2 2), (5), (6), (7), (8), (9), (10), (1 2 3), (11), (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), (1 1 2 4), (24), (25), (26), (27), (28), (1 1 2 2 2), (29), (30).

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A001055, A002865, A003963, A056239, A276024, A284640, A296150, A299701, A301957, A301988.

q:= n-> (l-> mul(i, i=l)=add(i, i=l))(map(i->
    numtheory[pi](i[1])$i[2], ifactors(n)[2])):
select(q, [$1..300])[];  # Alois P. Heinz, Mar 27 2019

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[300],Total[primeMS[#]]===Times@@primeMS[#]&]

A126796 Number of complete partitions of n.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 31, 39, 55, 71, 100, 125, 173, 218, 291, 366, 483, 600, 784, 971, 1244, 1538, 1957, 2395, 3023, 3693, 4605, 5604, 6942, 8397, 10347, 12471, 15235, 18309, 22267, 26619, 32219, 38414, 46216, 54941, 65838, 77958, 93076, 109908

Offset: 0

Brian Hopkins, Feb 20 2007

A partition of n is complete if every number 1 to n can be represented as a sum of parts of the partition. This generalizes perfect partitions, where the representation for each number must be unique.
A partition is complete iff each part is no more than 1 more than the sum of all smaller parts. (This includes the smallest part, which thus must be 1.) - Franklin T. Adams-Watters, Mar 22 2007
For n > 0: a(n) = sum of n-th row in A261036 and also a(floor(n/2)) = A261036(n,floor((n+1)/2)). - Reinhard Zumkeller, Aug 08 2015
a(n+1) is the number of partitions of n such that each part is no more than 2 more than the sum of all smaller parts (generalizing Adams-Watters's criterion). Bijection: each partition counted by a(n+1) must contain a 1, removing that gives a desired partition of n. - Brian Hopkins, May 16 2017
A partition (x_1, ..., x_k) is complete if and only if 1, x_1, ..., x_k is a "regular sequence" (see A003513 for definition). As a result, the number of complete partitions with n parts is given by A003513(n+1). - Nathaniel Johnston, Jun 29 2023

			There are a(5) = 4 complete partitions of 5:
  [1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [1, 1, 3].
G.f.: 1 = 1*(1-x) + 1*x*(1-x)*(1-x^2) + 1*x^2*(1-x)*(1-x^2)*(1-x^3) + 2*x^3*(1-x)*(1-x^2)*(1-x^3)*(1-x^4) + 2*x^4*(1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5) + ...
From _Gus Wiseman_, Oct 14 2023: (Start)
The a(1) = 1 through a(8) = 10 partitions:
  (1)  (11)  (21)   (211)   (221)    (321)     (421)      (3221)
             (111)  (1111)  (311)    (2211)    (2221)     (3311)
                            (2111)   (3111)    (3211)     (4211)
                            (11111)  (21111)   (4111)     (22211)
                                     (111111)  (22111)    (32111)
                                               (31111)    (41111)
                                               (211111)   (221111)
                                               (1111111)  (311111)
                                                          (2111111)
                                                          (11111111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 301 terms from David W. Wilson)
George E. Andrews, George Beck, and Brian Hopkins, On a Conjecture of Hanna Connecting Distinct Part and Complete Partitions, Annals of Comb., 24(2020), pp. 217-224.
George Beck and Shane Chern, Reciprocity between partitions and compositions, arXiv:2108.04363 [math.CO], 2021.
Nathaniel Johnston and Sarah Plosker, Laplacian {-1,0,1}- and {-1,1}-diagonalizable graphs, arXiv:2308.15611 [math.CO], 2023.
SeungKyung Park, Complete Partitions, Fibonacci Quarterly, Vol. 36 (1998), pp. 354-360.

Cf. A002033, A003513, A209405, A261036, A286929, A286097.
For parts instead of sums we have A000009 (sc. coverings), ranks A055932.
The strict case is A188431, complement A365831.
These partitions have ranks A325781.
First column k = 0 of A365923.
The complement is counted by A365924, ranks A365830.
Cf. A000041, A018818, A046663, A047967, A276024, A304792, A325799, A365543, A365658, A365918, A365921.

import Data.MemoCombinators (memo3, integral, Memo)
a126796 n = a126796_list !! n
a126796_list = map (pMemo 1 1) [0..] where
   pMemo = memo3 integral integral integral p
   p   0 = 1
   p s k m
     | k > min m s = 0
     | otherwise   = pMemo (s + k) k (m - k) + pMemo s (k + 1) m
-- Reinhard Zumkeller, Aug 07 2015

isCompl := proc(p,n) local m,pers,reps,f,lst,s; reps := {}; pers := combinat[permute](p); for m from 1 to nops(pers) do lst := op(m,pers); for f from 1 to nops(lst) do s := add( op(i,lst),i=1..f); reps := reps union {s}; od; od; for m from 1 to n do if not m in reps then RETURN(false); fi; od; RETURN(true); end: A126796 := proc(n) local prts, res,p; prts := combinat[partition](n); res :=0; for p from 1 to nops(prts) do if isCompl(op(p,prts),n) then res := res+1; fi; od; RETURN(res); end: for n from 1 to 40 do printf("%d %d ",n,A126796(n)); od; # R. J. Mathar, Feb 27 2007
# At the beginning of the 2nd Maple program replace the current 15 by any other positive integer n in order to obtain a(n). - Emeric Deutsch, Mar 04 2007
with(combinat): a:=proc(n) local P,b,k,p,S,j: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i],i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: end: seq(a(n),n=1..30); # Emeric Deutsch, Mar 04 2007
with(combinat): n:=15: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i],i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: b; # Emeric Deutsch, Mar 04 2007

T[n_, k_] := T[n, k] = If[k <= 1, 1, If[n < 2k-1, T[n, Floor[(n+1)/2]], T[n, k-1] + T[n-k, k]]];
a[n_] := T[n, Floor[(n+1)/2]];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Apr 11 2017, after Franklin T. Adams-Watters *)
nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]]; Table[Length[Select[IntegerPartitions[n], nmz[#]=={}&]],{n,0,15}] (* Gus Wiseman, Oct 14 2023 *)

{T(n,k)=if(k<=1,1,if(n<2*k-1,T(n,floor((n+1)/2)),T(n,k-1)+T(n-k,k)))}
{a(n)=T(n,floor((n+1)/2))} /* If modified to save earlier results, this would be efficient. */ /* Franklin T. Adams-Watters, Mar 22 2007 */

/* As coefficients in g.f.: */
{a(n)=local(A=[1,1]);for(i=1,n+1,A=concat(A,0);A[#A]=polcoeff(1-sum(m=1,#A,A[m]*x^m*prod(k=1,m,1-x^k +x*O(x^#A))),#A) );A[n+1]}
for(n=0,50,print1(a(n),",")) /* Paul D. Hanna, Mar 06 2012 */

G.f.: 1 = Sum_{n>=0} a(n)*x^n*Product_{k=1..n+1} (1-x^k). - Paul D. Hanna, Mar 08 2012
a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi + 25*Pi/(24*sqrt(6))) / sqrt(n) + (25/16 - 1679*Pi^2/6912)/n). - Vaclav Kotesovec, May 24 2018, extended Nov 02 2019
a(n) = A000041(n) - A365924(n). - Gus Wiseman, Oct 14 2023

More terms from R. J. Mathar, Feb 27 2007
More terms from Emeric Deutsch, Mar 04 2007
Further terms from Franklin T. Adams-Watters and David W. Wilson, Mar 22 2007

A299701 Number of distinct subset-sums of the integer partition with Heinz number n.

Original entry on oeis.org

1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 5, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 6, 3, 4, 4, 6, 2, 7, 2, 6, 4, 4, 4, 7, 2, 4, 4, 7, 2, 8, 2, 6, 6, 4, 2, 7, 3, 6, 4, 6, 2, 8, 4, 8, 4, 4, 2, 8, 2, 4, 5, 7, 4, 8, 2, 6, 4, 7, 2, 8, 2, 4, 6, 6, 4, 8, 2, 8, 5, 4, 2, 9, 4, 4, 4

Offset: 1

Gus Wiseman, Feb 17 2018

nonn

An integer n is a subset-sum of an integer partition y if there exists a submultiset of y with sum n. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

Position of first appearance of n appears to be A259941(n-1) = least Heinz number of a complete partition of n-1. - Gus Wiseman, Nov 16 2023

			The subset-sums of (5,1,1,1) are {0, 1, 2, 3, 5, 6, 7, 8} so a(88) = 8.
The subset-sums of (4,3,1) are {0, 1, 3, 4, 5, 7, 8} so a(70) = 7.

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A000005, A000041, A000720, A001222, A056239, A108917, A112798, A122111, A122768, A215366, A276024, A284640, A296150, A299702.
Positions of first appearances are A259941.
The triangle for this rank statistic is A365658.
The semi version is A366739, sum A366738, strict A366741.
Cf. A032302, A070933, A304792, A304793, A365543, A365920, A367095.

Table[Length[Union[Total/@Subsets[Join@@Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]],{n,100}]

a(n) <= A000005(n) and a(n) = A000005(n) iff n is the Heinz number of a knapsack partition (A299702).

Comment corrected by Gus Wiseman, Aug 09 2024

A304792 Number of subset-sums of integer partitions of n.

Original entry on oeis.org

1, 2, 5, 10, 19, 34, 58, 96, 152, 240, 361, 548, 795, 1164, 1647, 2354, 3243, 4534, 6150, 8420, 11240, 15156, 19938, 26514, 34513, 45260, 58298, 75704, 96515, 124064, 157072, 199894, 251097, 317278, 395625, 496184, 615229, 765836, 944045, 1168792, 1432439

Offset: 0

Gus Wiseman, May 18 2018

nonn

For a multiset p of positive integers summing to n, a pair (t,p) is defined to be a subset sum if there exists a submultiset of p summing to t. This sequence is dominated by A122768 + A000041 (number of submultisets of integer partitions of n).

			The a(4)=19 subset sums are (0,4), (4,4), (0,31), (1,31), (3,31), (4,31), (0,22), (2,22), (4,22), (0,211), (1,211), (2,211), (3,211), (4,211), (0,1111), (1,1111), (2,1111), (3,1111), (4,1111).

Robert Price, Table of n, a(n) for n = 0..70

Cf. A000041, A108917, A122768, A276024, A284640, A299701, A301856, A301934, A301979, A304793.

b:= proc(n, i, s) option remember; `if`(n=0, nops(s),
     `if`(i<1, 0, b(n, i-1, s)+b(n-i, min(n-i, i),
      map(x-> [x, x+i][], s))))
    end:
a:= n-> b(n$2, {0}):
seq(a(n), n=0..40);  # Alois P. Heinz, May 18 2018

Table[Total[Length[Union[Total/@Subsets[#]]]&/@IntegerPartitions[n]],{n,15}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0, Length[s],
     If[i < 1, 0, b[n, i - 1, s] + b[n - i, Min[n - i, i],
     {#, # + i}& /@ s // Flatten // Union]]];
a[n_] := b[n, n, {0}];
a /@ Range[0, 40] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A304792_T(n,i,s,l):
    if n==0: return l
    if i<1: return 0
    return A304792_T(n,i-1,s,l)+A304792_T(n-i,min(n-i,i),(t:=tuple(sorted(set(s+tuple(x+i for x in s))))),len(t))
def A304792(n): return A304792_T(n,n,(0,),1) # Chai Wah Wu, Sep 25 2023, after Alois P. Heinz

a(n) = A276024(n) + A000041(n).

A002219 a(n) is the number of partitions of 2n that can be obtained by adding together two (not necessarily distinct) partitions of n.

Original entry on oeis.org

1, 3, 6, 14, 25, 53, 89, 167, 278, 480, 760, 1273, 1948, 3089, 4682, 7177, 10565, 15869, 22911, 33601, 47942, 68756, 96570, 136883, 189674, 264297, 362995, 499617, 678245, 924522, 1243098, 1676339, 2237625, 2988351, 3957525, 5247500, 6895946, 9070144, 11850304

Offset: 1

N. J. A. Sloane

			Here are the seven partitions of 5: 1^5, 1^3 2, 1 2^2, 1^2 3, 2 3, 1 4, 5. Adding these together in pairs we get a(5) = 25 partitions of 10: 1^10, 1^8 2, 1^6 2^2, etc. (we get all partitions of 10 into parts of size <= 5 - there are 30 such partitions - except for five of them: we do not get 2 4^2, 3^2 4, 2^3 4, 1 3^3, 2^5). - _N. J. A. Sloane_, Jun 03 2012
From _Gus Wiseman_, Oct 27 2022: (Start)
The a(1) = 1 through a(4) = 14 partitions:
  (11)  (22)    (33)      (44)
        (211)   (321)     (422)
        (1111)  (2211)    (431)
                (3111)    (2222)
                (21111)   (3221)
                (111111)  (3311)
                          (4211)
                          (22211)
                          (32111)
                          (41111)
                          (221111)
                          (311111)
                          (2111111)
                          (11111111)
(End)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..140 (terms 1..89 from Alois P. Heinz)
N. Metropolis and P. R. Stein, An elementary solution to a problem in restricted partitions, J. Combin. Theory, 9 (1970), 365-376.
Vladimir A. Shlyk, Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number, arXiv:1805.07989 [math.CO], 2018.

Column m=2 of A213086.
Bisection of A276107.
Cf. A064914, A000041, A002220, A002221, A002222, A213074, A006827, A046663.
The strict version is A237258, ranked by A357854.
Ranked by A357976 = positions of nonzero terms in A357879.
A122768 counts distinct submultisets of partitions.
A304792 counts subset-sums of partitions, positive A276024, strict A284640.
Cf. A108917, A235130, A237194, A300061.

g:= proc(n, i) option remember;
     `if`(n=0, 1, `if`(i>1, g(n, i-1), 0)+`if`(i>n, 0, g(n-i, i)))
    end:
b:= proc(n, i, s) option remember;
     `if`(i=1 and s<>{} or n in s, g(n, i), `if`(i<1 or s={}, 0,
      b(n, i-1, s)+ `if`(i>n, 0, b(n-i, i, map(x-> {`if`(x>n-i, NULL,
      max(x, n-i-x)), `if`(xn, NULL, max(x-i, n-x))}[], s)))))
    end:
a:= n-> b(2*n, n, {n}):
seq(a(n), n=1..25);  # Alois P. Heinz, Jul 10 2012

Mathematica

b[n_, i_, s_] := b[n, i, s] = If[MemberQ[s, 0 | n], 0, If[n == 0, 1, If[i < 1, 0, b[n, i-1, s] + If[i <= n, b[n-i, i, Select[Flatten[Transpose[{s, s-i}]], 0 <= # <= n-i &]], 0]]]]; A006827[n_] := b[2*n, 2*n, {n}]; a[n_] := PartitionsP[2*n] - A006827[n]; Table[Print[an = a[n]]; an, {n, 1, 25}] (* Jean-François Alcover, Nov 12 2013, after Alois P. Heinz *) primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]; subptns[s_]:=primeMS/@Divisors[Times@@Prime/@s]; Table[Length[Select[IntegerPartitions[2n],MemberQ[Total/@subptns[#],n]&]],{n,10}] (* Gus Wiseman, Oct 27 2022 *)

Python

from itertools import combinations_with_replacement from sympy.utilities.iterables import partitions def A002219(n): return len({tuple(sorted((p+q).items())) for p, q in combinations_with_replacement(tuple(Counter(p) for p in partitions(n)),2)}) # Chai Wah Wu, Sep 20 2023

Formula

See A213074 for Metropolis and Stein's formulas.

a(n) = A000041(2*n) - A006827(n) = A000041(2*n) - A046663(2*n,n).

a(n) = A276107(2*n). - Max Alekseyev, Oct 17 2022

Extensions

Better description from Vladeta Jovovic, Mar 06 2000

More terms from Christian G. Bower, Oct 12 2001

Edited by N. J. A. Sloane, Jun 03 2012

More terms from Alois P. Heinz, Jul 10 2012

A284640 Number of positive subset sums of strict integer partitions of n.

Original entry on oeis.org

1, 1, 4, 4, 7, 13, 17, 23, 34, 49, 62, 87, 112, 149, 199, 249, 318, 408, 512, 635, 820, 991, 1238, 1515, 1864, 2248, 2770, 3326, 4030, 4818, 5808, 6882, 8290, 9756, 11639, 13719, 16236, 18999, 22468, 26144, 30724, 35761, 41754, 48357, 56380, 65018, 75438

Offset: 1

Gus Wiseman, Mar 31 2017

nonn

For a strict integer partition p summing to n, a pair (t,p) is defined to be a positive subset sum if there exists a nonempty subset of p summing to t.

			The a(6)=13 subset sums are:
(6,6),
(1,51), (5,51), (6,51),
(2,42), (4,42), (6,42),
(1,321), (2,321), (3,321), (4,321), (5,321), (6,321).

Robert Price, Table of n, a(n) for n = 1..80

Cf. A122768, A275972, A276024.

nn=25;Total/@Table[Function[ptn,Length[Union[Total/@Rest[Subsets[ptn]]]]]/@Select[IntegerPartitions[n],UnsameQ@@#&],{n,nn}]

A046663 Triangle: T(n,k) = number of partitions of n (>=2) with no subsum equal to k (1 <= k <= n-1).

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 4, 3, 5, 3, 4, 4, 4, 4, 4, 4, 4, 7, 5, 7, 8, 7, 5, 7, 8, 7, 7, 8, 8, 7, 7, 8, 12, 9, 12, 9, 17, 9, 12, 9, 12, 14, 11, 12, 12, 13, 13, 12, 12, 11, 14, 21, 15, 19, 15, 21, 24, 21, 15, 19, 15, 21, 24, 19, 20, 19, 21, 22, 22, 21, 19, 20, 19, 24, 34, 23, 30, 24, 30, 25, 46, 25, 30, 24, 30, 23, 34

Offset: 2

N. J. A. Sloane

			For n = 4 there are two partitions (4, 2+2) with no subsum equal to 1, two (4, 3+1) with no subsum equal to 2 and two (4, 2+2) with no subsum equal to 3.
Triangle T(n,k) begins:
   1;
   1,  1;
   2,  2,  2;
   2,  2,  2,  2;
   4,  3,  5,  3,  4;
   4,  4,  4,  4,  4,  4;
   7,  5,  7,  8,  7,  5,  7;
   8,  7,  7,  8,  8,  7,  7,  8;
  12,  9, 12,  9, 17,  9, 12,  9, 12;
  ...
From _Gus Wiseman_, Oct 11 2023: (Start)
Row n = 8 counts the following partitions:
  (8)     (8)    (8)     (8)     (8)     (8)    (8)
  (62)    (71)   (71)    (71)    (71)    (71)   (62)
  (53)    (53)   (62)    (62)    (62)    (53)   (53)
  (44)    (44)   (611)   (611)   (611)   (44)   (44)
  (422)   (431)  (44)    (53)    (44)    (431)  (422)
  (332)          (422)   (521)   (422)          (332)
  (2222)         (2222)  (5111)  (2222)         (2222)
                         (332)
(End)

Alois P. Heinz, Rows n = 2..98, flattened
P. Erdős, J. L. Nicolas and A. Sárközy, On the number of partitions of n without a given subsum (I), Discrete Math., 75 (1989), 155-166 = Annals Discrete Math. Vol. 43, Graph Theory and Combinatorics 1988, ed. B. Bollobas.

Column k = 0 and diagonal k = n are both A002865.
Central diagonal n = 2k is A006827.
The complement with expanded domain is A365543.
The strict case is A365663, complement A365661.
Row sums are A365918, complement A304792.
For subsets instead of partitions we have A366320, complement A365381.
A000041 counts integer partitions, strict A000009.
A276024 counts distinct subset-sums of partitions.
A364272 counts sum-full strict partitions, sum-free A364349.
Cf. A000124, A002219, A093971, A108917, A122768, A299701, A365658.

g:= proc(n, i) option remember;
     `if`(n=0, 1, `if`(i>1, g(n, i-1), 0)+`if`(i>n, 0, g(n-i, i)))
    end:
b:= proc(n, i, s) option remember;
     `if`(0 in s or n in s, 0, `if`(n=0 or s={}, g(n, i),
     `if`(i<1, 0, b(n, i-1, s)+`if`(i>n, 0, b(n-i, i,
      select(y-> 0<=y and y<=n-i, map(x-> [x, x-i][], s)))))))
    end:
T:= (n, k)-> b(n, n, {min(k, n-k)}):
seq(seq(T(n, k), k=1..n-1), n=2..16);  # Alois P. Heinz, Jul 13 2012

g[n_, i_] := g[n, i] = If[n == 0, 1, If[i > 1, g[n, i-1], 0] + If[i > n, 0, g[n-i, i]]]; b[n_, i_, s_] := b[n, i, s] = If[MemberQ[s, 0 | n], 0, If[n == 0 || s == {}, g[n, i], If[i < 1, 0, b[n, i-1, s] + If[i > n, 0, b[n-i, i, Select[Flatten[s /. x_ :> {x, x-i}], 0 <= # <= n-i &]]]]]]; t[n_, k_] := b[n, n, {Min[k, n-k]}]; Table[t[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Aug 20 2013, translated from Maple *)
Table[Length[Select[IntegerPartitions[n],FreeQ[Total/@Subsets[#],k]&]],{n,2,10},{k,1,n-1}] (* Gus Wiseman, Oct 11 2023 *)

Corrected and extended by Don Reble, Nov 04 2001

A089723 a(1)=1; for n>1, a(n) gives number of ways to write n as n = x^y, 2 <= x, 1 <= y.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1

Offset: 1

Naohiro Nomoto, Jan 07 2004

This function depends only on the prime signature of n. - Franklin T. Adams-Watters, Mar 10 2006
a(n) is the number of perfect divisors of n. Perfect divisor of n is divisor d such that d^k = n for some k >= 1. a(n) > 1 for perfect powers n = A001597(m) for m > 2. - Jaroslav Krizek, Jan 23 2010
Also the number of uniform perfect integer partitions of n - 1. An integer partition of n is uniform if all parts appear with the same multiplicity, and perfect if every nonnegative integer up to n is the sum of a unique submultiset. The Heinz numbers of these partitions are given by A326037. The a(16) = 3 partitions are: (8,4,2,1), (4,4,4,1,1,1), (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1). - Gus Wiseman, Jun 07 2019
The record values occur at 1 and at 2^A002182(n) for n > 1. - Amiram Eldar, Nov 06 2020

			144 = 2^4 * 3^2, gcd(4,2) = 2, d(2) = 2, so a(144) = 2. The representations are 144^1 and 12^2.
From _Friedjof Tellkamp_, Jun 14 2025: (Start)
n:          1, 2, 3, 4, 5, 6, 7, 8, 9, ...
----------------------------------------------------
1st powers: 1, 1, 1, 1, 1, 1, 1, 1, 1, ... (A000012)
Squares:    1, 0, 0, 1, 0, 0, 0, 0, 1, ... (A010052)
Cubes:      1, 0, 0, 0, 0, 0, 0, 1, 0, ... (A010057)
Quartics:   1, 0, 0, 0, 0, 0, 0, 0, 0, ... (A374016)
...
Sum:       oo, 1, 1, 2, 1, 1, 1, 2, 2, ...
a(1)=1:     1, 1, 1, 2, 1, 1, 1, 2, 2, ... (= this sequence). (End)

N. J. A. Sloane, Table of n, a(n) for n = 1..20000
Solomon W. Golomb, A new arithmetic function of combinatorial significance, J. Number Theory, Vol. 5, No. 3 (1973), pp. 218-223. 1973JNT.....5..218G
Jan Mycielski, Sur les représentations des nombres naturels par des puissances à base et exposant naturels, Colloquium Mathematicum, Vol. 2 (1951), pp. 254-260. See gamma(n).
N. J. A. Sloane, Maple programs for A007916, A278028, A278029, A052409, A089723, A277564

Cf. A000005, A277564, A278028.
Cf. A000961, A002033, A002182, A007916, A047966, A070941, A108917, A126796, A276024, A326035, A326036, A326037.
Cf. A010052, A010057, A374016, A259362.

with(numtheory):
A089723 := proc(n) local t1,t2,g,j;
if n=1 then 1 else
t1:=ifactors(n)[2]; t2:=nops(t1); g := t1[1][2];
for j from 2 to t2 do g:=gcd(g,t1[j][2]); od:
tau(g); fi; end;
[seq(A089723(n),n=1..100)]; # N. J. A. Sloane, Nov 10 2016

Table[DivisorSigma[0, GCD @@ FactorInteger[n][[All, 2]]], {n, 100}] (* Gus Wiseman, Jun 12 2017 *)

a(n) = if (n==1, 1, numdiv(gcd(factor(n)[,2]))); \\ Michel Marcus, Jun 13 2017

from math import gcd
from sympy import factorint, divisor_sigma
def a(n):
    if n == 1: return 1
    e = list(factorint(n).values())
    g = e[0]
    for ei in e[1:]: g = gcd(g, ei)
    return divisor_sigma(g, 0)
print([a(n) for n in range(1, 105)]) # Michael S. Branicky, Jul 15 2021

If n = Product p_i^e_i, a(n) = d(gcd()). - Franklin T. Adams-Watters, Mar 10 2006
Sum_{n=1..m} a(n) = A255165(m) + 1. - Richard R. Forberg, Feb 16 2015
Sum_{n>=2} a(n)/n^s = Sum_{n>=2} 1/(n^s-1) = Sum_{k>=1} (zeta(s*k)-1) for all real s with Re(s) > 1 (Golomb, 1973). - Amiram Eldar, Nov 06 2020
For n > 1, a(n) = Sum_{i=1..floor(n/2)} floor(n^(1/i))-floor((n-1)^(1/i)). - Wesley Ivan Hurt, Dec 08 2020
Sum_{n>=1} (a(n)-1)/n = 1 (Mycielski, 1951). - Amiram Eldar, Jul 15 2021
From Friedjof Tellkamp, Jun 14 2025: (Start)
a(n) = 1 + A259362(n) = 1 + A010052(n) + A010057(n) + A374016(n) + (...), for n > 1.
G.f.: x + Sum_{j>=2, k>=1} x^(j^k). (End)

cp's OEIS Frontend

A006128 Total number of parts in all partitions of n. Also, sum of largest parts of all partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A299702 Heinz numbers of knapsack partitions.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A301987 Heinz numbers of integer partitions whose product is equal to their sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A126796 Number of complete partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A299701 Number of distinct subset-sums of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A304792 Number of subset-sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python