A122768 -id:A122768 - cp's OEIS frontend

A365658 Triangle read by rows where T(n,k) is the number of integer partitions of n with k distinct possible sums of nonempty submultisets.

1, 1, 1, 1, 0, 2, 1, 1, 1, 2, 1, 0, 2, 0, 4, 1, 1, 3, 0, 1, 5, 1, 0, 3, 0, 3, 0, 8, 1, 1, 3, 2, 2, 1, 2, 10, 1, 0, 5, 0, 3, 0, 5, 0, 16, 1, 1, 4, 0, 6, 2, 4, 2, 2, 20, 1, 0, 5, 0, 5, 0, 8, 0, 6, 0, 31, 1, 1, 6, 2, 3, 6, 6, 1, 4, 4, 4, 39, 1, 0, 6, 0, 6, 0, 12, 0, 8, 0, 13, 0, 55

Offset: 1

Gus Wiseman, Sep 16 2023

Conjecture: Positions of strictly positive rows are given by A048166.

			Triangle begins:
  1
  1  1
  1  0  2
  1  1  1  2
  1  0  2  0  4
  1  1  3  0  1  5
  1  0  3  0  3  0  8
  1  1  3  2  2  1  2 10
  1  0  5  0  3  0  5  0 16
  1  1  4  0  6  2  4  2  2 20
  1  0  5  0  5  0  8  0  6  0 31
  1  1  6  2  3  6  6  1  4  4  4 39
  1  0  6  0  6  0 12  0  8  0 13  0 55
  1  1  6  0  6  3 16  3  5  3  7  8  5 71

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

Row sums are A000041.
Last column n = k is A126796.
Column k = 3 appears to be A137719.
This is the triangle for the rank statistic A299701.
Central column n = 2k is A365660.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A365543 counts partitions with a submultiset summing to k, strict A365661.
Cf. A046663, A108917, A122768, A304792, A364272, A364916, A365381.

Table[Length[Select[IntegerPartitions[n],Length[Union[Total/@Rest[Subsets[#]]]]==k&]],{n,10},{k,n}]

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 18 2018

nonn

A positive integer n is a positive 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).
a(n) <= A000005(n).
One less than the number of distinct values obtained when A056239 is applied to all divisors of n. - Antti Karttunen, Jul 01 2018

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

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A056239, A122768, A276024, A284640, A296150, A299701, A299702, A301855, A301935, A301957, A304792, A304795, A305611.

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

up_to = 65537;
A056239(n) = { my(f); if(1==n, 0, f=factor(n); sum(i=1, #f~, f[i,2] * primepi(f[i,1]))); }
v056239 = vector(up_to,n,A056239(n));
A304793(n) = { my(m=Map(),s,k=0); fordiv(n,d,if(!mapisdefined(m,s = v056239[d]), mapput(m,s,s); k++)); (k-1); }; \\ Antti Karttunen, Jul 01 2018

More terms from Antti Karttunen, Jul 01 2018

A317142 Number of refinement-ordered pairs of strict integer partitions of n.

Original entry on oeis.org

1, 1, 1, 3, 3, 5, 9, 12, 16, 24, 37, 47, 68, 90, 123, 180, 228, 307, 408, 540, 694, 970, 1207, 1598, 2048, 2669, 3357, 4382, 5599, 7109, 8990, 11428, 14330, 18144, 22652, 28343, 35746, 44269, 55094, 68384, 84780, 104477, 129360, 158682, 195323, 240177, 293704

Offset: 0

Gus Wiseman, Jul 22 2018

nonn

If x and y are strict partitions of the same integer and it is possible to produce x by further partitioning the parts of y, flattening, and sorting, then x <= y.

This sequence is dominated by A294617 (set partitions of strict partitions).

			The a(9) = 24 refinement-ordered pairs:
    (9)<=(9)
  (5,4)<=(9)   (5,4)<=(5,4)
  (6,3)<=(9)   (6,3)<=(6,3)
  (7,2)<=(9)   (7,2)<=(7,2)
  (8,1)<=(9)   (8,1)<=(8,1)
(4,3,2)<=(9) (4,3,2)<=(5,4) (4,3,2)<=(6,3) (4,3,2)<=(7,2) (4,3,2)<=(4,3,2)
(5,3,1)<=(9) (5,3,1)<=(5,4) (5,3,1)<=(6,3) (5,3,1)<=(8,1) (5,3,1)<=(5,3,1)
(6,2,1)<=(9) (6,2,1)<=(6,3) (6,2,1)<=(7,2) (6,2,1)<=(8,1) (6,2,1)<=(6,2,1)

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

Cf. A002846, A108917, A122768, A213427, A265947, A284640, A294617, A299201, A300383, A317141.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Sum[Length[Union[Select[Sort/@Map[Total,mps[ptn],{2}],UnsameQ@@#&]]],{ptn,Select[IntegerPartitions[n],UnsameQ@@#&]}],{n,30}]

A301899 Heinz numbers of strict knapsack partitions. Squarefree numbers such that every divisor has a different Heinz weight A056239(d).

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109

Offset: 1

Gus Wiseman, Mar 28 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).

			42 is the Heinz number of (4,2,1) which is strict and knapsack, so is in the sequence. 45 is the Heinz number of (3,2,2) which is knapsack but not strict, so is not in the sequence. 30 is the Heinz number of (3,2,1) which is strict but not knapsack, so is not in the sequence.
Sequence of strict knapsack partitions begins: (), (1), (2), (3), (21), (4), (31), (5), (6), (41), (32), (7), (8), (42), (51), (9), (61).

Cf. A000712, A005117, A056239, A108917, A112798, A122768, A275972, A276024, A284640, A296150, A299701, A299702, A299729, A301829, A301854, A301900.

wt[n_]:=If[n===1,0,Total[Cases[FactorInteger[n],{p_,k_}:>k*PrimePi[p]]]];
Select[Range[100],SquareFreeQ[#]&&UnsameQ@@wt/@Divisors[#]&]

Intersection of A299702 and A005117.

A365918 Number of distinct non-subset-sums of integer partitions of n.

Original entry on oeis.org

0, 1, 2, 6, 8, 19, 24, 46, 60, 101, 124, 206, 250, 378, 462, 684, 812, 1165, 1380, 1927, 2268, 3108, 3606, 4862, 5648, 7474, 8576, 11307, 12886, 16652, 19050, 24420, 27584, 35225, 39604, 49920, 56370, 70540, 78608, 98419, 109666, 135212, 151176, 185875, 205308

Offset: 1

Gus Wiseman, Sep 23 2023

nonn

For an integer partition y of n, we call a positive integer k <= n a non-subset-sum iff there is no submultiset of y summing to k.

			The a(6) = 19 ways, showing each partition and its non-subset-sums:
       (6): 1,2,3,4,5
      (51): 2,3,4
      (42): 1,3,5
     (411): 3
      (33): 1,2,4,5
     (321):
    (3111):
     (222): 1,3,5
    (2211):
   (21111):
  (111111):

Row sums of A046663, strict A365663.
The zero-full complement (subset-sums) is A304792.
The strict case is A365922.
Weighted row-sums of A365923, rank statistic A325799, complement A365658.
A000041 counts integer partitions, strict A000009.
A126796 counts complete partitions, ranks A325781, strict A188431.
A365543 counts partitions with a submultiset summing to k, strict A365661.
A365924 counts incomplete partitions, ranks A365830, strict A365831.
Cf. A006827, A122768, A364272, A364350, A364839, A365919, A365921.

Table[Total[Length[Complement[Range[n],Total/@Subsets[#]]]&/@IntegerPartitions[n]],{n,10}]

# uses A304792_T
from sympy import npartitions
def A365918(n): return (n+1)*npartitions(n)-A304792_T(n,n,(0,),1) # Chai Wah Wu, Sep 25 2023

a(n) = (n+1)*A000041(n) - A304792(n).

a(21)-a(45) from Chai Wah Wu, Sep 25 2023

A366738 Number of semi-sums of integer partitions of n.

Original entry on oeis.org

0, 0, 1, 2, 5, 9, 17, 28, 46, 72, 111, 166, 243, 352, 500, 704, 973, 1341, 1819, 2459, 3277, 4363, 5735, 7529, 9779, 12685, 16301, 20929, 26638, 33878, 42778, 53942, 67583, 84600, 105270, 130853, 161835, 199896, 245788, 301890, 369208, 451046, 549002, 667370

Offset: 0

Gus Wiseman, Nov 06 2023

nonn

We define a semi-sum of a multiset to be any sum of a 2-element submultiset. This is different from sums of pairs of elements. For example, 2 is the sum of a pair of elements of {1}, but there are no semi-sums.

			The partitions of 6 and their a(6) = 17 semi-sums:
       (6) ->
      (51) -> 6
      (42) -> 6
     (411) -> 2,5
      (33) -> 6
     (321) -> 3,4,5
    (3111) -> 2,4
     (222) -> 4
    (2211) -> 2,3,4
   (21111) -> 2,3
  (111111) -> 2

The non-binary version is A304792.
The strict non-binary version is A365925.
For prime indices instead of partitions we have A366739.
The strict case is A366741.
A000041 counts integer partitions, strict A000009.
A001358 lists semiprimes, squarefree A006881, conjugate A065119.
A126796 counts complete partitions, ranks A325781, strict A188431.
A276024 counts positive subset-sums of partitions, strict A284640.
A365924 counts incomplete partitions, ranks A365830, strict A365831.
Cf. A008967, A046663, A117855, A122768, A238628, A299701, A365543, A365544, A366753, A367095.

Table[Total[Length[Union[Total/@Subsets[#,{2}]]]&/@IntegerPartitions[n]],{n,0,15}]

More terms from Alois P. Heinz, Nov 06 2023

A301830 Number of factorizations of n into factors (greater than 1) of two kinds.

Original entry on oeis.org

1, 2, 2, 5, 2, 6, 2, 10, 5, 6, 2, 16, 2, 6, 6, 20, 2, 16, 2, 16, 6, 6, 2, 36, 5, 6, 10, 16, 2, 22, 2, 36, 6, 6, 6, 46, 2, 6, 6, 36, 2, 22, 2, 16, 16, 6, 2, 76, 5, 16, 6, 16, 2, 36, 6, 36, 6, 6, 2, 64, 2, 6, 16, 65, 6, 22, 2, 16, 6, 22, 2, 108, 2, 6, 16, 16, 6

Offset: 1

Gus Wiseman, Mar 27 2018

nonn

a(n) depends only on the prime signature of n. - Andrew Howroyd, Nov 18 2018

			The a(6) = 6 factorizations: (2*3)*(), (3)*(2), (2)*(3), ()*(2*3), (6)*(), ()*(6).
The a(12) = 16 factorizations:
  ()*(2*2*3), (2)*(2*3), (3)*(2*2), (2*2)*(3), (2*3)*(2), (2*2*3)*(),
  ()*(2*6), (2)*(6), (6)*(2), (2*6)*(), ()*(3*4), (3)*(4), (4)*(3), (3*4)*(),
  ()*(12), (12)*().

Andrew Howroyd, Table of n, a(n) for n = 1..10000
Jacob Sprittulla, On Colored Factorizations, arXiv:2008.09984 [math.CO], 2020.
Index to sequences related to prime signature

Cf. A000712, A001055, A001222, A001405, A122768, A276024, A281113, A284640, A295632, A299701, A299702, A299729, A301829.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Sum[Length[facs[d]]*Length[facs[n/d]],{d,Divisors[n]}],{n,100}]

MultEulerT(u)={my(v=vector(#u)); v[1]=1; for(k=2, #u, forstep(j=#v\k*k, k, -k, my(i=j, e=0); while(i%k==0, i/=k; e++; v[j]+=binomial(e+u[k]-1, e)*v[i]))); v}
seq(n)={MultEulerT(vector(n, i, 2))} \\ Andrew Howroyd, Nov 18 2018

Dirichlet g.f.: Product_{n > 1} 1/(1 - n^(-s))^2. [corrected by Ilya Gutkovskiy, Dec 14 2020]

a(p^n) = A000712(n) for prime p. - Andrew Howroyd, Nov 18 2018

A316314 Number of distinct nonempty-subset-averages of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 4, 1, 3, 3, 1, 1, 4, 1, 4, 3, 3, 1, 5, 1, 3, 1, 4, 1, 5, 1, 1, 3, 3, 3, 5, 1, 3, 3, 5, 1, 7, 1, 4, 4, 3, 1, 6, 1, 4, 3, 4, 1, 5, 3, 5, 3, 3, 1, 8, 1, 3, 4, 1, 3, 7, 1, 4, 3, 7, 1, 7, 1, 3, 4, 4, 3, 7, 1, 6, 1, 3, 1, 8, 3, 3, 3, 5, 1, 7, 3, 4, 3, 3, 3, 7, 1, 4, 4, 5, 1, 7, 1, 5, 5

Offset: 1

Gus Wiseman, Jun 29 2018

nonn

A rational number q is a nonempty-subset-average of an integer partition y if there exists a nonempty submultiset of y with average q.

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

			The a(42) = 7 subset-averages of (4,2,1) are 1, 3/2, 2, 7/3, 5/2, 3, 4.
The a(72) = 7 subset-averages of (2,2,1,1,1) are 1, 5/4, 4/3, 7/5, 3/2, 5/3, 2.

Cf. A032302, A056239, A108917, A122768, A275972, A276024, A296150, A299701, A299702, A301899, A301957, A304793, A316313.

One less than A316398.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Length[Union[Mean/@Rest[Subsets[primeMS[n]]]]],{n,100}]

up_to = 65537;
A056239(n) = { my(f); if(1==n, 0, f=factor(n); sum(i=1, #f~, f[i,2] * primepi(f[i,1]))); }
v056239 = vector(up_to,n,A056239(n));
A316314(n) = { my(m=Map(),s,k=0); fordiv(n,d,if((d>1)&&!mapisdefined(m,s = v056239[d]/bigomega(d)), mapput(m,s,s); k++)); (k); }; \\ Antti Karttunen, Sep 23 2018

a(n) = A316398(n) - 1.

More terms from Antti Karttunen, Sep 23 2018

A347461 Number of distinct possible alternating products of integer partitions of n.

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 7, 10, 12, 16, 19, 23, 27, 34, 41, 49, 57, 67, 78, 91, 106, 125, 147, 166, 187, 215, 245, 277, 317, 357, 405, 460, 524, 592, 666, 740, 829, 928, 1032, 1147, 1273, 1399, 1555, 1713, 1892, 2087, 2298, 2523, 2783, 3070, 3383, 3724, 4104, 4504

Offset: 0

Gus Wiseman, Oct 06 2021

nonn

We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)).

			Partitions representing each of the a(7) = 10 alternating products are:
     (7) -> 7
    (61) -> 6
    (52) -> 5/2
   (511) -> 5
    (43) -> 4/3
   (421) -> 2
  (4111) -> 4
   (331) -> 1
   (322) -> 3
  (3211) -> 3/2

The version for alternating sum is A004526.
Counting only integers gives A028310, reverse A347707.
The version for factorizations is A347460, reverse A038548.
The reverse version is A347462.
A000041 counts partitions.
A027187 counts partitions of even length.
A027193 counts partitions of odd length.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A108917 counts knapsack partitions, ranked by A299702.
A122768 counts distinct submultisets of partitions.
A126796 counts complete partitions.
A293627 counts knapsack factorizations by sum.
A301957 counts distinct subset-products of prime indices.
A304792 counts subset-sums of partitions, positive A276024, strict A284640.
A304793 counts distinct positive subset-sums of prime indices.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
Cf. A000070, A001055, A002033, A002219, A028983, A119620, A325768, A345926, A347443, A347444, A347445, A347446.

altprod[q_]:=Product[q[[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Union[altprod/@IntegerPartitions[n]]],{n,0,30}]

A048574 Self-convolution of 1 2 3 5 7 11 15 22 30 42 56 77 ... (A000041).

Original entry on oeis.org

1, 4, 10, 22, 43, 80, 141, 240, 397, 640, 1011, 1568, 2395, 3604, 5360, 7876, 11460, 16510, 23588, 33418, 47006, 65640, 91085, 125596, 172215, 234820, 318579, 430060, 577920, 773130, 1030007, 1366644, 1806445, 2378892, 3121835, 4082796

Offset: 2

Alford Arnold

Number of proper partitions of n into parts of two kinds (i.e. both kinds must be present). - Franklin T. Adams-Watters, Feb 08 2006

			a(4) = 22 because (1,2,3,5)*(5,3,2,1) = 5 + 6 + 6 + 5 = 22

Reinhard Zumkeller, Table of n, a(n) for n = 2..5000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 804

Cf. A000041, A000712, A023626.
Essentially the same as A052837.
Cf. A122768.
Column k=2 of A060642.

a048574 n = a048574_list !! (n-2)
a048574_list = f (drop 2 a000041_list) [1] where
f (p:ps) rs = (sum $ zipWith (*) rs $ tail a000041_list) : f ps (p : rs)
-- Reinhard Zumkeller, Nov 09 2015

spec := [S,{C=Sequence(Z,1 <= card),B=Set(C,1 <= card),S=Prod(B,B)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20); # Franklin T. Adams-Watters, Feb 08 2006
# second Maple program:
a:= n-> (p-> add(p(j)*p(n-j), j=1..n-1))(combinat[numbpart]):
seq(a(n), n=2..40);  # Alois P. Heinz, May 26 2018

a[n_] := First[ ListConvolve[ pp = Array[ PartitionsP, n], pp]]; Table[ a[n], {n, 1, 36}] (* Jean-François Alcover, Oct 21 2011 *)
Table[ListConvolve[PartitionsP[Range[n]],PartitionsP[Range[n]]],{n,40}]// Flatten (* Harvey P. Dale, Oct 29 2020 *)

a(n) = sum(k=1, n-1, numbpart(k)*numbpart(n-k)); \\ Michel Marcus, Dec 11 2016

From Franklin T. Adams-Watters, Feb 08 2006: (Start)
a(0) = 0, a(n) = A000712(n)-2*A000041(n) for n>0.
a(n) = Sum_{k=1..n-1} A000041(k)*A000041(n-k).
G.f.: ((Product_{k>0} 1/(1-x^k))-1)^2 = (exp(Sum_{k>0} (x^k/(1-x^k)/k))-1)^2. (End)
a(n) ~ exp(2*Pi*sqrt(n/3)) / (4*3^(3/4)*n^(5/4)). - Vaclav Kotesovec, Mar 10 2018

More terms from Larry Reeves (larryr(AT)acm.org), Sep 29 2000

cp's OEIS Frontend

A365658 Triangle read by rows where T(n,k) is the number of integer partitions of n with k distinct possible sums of nonempty submultisets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A317142 Number of refinement-ordered pairs of strict integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A301899 Heinz numbers of strict knapsack partitions. Squarefree numbers such that every divisor has a different Heinz weight A056239(d).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A365918 Number of distinct non-subset-sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A366738 Number of semi-sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A301830 Number of factorizations of n into factors (greater than 1) of two kinds.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A316314 Number of distinct nonempty-subset-averages of the integer partition with Heinz number n.

Views

Author