A088808 -id:A088808 - cp's OEIS frontend

A088809 Number of subsets of {1, ..., n} that are not sum-free.

0, 0, 0, 1, 3, 10, 27, 67, 154, 350, 763, 1638, 3450, 7191, 14831, 30398, 61891, 125557, 253841, 511818, 1029863, 2069341, 4153060, 8327646, 16687483, 33422562, 66916342, 133936603, 268026776, 536277032, 1072886163, 2146245056, 4293187682, 8587371116

Offset: 0

Reinhard Zumkeller, Oct 19 2003

nonn

a(n) = 2^n - A085489(n); a non-sum-free subset contains at least one subset {u,v, w} with w=u+v.

A variation of binary sum-full sets where parts cannot be re-used, this sequence counts subsets of {1..n} with an element equal to the sum of two distinct others. The complement is counted by A085489. The non-binary version is A364534. For re-usable parts we have A093971. - Gus Wiseman, Aug 10 2023

			From _Gus Wiseman_, Aug 10 2023: (Start)
The set S = {1,3,6,8} has pair-sums {4,7,9,11,14}, which are all missing from S, so it is not counted under a(8).
The set {1,4,6,7} has pair-sum 1 + 6 = 7, so is counted under a(7).
The a(1) = 0 through a(5) = 10 sets:
  .  .  {1,2,3}  {1,2,3}    {1,2,3}
                 {1,3,4}    {1,3,4}
                 {1,2,3,4}  {1,4,5}
                            {2,3,5}
                            {1,2,3,4}
                            {1,2,3,5}
                            {1,2,4,5}
                            {1,3,4,5}
                            {2,3,4,5}
                            {1,2,3,4,5}
(End)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..75
Eric Weisstein's World of Mathematics, Sum-Free Set
Reinhard Zumkeller, Illustration of initial terms

The complement is counted by A085489, differences A364755.
With re-usable parts we have A093971, for partitions A363225.
The complement for partitions is A236912:
  non-binary A237667,
  ranks A364461,
  strict A364533.
The version for partitions is A237113:
  non-binary A237668,
  ranks A364462,
  strict A364670.
The non-binary version is A364534, complement A151897.
First differences are A364756.
Cf. A000079, A007865, A050291, A051026, A103580, A288728, A326020, A326080, A326083, A364272, A364349.

Table[Length[Select[Subsets[Range[n]],Intersection[#,Total/@Subsets[#,{2}]]!={}&]],{n,0,10}] (* Gus Wiseman, Aug 10 2023 *)

Terms a(32) and beyond from Fausto A. C. Cariboni, Sep 28 2020

A050291 Number of double-free subsets of {1, 2, ..., n}.

Original entry on oeis.org

1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 288, 576, 960, 1920, 2880, 5760, 9360, 18720, 28080, 56160, 93600, 187200, 280800, 561600, 898560, 1797120, 2695680, 5391360, 8985600, 17971200, 26956800, 53913600, 87091200, 174182400, 261273600, 522547200, 870912000

Offset: 0

Eric W. Weisstein

A set is double-free if it does not contain both x and 2x.

So these are equally "half-free" subsets. - Gus Wiseman, Jul 08 2019

			From _Gus Wiseman_, Jul 08 2019: (Start)
The a(0) = 1 through a(5) = 20 double-free subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {1,3}  {4}      {4}
                {2,3}  {1,3}    {5}
                       {1,4}    {1,3}
                       {2,3}    {1,4}
                       {3,4}    {1,5}
                       {1,3,4}  {2,3}
                                {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {1,3,4}
                                {1,3,5}
                                {1,4,5}
                                {2,3,5}
                                {3,4,5}
                                {1,3,4,5}
(End)

Wang, E. T. H. ``On Double-Free Sets of Integers.'' Ars Combin. 28, 97-100, 1989.

Alois P. Heinz, Table of n, a(n) for n = 0..4030 (terms n = 1..400 from T. D. Noe)
Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
Eric Weisstein's World of Mathematics, Double-Free Set.

Cf. A000045, A007814, A050292-A050296.

Cf. A007865, A103580, A120641, A308546, A320340, A323092, A326083, A326115.

a:= proc(n) option remember; `if`(n=0, 1, (F-> (p-> a(n-1)*F(p+3)
      /F(p+2))(padic[ordp](n, 2)))(j-> (<<0|1>, <1|1>>^j)[1, 2]))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 16 2019

a[n_] := a[n] = (b = IntegerExponent[2n, 2]; a[n-1]*Fibonacci[b+2]/Fibonacci[b+1]); a[1]=2; Table[a[n], {n, 1, 34}] (* Jean-François Alcover, Oct 10 2012, from first formula *)
Table[Length[Select[Subsets[Range[n]],Intersection[#,#/2]=={}&]],{n,0,10}] (* Gus Wiseman, Jul 08 2019 *)

first(n)=my(v=vector(n)); v[1]=2; for(k=2,n, v[k]=v[k-1]*fibonacci(valuation(k,2)+3)/fibonacci(valuation(k,2)+2)); v \\ Charles R Greathouse IV, Feb 07 2017

a(n) = a(n-1)*Fibonacci(b(2n)+2)/Fibonacci(b(2n)+1), Fibonacci = A000045, b = A007814.

a(n) = 2^n - A088808(n). - Reinhard Zumkeller, Oct 19 2003

Extended with formula by Christian G. Bower, Sep 15 1999

a(0)=1 prepended by Alois P. Heinz, Jan 16 2019

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

A364467 Number of integer partitions of n where some part is the difference of two consecutive parts.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 4, 5, 9, 13, 21, 28, 42, 55, 78, 106, 144, 187, 255, 325, 429, 554, 717, 906, 1165, 1460, 1853, 2308, 2899, 3582, 4468, 5489, 6779, 8291, 10173, 12363, 15079, 18247, 22124, 26645, 32147, 38555, 46285, 55310, 66093, 78684, 93674, 111104

Offset: 0

Gus Wiseman, Jul 31 2023

nonn

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

			The a(3) = 1 through a(9) = 13 partitions:
  (21)  (211)  (221)   (42)     (421)     (422)      (63)
               (2111)  (321)    (2221)    (431)      (621)
                       (2211)   (3211)    (521)      (3321)
                       (21111)  (22111)   (3221)     (4221)
                                (211111)  (4211)     (4311)
                                          (22211)    (5211)
                                          (32111)    (22221)
                                          (221111)   (32211)
                                          (2111111)  (42111)
                                                     (222111)
                                                     (321111)
                                                     (2211111)
                                                     (21111111)

For all differences of pairs parts we have A363225, complement A364345.
The complement is counted by A363260.
For subsets of {1..n} we have A364466, complement A364463.
The strict case is A364536, complement A364464.
These partitions have ranks A364537.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A050291 counts double-free subsets, complement A088808.
A323092 counts double-free partitions, ranks A320340.
A325325 counts partitions with distinct first differences.
Cf. A002865, A025065, A093971, A108917, A196723, A229816, A236912, A237113, A237667, A320347, A326083.

Table[Length[Select[IntegerPartitions[n],Intersection[#,-Differences[#]]!={}&]],{n,0,30}]

from collections import Counter
from sympy.utilities.iterables import partitions
def A364467(n): return sum(1 for s,p in map(lambda x: (x[0],tuple(sorted(Counter(x[1]).elements()))), partitions(n,size=True)) if not set(p).isdisjoint({p[i+1]-p[i] for i in range(s-1)})) # Chai Wah Wu, Sep 26 2023

A364537 Heinz numbers of integer partitions where some part is the difference of two consecutive parts.

Original entry on oeis.org

6, 12, 18, 21, 24, 30, 36, 42, 48, 54, 60, 63, 65, 66, 70, 72, 78, 84, 90, 96, 102, 108, 114, 120, 126, 130, 132, 133, 138, 140, 144, 147, 150, 154, 156, 162, 165, 168, 174, 180, 186, 189, 192, 195, 198, 204, 210, 216, 222, 228, 231, 234, 240, 246, 252, 258

Offset: 1

Gus Wiseman, Aug 02 2023

nonn

In other words, partitions whose parts are not disjoint from their first differences.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The partition {3,4,5,7} with Heinz number 6545 has first differences (1,1,2) so is not in the sequence.
The terms together with their prime indices begin:
   6: {1,2}
  12: {1,1,2}
  18: {1,2,2}
  21: {2,4}
  24: {1,1,1,2}
  30: {1,2,3}
  36: {1,1,2,2}
  42: {1,2,4}
  48: {1,1,1,1,2}
  54: {1,2,2,2}
  60: {1,1,2,3}
  63: {2,2,4}
  65: {3,6}
  66: {1,2,5}
  70: {1,3,4}
  72: {1,1,1,2,2}
  78: {1,2,6}
  84: {1,1,2,4}
  90: {1,2,2,3}
  96: {1,1,1,1,1,2}

For all differences of pairs the complement is A364347, counted by A364345.
For all differences of pairs we have A364348, counted by A363225.
Subsets of {1..n} of this type are counted by A364466, complement A364463.
These partitions are counted by A364467, complement A363260.
The strict case is A364536, complement A364464.
A050291 counts double-free subsets, complement A088808.
A323092 counts double-free partitions, ranks A320340.
A325325 counts partitions with distinct first differences.
Cf. A002865, A025065, A093971, A108917, A196723, A229816, A236912, A237113, A237667, A320347, A326083.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Intersection[prix[#],Differences[prix[#]]]!={}&]

A088812 Number of subsets of {1, ..., n} that are neither double-free nor sum-free.

Original entry on oeis.org

0, 0, 0, 1, 2, 6, 21, 49, 119, 266, 626, 1315, 2859, 5878, 12798, 26038, 54485, 109976, 230159, 462634, 945846, 1897597, 3893242, 7798862, 15834340, 31695551, 64315161, 128693477, 259241944, 518614045, 1046344906, 2092965726, 4206946359, 8414499960

Offset: 0

Reinhard Zumkeller, Oct 19 2003

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..75
Eric Weisstein's World of Mathematics, Double-Free Set
Eric Weisstein's World of Mathematics, Sum-Free Set
Reinhard Zumkeller, Illustration of initial terms

a(n) = 2^n - A088813(n) = A088808(n)-A088811(n) = A088809(n)-A088810(n).

Terms a(28) and beyond from Fausto A. C. Cariboni, Sep 29 2020

A088810 Number of subsets of {1, ..., n} that are double-free but not sum-free.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 6, 18, 35, 84, 137, 323, 591, 1313, 2033, 4360, 7406, 15581, 23682, 49184, 84017, 171744, 259818, 528784, 853143, 1727011, 2601181, 5243126, 8784832, 17662987, 26541257, 53279330, 86241323, 172871156, 259534578, 519917139

Offset: 0

Reinhard Zumkeller, Oct 19 2003

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..88
Eric Weisstein's World of Mathematics, Double-Free Set
Eric Weisstein's World of Mathematics, Sum-Free Set
Reinhard Zumkeller, Illustration of initial terms

a(n) = A050291(n) - A007865(n) = A088809(n) - A088812(n).

Terms a(28) and beyond from Fausto A. C. Cariboni, Sep 27 2020

A088811 Number of subsets of {1, ..., n} that are sum-free but not double-free.

Original entry on oeis.org

0, 0, 1, 1, 4, 6, 13, 19, 41, 54, 110, 157, 277, 394, 706, 970, 1691, 2376, 3905, 5494, 9130, 12355, 20262, 28146, 44316, 61761, 98023, 132891, 207912, 285667, 440118, 604322, 929737, 1252232, 1921062, 2625852, 3933025, 5351483, 8085728, 10856110

Offset: 0

Reinhard Zumkeller, Oct 19 2003

nonn

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..75
Eric Weisstein's World of Mathematics, Double-Free Set
Eric Weisstein's World of Mathematics, Sum-Free Set
Reinhard Zumkeller, Illustration of initial terms

a(n) = A088808(n) - A088812(n) = A085489(n) - A007865(n).

Terms a(28) and beyond from Fausto A. C. Cariboni, Sep 28 2020

cp's OEIS Frontend

A088809 Number of subsets of {1, ..., n} that are not sum-free.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A050291 Number of double-free subsets of {1, 2, ..., n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A364467 Number of integer partitions of n where some part is the difference of two consecutive parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

A364537 Heinz numbers of integer partitions where some part is the difference of two consecutive parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A088812 Number of subsets of {1, ..., n} that are neither double-free nor sum-free.

Views

Author

Keywords

Links

Formula

Extensions

A088810 Number of subsets of {1, ..., n} that are double-free but not sum-free.

Views

Author

Keywords

Links

Formula

Extensions

A088811 Number of subsets of {1, ..., n} that are sum-free but not double-free.

Views

Author

Keywords

Links

Formula

Extensions