A325877 -id:A325877 - cp's OEIS frontend

A325865 Number of maximal subsets of {1..n} of which every subset has a different sum.

1, 1, 1, 3, 3, 6, 14, 23, 27, 40, 64, 104, 180, 275, 399, 554, 679, 872, 1117, 1431, 1920, 2520, 3530, 4751, 6644, 8855, 12021, 15461, 19939, 25109, 31656, 38750, 46204, 55650, 65942, 78045, 91304, 106592, 124761, 145701, 172343, 201217, 238739, 280601, 339746, 400394

Offset: 0

Gus Wiseman, Jun 01 2019

nonn

			The a(1) = 1 through a(6) = 14 subsets:
  {1}  {1,2}  {1,2}  {1,3}    {1,2,4}  {1,2,4}
              {1,3}  {1,2,4}  {1,2,5}  {1,2,5}
              {2,3}  {2,3,4}  {1,3,5}  {1,2,6}
                              {2,3,4}  {1,3,5}
                              {2,4,5}  {1,3,6}
                              {3,4,5}  {1,4,6}
                                       {2,3,4}
                                       {2,3,6}
                                       {2,4,5}
                                       {2,5,6}
                                       {3,4,5}
                                       {3,4,6}
                                       {3,5,6}
                                       {4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..60

Cf. A002033, A108917, A143823, A196723, A275972.

Cf. A325860, A325864, A325866, A325867, A325877, A325878, A325879, A325880.

fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&)/@y];
Table[Length[fasmax[Select[Subsets[Range[n]],UnsameQ@@Plus@@@Subsets[#]&]]],{n,0,10}]

a(n)={
  my(ismaxl(w)=for(k=1, n, if(!bitand(w,w< n, ismaxl(w),
         my(s=self()(k+1, b,w));
         if(!bitand(w,w<Andrew Howroyd, Mar 23 2025

a(18) onwards from Andrew Howroyd, Mar 23 2025

A326016 Number of knapsack partitions of n such that no addition of one part up to the maximum is knapsack.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 1, 1, 0, 3, 0, 0, 0, 1, 0, 8, 0, 8, 4, 3, 0, 11, 5, 3, 2, 5, 0, 29, 2, 9, 8, 20, 2

Offset: 1

Gus Wiseman, Jun 03 2019

An integer partition is knapsack if every distinct submultiset has a different sum.

The Heinz numbers of these partitions are given by A326018.

			The initial terms count the following partitions:
  15: (5,4,3,3)
  21: (7,6,5,3)
  21: (7,5,3,3,3)
  24: (8,7,6,3)
  25: (7,5,5,4,4)
  27: (9,8,7,3)
  27: (9,7,6,5)
  27: (8,7,3,3,3,3)
  31: (10,8,6,6,1)
  33: (11,9,7,3,3)
  33: (11,8,5,5,4)
  33: (11,7,6,6,3)
  33: (11,7,3,3,3,3,3)
  33: (11,5,5,4,4,4)
  33: (10,9,8,3,3)
  33: (10,8,6,6,3)
  33: (10,8,3,3,3,3,3)

Cf. A002033, A108917, A275972, A276024.

Cf. A325863, A325864, A325877, A325878, A325880, A326015, A326017, A326018.

sums[ptn_]:=sums[ptn]=If[Length[ptn]==1,ptn,Union@@(Join[sums[#],sums[#]+Total[ptn]-Total[#]]&/@Union[Table[Delete[ptn,i],{i,Length[ptn]}]])];
ksQ[y_]:=Length[sums[Sort[y]]]==Times@@(Length/@Split[Sort[y]]+1)-1;
maxks[n_]:=Select[IntegerPartitions[n],ksQ[#]&&Select[Table[Sort[Append[#,i]],{i,Range[Max@@#]}],ksQ]=={}&];
Table[Length[maxks[n]],{n,30}]

A326015 Number of strict knapsack partitions of n such that no superset with the same maximum is knapsack.

Original entry on oeis.org

1, 0, 1, 1, 1, 0, 1, 1, 3, 2, 4, 4, 5, 3, 3, 4, 6, 2, 7, 6, 13, 9, 19, 16, 27, 21, 40, 33, 47, 37, 54, 48, 66, 51, 65, 65, 77, 64, 80, 71, 96, 60, 106, 95, 112, 93, 152, 114, 191, 131, 242, 192, 303, 210, 366, 300, 482, 352, 581, 450, 713, 539, 882, 689, 995

Offset: 1

Gus Wiseman, Jun 03 2019

nonn

An integer partition is knapsack if every distinct submultiset has a different sum.

These are the subsets counted by A325867, ordered by sum rather than maximum.

			The a(1) = 1 through a(17) = 6 strict knapsack partitions (empty columns not shown):
  {1}  {2,1}  {3,1}  {3,2}  {4,2,1}  {5,2,1}  {4,3,2}  {6,3,1}  {5,4,2}
                                              {5,3,1}  {7,2,1}  {6,3,2}
                                              {6,2,1}           {6,4,1}
                                                                {7,3,1}
.
  {5,4,3}  {6,4,3}  {6,5,3}  {6,5,4}    {7,5,4}    {7,6,4}
  {7,3,2}  {6,5,2}  {8,5,1}  {7,6,2}    {9,4,3}    {9,5,3}
  {7,4,1}  {7,4,2}  {9,3,2}  {8,4,2,1}  {9,6,1}    {9,6,2}
  {8,3,1}  {7,5,1}                      {9,4,2,1}  {8,4,3,2}
           {9,3,1}                                 {9,5,2,1}
                                                   {10,4,2,1}

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..600

Cf. A002033, A108917, A275972, A276024.

Cf. A325863, A325864, A325877, A325878, A325880, A326016, A326017, A326018.

ksQ[y_]:=UnsameQ@@Total/@Union[Subsets[y]]
maxsks[n_]:=Select[Select[IntegerPartitions[n],UnsameQ@@#&&ksQ[#]&],Select[Table[Append[#,i],{i,Complement[Range[Max@@#],#]}],ksQ]=={}&];
Table[Length[maxsks[n]],{n,30}]

A325863 Number of integer partitions of n such that every distinct non-singleton submultiset has a different sum.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 9, 11, 15, 17, 24, 29, 31, 41, 51, 58, 67, 84, 91, 117, 117

Offset: 0

Gus Wiseman, May 31 2019

A knapsack partition (A108917, A299702) is an integer partition such that every submultiset has a different sum. The one non-knapsack partition counted under a(4) is (2,1,1).

			The partition (2,1,1,1) has non-singleton submultisets {1,2} and {1,1,1} with the same sum, so (2,1,1,1) is not counted under a(5).
The a(1) = 1 through a(8) = 15 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (32)     (33)      (43)       (44)
             (111)  (31)    (41)     (42)      (52)       (53)
                    (211)   (221)    (51)      (61)       (62)
                    (1111)  (311)    (222)     (322)      (71)
                            (11111)  (321)     (331)      (332)
                                     (411)     (421)      (422)
                                     (3111)    (511)      (431)
                                     (111111)  (2221)     (521)
                                               (4111)     (611)
                                               (1111111)  (2222)
                                                          (3311)
                                                          (5111)
                                                          (41111)
                                                          (11111111)
The 10 non-knapsack partitions counted under a(12):
  (7,6,1)
  (7,5,2)
  (7,4,3)
  (7,5,1,1)
  (7,4,2,1)
  (7,3,3,1)
  (7,3,2,2)
  (7,4,1,1,1)
  (7,2,2,2,1)
  (7,1,1,1,1,1,1,1)

Dominates A108917.

Cf. A002033, A055212, A143823, A196723, A276024, A299702, A325856, A325862, A325864, A325865, A325866, A325867, A325877.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@Plus@@@Union[Subsets[#,{2,Length[#]}]]&]],{n,0,15}]

A325991 Heinz numbers of integer partitions such that not every orderless pair of distinct parts has a different sum.

Original entry on oeis.org

210, 420, 462, 630, 840, 858, 910, 924, 1050, 1155, 1260, 1326, 1386, 1470, 1680, 1716, 1820, 1848, 1870, 1890, 1938, 2100, 2145, 2310, 2470, 2520, 2574, 2622, 2652, 2730, 2772, 2926, 2940, 3150, 3234, 3315, 3360, 3432, 3465, 3570, 3640, 3696, 3740, 3780, 3876

Offset: 1

Gus Wiseman, Jun 02 2019

nonn

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

			The sequence of terms together with their prime indices begins:
   210: {1,2,3,4}
   420: {1,1,2,3,4}
   462: {1,2,4,5}
   630: {1,2,2,3,4}
   840: {1,1,1,2,3,4}
   858: {1,2,5,6}
   910: {1,3,4,6}
   924: {1,1,2,4,5}
  1050: {1,2,3,3,4}
  1155: {2,3,4,5}
  1260: {1,1,2,2,3,4}
  1326: {1,2,6,7}
  1386: {1,2,2,4,5}
  1470: {1,2,3,4,4}
  1680: {1,1,1,1,2,3,4}
  1716: {1,1,2,5,6}
  1820: {1,1,3,4,6}
  1848: {1,1,1,2,4,5}
  1870: {1,3,5,7}
  1890: {1,2,2,2,3,4}

The subset case is A196723.
The maximal case is A325878.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A056239, A103300, A108917, A112798, A143823, A196724, A325853, A325855, A325858, A325859, A325862, A325992, A325993, A325994.

Select[Range[1000],!UnsameQ@@Plus@@@Subsets[PrimePi/@First/@FactorInteger[#],{2}]&]

A325993 Heinz numbers of integer partitions such that not every orderless pair of distinct parts has a different product.

Original entry on oeis.org

390, 780, 798, 1170, 1365, 1560, 1596, 1914, 1950, 2340, 2394, 2590, 2730, 2886, 3120, 3192, 3510, 3828, 3900, 3990, 4095, 4290, 4386, 4485, 4680, 4788, 5070, 5170, 5180, 5460, 5586, 5742, 5772, 5850, 6042, 6240, 6384, 6630, 6699, 6825, 7020, 7182, 7410, 7656

Offset: 1

Gus Wiseman, Jun 02 2019

nonn

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

			The sequence of terms together with their prime indices begins:
   390: {1,2,3,6}
   780: {1,1,2,3,6}
   798: {1,2,4,8}
  1170: {1,2,2,3,6}
  1365: {2,3,4,6}
  1560: {1,1,1,2,3,6}
  1596: {1,1,2,4,8}
  1914: {1,2,5,10}
  1950: {1,2,3,3,6}
  2340: {1,1,2,2,3,6}
  2394: {1,2,2,4,8}
  2590: {1,3,4,12}
  2730: {1,2,3,4,6}
  2886: {1,2,6,12}
  3120: {1,1,1,1,2,3,6}
  3192: {1,1,1,2,4,8}
  3510: {1,2,2,2,3,6}
  3828: {1,1,2,5,10}
  3900: {1,1,2,3,3,6}
  3990: {1,2,3,4,8}

The subset case is A196724.
The maximal case is A325859.
The integer partition case is A325856.
The strict integer partition case is A325855.
Heinz numbers of the counterexamples are given by A325993.
Cf. A002033, A056239, A108917, A112798, A143823, A292886, A325858, A325877, A325991, A325992, A325994.

Select[Range[1000],!UnsameQ@@Times@@@Subsets[PrimePi/@First/@FactorInteger[#],{2}]&]

A325866 Number of subsets of {1..n} containing n such that every subset has a different sum.

Original entry on oeis.org

1, 2, 3, 6, 9, 14, 20, 35, 44, 76, 96, 139, 179, 257, 312, 483, 561, 793, 970, 1459, 1535, 2307, 2619, 3503, 4130, 5478, 5973, 8165, 9081, 11666, 13176, 17738, 18440, 24778, 26873, 35187, 38070, 49978, 51776, 72457, 74207, 92512, 102210, 135571, 136786, 179604

Offset: 1

Gus Wiseman, Jun 01 2019

nonn

These are strict knapsack partitions (A275972) organized by maximum rather than sum.

			The a(1) = 1 through a(6) = 14 subsets:
  {1}  {2}    {3}    {4}      {5}      {6}
       {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
              {2,3}  {2,4}    {2,5}    {2,6}
                     {3,4}    {3,5}    {3,6}
                     {1,2,4}  {4,5}    {4,6}
                     {2,3,4}  {1,2,5}  {5,6}
                              {1,3,5}  {1,2,6}
                              {2,4,5}  {1,3,6}
                              {3,4,5}  {1,4,6}
                                       {2,3,6}
                                       {2,5,6}
                                       {3,4,6}
                                       {3,5,6}
                                       {4,5,6}

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..150

Cf. A108917, A143823, A143824, A196723, A275972.

Cf. A325860, A325864, A325865, A325867, A325877, A325878, A325880.

Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&UnsameQ@@Plus@@@Subsets[#]&]],{n,10}]

a(18)-a(46) from Alois P. Heinz, Jun 03 2019

A364465 Number of subsets of {1..n} with all different first differences of elements.

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 36, 61, 99, 156, 240, 381, 587, 894, 1334, 1967, 2951, 4370, 6406, 9293, 13357, 18976, 27346, 39013, 55437, 78154, 109632, 152415, 210801, 293502, 406664, 561693, 772463, 1058108, 1441796, 1956293, 2639215, 3579542, 4835842, 6523207

Offset: 0

Gus Wiseman, Jul 30 2023

nonn

			The a(0) = 1 through a(4) = 13 subsets:
  {}  {}   {}     {}     {}
      {1}  {1}    {1}    {1}
           {2}    {2}    {2}
           {1,2}  {3}    {3}
                  {1,2}  {4}
                  {1,3}  {1,2}
                  {2,3}  {1,3}
                         {1,4}
                         {2,3}
                         {2,4}
                         {3,4}
                         {1,2,4}
                         {1,3,4}

Rémy Sigrist, C++ program

For all differences of pairs of elements we have A196723
For partitions instead of subsets we have A325325, strict A320347.
For subset-sums we have A325864, for partitions A108917, A275972.
A007318 counts subsets by length.
A053632 counts subsets by sum.
A363260 counts partitions disjoint from differences, complement A364467.
A364463 counts subsets disjoint from differences, complement A364466.
Cf. A000009, A008289, A011782, A236912, A320348, A325857, A325877, A325878, A326083, A364345, A364346.

Table[Length[Select[Subsets[Range[n]],UnsameQ@@Differences[#]&]],{n,0,10}]

More terms from Rémy Sigrist, Aug 06 2023

A364613 a(n) = number of partitions of n whose sum multiset is free of duplicates; see Comments.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 8, 10, 12, 15, 18, 20, 26, 29, 36, 38, 50, 53, 67, 69, 89, 95, 115, 122, 151, 161, 195, 201, 247, 266, 312, 330, 386, 419, 487, 520, 600, 641, 742, 793, 901, 979, 1088, 1186, 1331, 1454, 1605, 1730, 1925, 2102, 2311, 2525, 2741, 3001

Offset: 0

Clark Kimberling, Sep 17 2023

nonn

If M is a multiset of real numbers, then the sum multiset of M consists of the sums of pairs of distinct numbers in M. For example, the sum multiset of (1,2,4,5) is {3,5,6,6,7,9}.

			The partitions of 8 are [8], [7,1], [6,2], [6,1,1], [5,3], [5,2,1], [5,1,1,1], [4,4], [4,3,1], [4,2,2], [4,2,1,1], [4,1,1,1,1], [3,3,2], [3,3,1,1], [3,2,2,1], [3,2,1,1,1], [3,1,1,1,1,1], [2,2,2,2], [2,2,2,1,1], [2,2,1,1,1,1], [2,1,1,1,1,1,1], [1,1,1,1,1,1,1,1]. The 7 partitions whose sum multiset is duplicate-free are [8], [7,1], [6,2], [5,3], [5,2,1], [4,4], [4,3,1].

Cf. A000041, A236912, A325877, A363994.

s[n_, k_] := s[n, k] = Subsets[IntegerPartitions[n][[k]], {2}];
g[n_, k_] := g[n, k] = DuplicateFreeQ[Map[Total, s[n, k]]];
t[n_] := Table[g[n, k], {k, 1, PartitionsP[n]}];
a[n_] := Count[t[n], True]
Table[a[n], {n, 1, 40}]

a(n) = A325877(n) - (1 - n mod 2) for n > 0. - Andrew Howroyd, Sep 17 2023

More terms from Alois P. Heinz, Sep 17 2023

cp's OEIS Frontend

A325865 Number of maximal subsets of {1..n} of which every subset has a different sum.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A326016 Number of knapsack partitions of n such that no addition of one part up to the maximum is knapsack.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326015 Number of strict knapsack partitions of n such that no superset with the same maximum is knapsack.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325863 Number of integer partitions of n such that every distinct non-singleton submultiset has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325991 Heinz numbers of integer partitions such that not every orderless pair of distinct parts has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325993 Heinz numbers of integer partitions such that not every orderless pair of distinct parts has a different product.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325866 Number of subsets of {1..n} containing n such that every subset has a different sum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A364465 Number of subsets of {1..n} with all different first differences of elements.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A364613 a(n) = number of partitions of n whose sum multiset is free of duplicates; see Comments.