A325877 -id:A325877 - 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}]

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

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 36, 56, 91, 135, 211, 307, 446, 625, 882, 1194, 1677, 2238, 3031, 4001, 5460, 6995, 9302, 11921, 15424, 19554, 25032, 31005, 39170, 48251, 59917, 73093, 90831, 109271, 134049, 160922, 196109, 234179, 284157, 335933, 408390, 482597, 575109

Offset: 0

Gus Wiseman, Jun 01 2019

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}
                         {2,3,4}

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..150 (terms 0..60 from Giovanni Resta)

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

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

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

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

A325878 Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.

Original entry on oeis.org

1, 1, 1, 1, 4, 5, 8, 22, 40, 56, 78, 124, 222, 390, 616, 892, 1220, 1620, 2182, 3042, 4392, 6364, 9054, 12608, 16980, 22244, 28482, 36208, 45864, 58692, 75804, 98440, 128694, 168250, 218558, 281210, 357594, 449402, 560034, 693332, 853546, 1050118, 1293458, 1596144, 1975394

Offset: 0

Gus Wiseman, Jun 02 2019

nonn

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

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

The subset case is A196723.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A108917, A143823, A143824, A276024.
Cf. A325858, A325859, A325864, A325865, A325867, A325879, A325880, A382398.

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

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

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

A364466 Number of subsets of {1..n} where some element is a difference of two consecutive elements.

Original entry on oeis.org

0, 0, 1, 2, 6, 14, 34, 74, 164, 345, 734, 1523, 3161, 6488, 13302, 27104, 55150, 111823, 226443, 457586, 923721, 1862183, 3751130, 7549354, 15184291, 30521675, 61322711, 123151315, 247230601, 496158486, 995447739, 1996668494, 4004044396, 8027966324, 16092990132, 32255168125

Offset: 0

Gus Wiseman, Jul 31 2023

nonn

In other words, the elements are not disjoint from their own first differences.

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

For differences of all pairs we have A093971, complement A196723.
For partitions we have A363260, complement A364467.
The complement is counted by A364463.
For subset-sums instead of differences we have A364534, complement A325864.
For strict partitions we have A364536, complement A364464.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A050291 counts double-free subsets, complement A088808.
A108917 counts knapsack partitions, strict A275972.
A325325 counts partitions with all distinct differences, strict A320347.
Cf. A011782, A212986, A237113, A325877, A325878, A326083, A363225.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Differences[#]]!={}&]],{n,0,10}]

from itertools import combinations
def A364466(n): return sum(1 for l in range(n+1) for c in combinations(range(1,n+1),l) if not set(c).isdisjoint({c[i+1]-c[i] for i in range(l-1)})) # Chai Wah Wu, Sep 26 2023

a(n) = 2^n - A364463(n). - Chai Wah Wu, Sep 26 2023

a(21)-a(32) from Chai Wah Wu, Sep 26 2023

a(33)-a(35) from Chai Wah Wu, Sep 27 2023

A325854 Number of strict integer partitions of n such that every pair of distinct parts has a different quotient.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 4, 6, 8, 9, 12, 13, 16, 20, 23, 30, 33, 41, 47, 52, 61, 75, 90, 98, 116, 132, 151, 173, 206, 226, 263, 297, 337, 387, 427, 488, 555, 623, 697, 782, 886, 984, 1108, 1240, 1374, 1545, 1726, 1910, 2120, 2358, 2614, 2903, 3218, 3567, 3933

Offset: 0

Gus Wiseman, May 31 2019

nonn

Also the number of strict integer partitions of n such that every pair of (not necessarily distinct) parts has a different product.

			The a(1) = 1 through a(10) = 9 partitions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)    (7)   (8)    (9)    (A)
            (21)  (31)  (32)  (42)   (43)  (53)   (54)   (64)
                        (41)  (51)   (52)  (62)   (63)   (73)
                              (321)  (61)  (71)   (72)   (82)
                                           (431)  (81)   (91)
                                           (521)  (432)  (532)
                                                  (531)  (541)
                                                  (621)  (631)
                                                         (721)
The two strict partitions of 13 such that not every pair of distinct parts has a different quotient are (9,3,1) and (6,4,2,1).

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

The subset case is A325860.
The maximal case is A325861.
The integer partition case is A325853.
The strict integer partition case is A325854.
Heinz numbers of the counterexamples are given by A325994.
Cf. A108917, A143823, A196724, A275972, A325768, A325855, A325858, A325868, A325869, A325876, A325877.

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

A325856 Number of integer partitions of n such that every pair of distinct parts has a different product.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 76, 100, 133, 171, 225, 287, 369, 467, 592, 740, 931, 1155, 1435, 1767, 2178, 2661, 3254, 3953, 4798, 5793, 6991, 8390, 10069, 12022, 14346, 17054, 20255, 23960, 28334, 33390, 39308, 46148, 54116, 63295, 73967, 86224

Offset: 0

Gus Wiseman, May 31 2019

nonn

			The five partitions of 15 not satisfying the condition are:
  (8,4,2,1)
  (6,4,3,2)
  (6,3,3,2,1)
  (6,3,2,2,1,1)
  (6,3,2,1,1,1,1)

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

The subset case is A196724.
The maximal case is A325859.
The integer partition case is A325856.
The strict integer partition case is A325855.
Cf. A002033, A108917, A143823, A325853, A325854, A325857, A325858, A325877.

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

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

A325855 Number of strict integer partitions of n such that every pair of distinct parts has a different product.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 14, 18, 22, 25, 31, 37, 44, 53, 59, 69, 83, 100, 111, 129, 152, 173, 198, 232, 260, 302, 342, 386, 448, 498, 565, 646, 728, 819, 918, 1039, 1164, 1310, 1462, 1631, 1830, 2053, 2282, 2532, 2825, 3136, 3482, 3869, 4300, 4744

Offset: 0

Gus Wiseman, May 31 2019

nonn

			The a(1) = 1 through a(10) = 10 partitions (A = 10):
  (1)  (2)  (3)   (4)   (5)   (6)    (7)    (8)    (9)    (A)
            (21)  (31)  (32)  (42)   (43)   (53)   (54)   (64)
                        (41)  (51)   (52)   (62)   (63)   (73)
                              (321)  (61)   (71)   (72)   (82)
                                     (421)  (431)  (81)   (91)
                                            (521)  (432)  (532)
                                                   (531)  (541)
                                                   (621)  (631)
                                                          (721)
                                                          (4321)

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

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, A108917, A143823, A275972, A325854, A325858, A325876, A325877.

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

A325857 Number of integer partitions of n such that every orderless pair of distinct parts has a different sum.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 55, 74, 97, 125, 165, 209, 269, 335, 428, 527, 664, 804, 1005, 1210, 1496, 1780, 2186, 2586, 3148, 3698, 4473, 5226, 6279, 7290, 8706, 10067, 11950, 13744, 16242, 18605, 21864, 24942, 29184, 33188, 38651, 43782, 50791, 57402, 66300, 74683, 86026, 96658

Offset: 0

Gus Wiseman, May 31 2019

nonn

			The A000041(14) - a(14) = 10 partitions of 14 not satisfying the condition are:
  (6,5,2,1)
  (6,4,3,1)
  (5,4,3,2)
  (5,4,2,2,1)
  (4,4,3,2,1)
  (5,4,2,1,1,1)
  (4,3,3,2,1,1)
  (4,3,2,2,2,1)
  (4,3,2,2,1,1,1)
  (4,3,2,1,1,1,1,1)

Max Alekseyev, Table of n, a(n) for n = 0..80

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, A103300, A108917, A143823, A196724, A325853, A325855, A325858, A325859, A325862.

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

Terms a(31) onward from Max Alekseyev, Sep 23 2023

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A325878 Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A364466 Number of subsets of {1..n} where some element is a difference of two consecutive elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A325854 Number of strict integer partitions of n such that every pair of distinct parts has a different quotient.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325856 Number of integer partitions of n such that every pair of distinct parts has a different product.

Views

Author

Keywords

Examples

Links

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