A325863 -id:A325863 - cp's OEIS frontend

A196723 Number of subsets of {1..n} (including empty set) such that the pairwise sums of distinct elements are all distinct.

1, 2, 4, 8, 15, 28, 50, 86, 143, 236, 376, 594, 913, 1380, 2048, 3016, 4367, 6302, 8974, 12670, 17685, 24580, 33738, 46072, 62367, 83990, 112342, 149734, 198153, 261562, 343210, 448694, 583445, 756846, 976086, 1255658, 1607831, 2053186, 2610560, 3312040, 4183689

Offset: 0

Alois P. Heinz, Oct 06 2011

nonn

The number of subsets of {1..n} such that every orderless pair of (not necessarily distinct) elements has a different sum is A143823(n).

			a(4) = 15: {}, {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..110

Cf. A143823, A196719, A196720, A196721, A196722, A196724.
The subset case is A196723 (this sequence).
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. A108917, A325858, A325862, A325863, A325864.

b:= proc(n, s) local sn, m;
      m:= nops(s);
      sn:= [s[], n];
      `if`(n<1, 1, b(n-1, s) +`if`(m*(m+1)/2 = nops(({seq(seq(
       sn[i]+sn[j], j=i+1..m+1), i=1..m)})), b(n-1, sn), 0))
    end:
a:= proc(n) option remember;
      b(n-1, [n]) +`if`(n=0, 0, a(n-1))
    end:
seq(a(n), n=0..20);

b[n_, s_] := b[n, s] = Module[{sn, m}, m = Length[s]; sn = Append[s, n]; If[n<1, 1, b[n-1, s] + If[m*(m+1)/2 == Length[ Union[ Flatten[ Table[ sn[[i]] + sn[[j]], {i, 1, m}, {j, i+1, m+1}]]]], b[n-1, sn], 0]]];
a[n_] := a[n] = b[n-1, {n}] + If[n == 0, 0, a[n-1]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jan 31 2017, translated from Maple *)
Table[Length[Select[Subsets[Range[n]],UnsameQ@@Plus@@@Subsets[#,{2}]&]],{n,0,10}] (* Gus Wiseman, Jun 03 2019 *)

Edited by Gus Wiseman, Jun 03 2019

A325862 Number of integer partitions of n such that every set of distinct parts has a different sum.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 10, 14, 19, 26, 34, 46, 58, 77, 93, 122, 146, 188, 217, 282, 327, 410, 470, 596, 673, 848, 947, 1178, 1325, 1629, 1798, 2213, 2444, 2962, 3247, 3935, 4292, 5149, 5579, 6674, 7247, 8590, 9221, 10964, 11804, 13870, 14843, 17480, 18675, 21866

Offset: 0

Gus Wiseman, May 31 2019

nonn

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 a(1) = 1 through a(7) = 14 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (21)   (22)    (32)     (33)      (43)
             (111)  (31)    (41)     (42)      (52)
                    (211)   (221)    (51)      (61)
                    (1111)  (311)    (222)     (322)
                            (2111)   (411)     (331)
                            (11111)  (2211)    (421)
                                     (3111)    (511)
                                     (21111)   (2221)
                                     (111111)  (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)
The three non-knapsack partitions counted under a(6) are:
  (2,2,1,1)
  (3,1,1,1)
  (2,1,1,1,1)

Dominates A108917.

Cf. A002033, A034444, A196723, A275972, A276024, A299702, A325592, A325856, A325863, A325864, A325865, A325877.

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

A326017 Triangle read by rows where T(n,k) is the number of knapsack partitions of n with maximum k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 1, 1, 2, 3, 2, 1, 1, 0, 1, 1, 2, 1, 3, 2, 1, 1, 0, 1, 1, 2, 2, 4, 3, 2, 1, 1, 0, 1, 1, 2, 3, 1, 4, 3, 2, 1, 1, 0, 1, 1, 3, 3, 4, 6, 4, 3, 2, 1, 1, 0, 1, 1, 1, 1, 3, 1, 6, 4

Offset: 0

Gus Wiseman, Jun 03 2019

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

			Triangle begins:
  1
  0  1
  0  1  1
  0  1  1  1
  0  1  1  1  1
  0  1  1  2  1  1
  0  1  1  1  2  1  1
  0  1  1  2  3  2  1  1
  0  1  1  2  1  3  2  1  1
  0  1  1  2  2  4  3  2  1  1
  0  1  1  2  3  1  4  3  2  1  1
  0  1  1  3  3  4  6  4  3  2  1  1
  0  1  1  1  1  3  1  6  4  3  2  1  1
  0  1  1  3  3  5  4  7  6  4  3  2  1  1
  0  1  1  2  3  5  4  1  7  6  4  3  2  1  1
  0  1  1  2  3  4  6  6 11  7  6  4  3  2  1  1
Row n = 9 counts the following partitions:
  (111111111)  (22221)  (333)   (432)  (54)     (63)    (72)   (81)  (9)
                        (3222)  (441)  (522)    (621)   (711)
                                       (531)    (6111)
                                       (51111)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..10010
Fausto A. C. Cariboni, Conjectures on columns of T(n,k), Jun 05 2021.

Row sums are A108917.
Column k = 3 is A326034.
Cf. A002033, A196723, A275972, A276024.
Cf. A325592, A325857, A325862, A325863, A325864, A325877, A326016, A326018.

ks[n_]:=Select[IntegerPartitions[n],UnsameQ@@Total/@Union[Subsets[#]]&];
Table[Length[Select[ks[n],Length[#]==k==0||Max@@#==k&]],{n,0,15},{k,0,n}]

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}]

A326019 Heinz numbers of non-knapsack partitions such that every non-singleton submultiset has a different sum.

Original entry on oeis.org

12, 30, 40, 63, 70, 112, 154, 165, 198, 220, 273, 286, 325, 351, 352, 364, 442, 561, 595, 646, 714, 741, 748, 765, 832, 850, 874, 918, 931, 952, 988, 1045, 1173, 1254, 1334, 1425, 1495, 1539, 1564, 1653, 1672, 1771, 1794, 1798, 1900, 2139, 2176, 2204, 2254

Offset: 1

Gus Wiseman, Jun 03 2019

nonn

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

			The sequence of terms together with their prime indices begins:
   12: {1,1,2}
   30: {1,2,3}
   40: {1,1,1,3}
   63: {2,2,4}
   70: {1,3,4}
  112: {1,1,1,1,4}
  154: {1,4,5}
  165: {2,3,5}
  198: {1,2,2,5}
  220: {1,1,3,5}
  273: {2,4,6}
  286: {1,5,6}
  325: {3,3,6}
  351: {2,2,2,6}
  352: {1,1,1,1,1,5}
  364: {1,1,4,6}
  442: {1,6,7}
  561: {2,5,7}
  595: {3,4,7}
  646: {1,7,8}

Cf. A108917, A275972, A299702, A299729, A304793.

Cf. A325780, A325862, A325863, A326016, A326018.

hwt[n_]:=Total[Cases[FactorInteger[n],{p_,k_}:>PrimePi[p]*k]];
Select[Range[1000],!UnsameQ@@hwt/@Divisors[#]&&UnsameQ@@hwt/@Select[Divisors[#],!PrimeQ[#]&]&]

A326033 Number of knapsack partitions of n such that no addition of one part equal to an existing part 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, 1, 1, 0, 8, 0, 8, 4, 3, 0, 11, 5, 3, 4, 5, 0, 30, 2, 9, 9, 20, 3, 37, 6, 18, 16, 37, 20, 71, 12, 37, 40

Offset: 1

Gus Wiseman, Jun 03 2019

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

			The partition (10,8,6,6) is counted under a(30) because (10,10,8,6,6), (10,8,8,6,6), and (10,8,6,6,6) are not knapsack.

Cf. A002033, A108917, A275972, A276024, A299702.

Cf. A325857, A325862, A325863, A325864, A325865, A326015, A326016, 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,Union[#]}],ksQ]=={}&];
Table[Length[maxks[n]],{n,30}]

cp's OEIS Frontend

A196723 Number of subsets of {1..n} (including empty set) such that the pairwise sums of distinct elements are all distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A325862 Number of integer partitions of n such that every set of distinct parts has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326017 Triangle read by rows where T(n,k) is the number of knapsack partitions of n with maximum k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A326019 Heinz numbers of non-knapsack partitions such that every non-singleton submultiset has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326033 Number of knapsack partitions of n such that no addition of one part equal to an existing part is knapsack.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica