A363225 -id:A363225 - cp's OEIS frontend

A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.

1, 2, 4, 7, 13, 25, 47, 88, 166, 313, 589, 1109, 2089, 3934, 7408, 13951, 26273, 49477, 93175, 175468, 330442, 622289, 1171897, 2206921, 4156081, 7826746, 14739356, 27757207, 52272469, 98439697, 185381983, 349112000, 657448942, 1238110153

Offset: 0

Gus Wiseman, Nov 21 2023

			The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is counted under a(8).
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,3,4}
                         {2,3,4}

The version containing n appears to be A112575.
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400*
ranks:       A367224   A367225   A367226   A367227   A367397   A367401
A002865 counts partitions whose length is a part, complement A229816.
A364534 counts sum-full subsets.
A088809 and A093971 count subsets containing semi-sums.
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A237113, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366131, A366740.

Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#, {2}], Length[#]]&]], {n,0,10}]

from itertools import combinations
def A367400(n): return (n*(n+1)>>1)+1+sum(1 for k in range(3,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if not any({a,k-a}<=w for a in range(1,k+1>>1))) # Chai Wah Wu, Nov 21 2023

Conjectures from Chai Wah Wu, Nov 21 2023: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n > 3.
G.f.: (-x^3 + x^2 + 1)/(x^4 - 2*x^3 + x^2 - 2*x + 1). (End)

a(18)-a(33) from Chai Wah Wu, Nov 21 2023

A367401 Numbers m such that bigomega(m) is not the sum of prime indices of any semiprime divisor of m.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 34, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 64, 65, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77

Offset: 1

Gus Wiseman, Nov 21 2023

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

These are the Heinz numbers of the partitions counted by A367398.

			60 has semiprime divisor 10 with prime indices {1,3} summing to 4 = bigomega(60), so 60 is not in the sequence.
The terms together with their prime indices begin:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   6: {1,2}
   7: {4}
   8: {1,1,1}
   9: {2,2}
  10: {1,3}
  11: {5}
  13: {6}
  14: {1,4}
  15: {2,3}
  16: {1,1,1,1}
  17: {7}
  19: {8}
  20: {1,1,3}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
             sum-full  sum-free  comb-full comb-free semi-full semi-free
            -----------------------------------------------------------
partitions:  A367212   A367213   A367218   A367219   A367394   A367398
strict:      A367214   A367215   A367220   A367221   A367395   A367399
subsets:     A367216   A367217   A367222   A367223   A367396   A367400
ranks:       A367224   A367225   A367226   A367227   A367397   A367401*
A002865 counts partitions w/ length, complement A229816, ranks A325761.
A088809 and A093971 count subsets containing semi-sums.
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
A237113 counts partitions with a semi-sum of the parts, ranks A364462.
A366738 counts semi-sums of partitions, strict A366741.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
A367404 counts partitions with a semi-sum k, strict A367405.
Cf. A000700, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366740.

prix[n_]:=If[n==1,{}, Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100], FreeQ[Total/@Subsets[prix[#],{2}], PrimeOmega[#]]&]

A364671 Number of subsets of {1..n} containing all of their own first differences.

Original entry on oeis.org

1, 2, 4, 6, 10, 14, 23, 34, 58, 96, 171, 302, 565, 1041, 1969, 3719, 7105, 13544, 25999, 49852, 95949, 184658, 356129, 687068, 1327540, 2566295, 4966449, 9617306, 18640098, 36150918, 70166056, 136272548, 264844111, 515036040, 1002211421, 1951345157, 3801569113

Offset: 0

Gus Wiseman, Aug 04 2023

nonn

			The subset {1,2,4,5,10,14} has differences (1,2,1,5,4) so is counted under a(14).
The a(0) = 1 through a(5) = 14 subsets:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {2}    {2}      {2}        {2}
           {1,2}  {3}      {3}        {3}
                  {1,2}    {4}        {4}
                  {1,2,3}  {1,2}      {5}
                           {2,4}      {1,2}
                           {1,2,3}    {2,4}
                           {1,2,4}    {1,2,3}
                           {1,2,3,4}  {1,2,4}
                                      {1,2,3,4}
                                      {1,2,3,5}
                                      {1,2,4,5}
                                      {1,2,3,4,5}

Rémy Sigrist, C++ program

For differences of all strict pairs we have A054519, for partitions A007862.
For "disjoint" instead of "subset" we have A364463, partitions A363260.
For "non-disjoint" we have A364466, partitions A364467 (strict A364536).
The complement is counted by A364672, partitions A364673, A364674, A364675.
First differences of terms are A364752, complement A364753.
Cf. A151897, A196723, A237667, A237668, A325325, A326083, A363225, A364345, A364464, A364537.

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

More terms from Rémy Sigrist, Aug 06 2023

A364672 Number of subsets of {1..n} not containing all of their own first differences.

Original entry on oeis.org

0, 0, 0, 2, 6, 18, 41, 94, 198, 416, 853, 1746, 3531, 7151, 14415, 29049, 58431, 117528, 236145, 474436, 952627, 1912494, 3838175, 7701540, 15449676, 30988137, 62142415, 124600422, 249795358, 500719994, 1003575768, 2011211100, 4030123185, 8074898552, 16177657763, 32408393211, 64917907623

Offset: 0

Gus Wiseman, Aug 05 2023

nonn

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

For disjunction instead of containment we have A364463, partitions A363260.
For overlap we have A364466, partitions A364467 (strict A364536).
The complement is counted by A364671, partitions A364673, A364674, A364675.
First differences of terms are A364753, complement A364752.
Cf. A007862, A054519, A151897, A237667, A325325, A326083, A363225, A364345, A364464, A364537.

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

a(n) = 2^n - A364671(n). - Andrew Howroyd, Jan 27 2024

a(21) onwards (using A364671) added by Andrew Howroyd, Jan 27 2024

A364675 Number of integer partitions of n whose nonzero first differences are a submultiset of the parts.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 7, 7, 10, 12, 15, 15, 26, 25, 35, 45, 55, 60, 86, 94, 126, 150, 186, 216, 288, 328, 407, 493, 610, 699, 896, 1030, 1269, 1500, 1816, 2130, 2620, 3029, 3654, 4300, 5165, 5984, 7222, 8368, 9976, 11637, 13771, 15960, 18978, 21896, 25815, 29915

Offset: 0

Gus Wiseman, Aug 04 2023

nonn

Conjecture: For subsets of {1..n} instead of partitions of n we have A101925.

Conjecture: The strict version is A154402.

			The partition y = (3,2,1,1) has first differences (1,1,0), and (1,1) is a submultiset of y, so y is counted under a(7).
The a(1) = 1 through a(8) = 10 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (221)    (33)      (421)      (44)
             (111)  (211)   (2111)   (42)      (2221)     (422)
                    (1111)  (11111)  (222)     (3211)     (2222)
                                     (2211)    (22111)    (4211)
                                     (21111)   (211111)   (22211)
                                     (111111)  (1111111)  (32111)
                                                          (221111)
                                                          (2111111)
                                                          (11111111)

For subsets of {1..n} we appear to have A101925, A364671, A364672.
The strict case (no differences of 0) appears to be A154402.
Starting with the distinct parts gives A342337.
For disjoint multisets: A363260, subsets A364463, strict A364464.
For overlapping multisets: A364467, ranks A364537, strict A364536.
For subsets instead of submultisets we have A364673.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A236912 counts sum-free partitions, complement A237113.
A325325 counts partitions with distinct first differences.
Cf. A002865, A007862, A108917, A229816, A237667, A237668, A320347, A363225, A364272, A364345, A364466.

submultQ[cap_,fat_] := And@@Function[i,Count[fat,i] >= Count[cap,i]] /@ Union[List@@cap];
Table[Length[Select[IntegerPartitions[n], submultQ[Differences[Union[#]],#]&]], {n,0,30}]

A364674 Number of integer partitions of n containing all of their own nonzero first differences.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 8, 7, 11, 13, 17, 18, 32, 30, 44, 54, 70, 78, 114, 125, 171, 205, 257, 302, 408, 464, 592, 711, 892, 1042, 1330, 1543, 1925, 2279, 2787, 3291, 4061, 4727, 5753, 6792, 8197, 9583, 11593, 13505, 16198, 18965, 22548, 26290, 31340, 36363, 43046

Offset: 0

Gus Wiseman, Aug 04 2023

nonn

			The partition (10,5,3,3,2,1) has nonzero differences (5,2,1,1) so is counted under a(24).
The a(1) = 1 through a(9) = 13 partitions:
  (1) (2)  (3)   (4)    (5)     (6)      (7)       (8)        (9)
      (11) (21)  (22)   (221)   (33)     (421)     (44)       (63)
           (111) (211)  (2111)  (42)     (2221)    (422)      (333)
                 (1111) (11111) (222)    (3211)    (2222)     (3321)
                                (321)    (22111)   (3221)     (4221)
                                (2211)   (211111)  (4211)     (22221)
                                (21111)  (1111111) (22211)    (32211)
                                (111111)           (32111)    (42111)
                                                   (221111)   (222111)
                                                   (2111111)  (321111)
                                                   (11111111) (2211111)
                                                              (21111111)
                                                              (111111111)

For no differences we have A363260, subsets A364463, strict A364464.
For at least one difference we have A364467, ranks A364537, strict A364536.
For subsets instead of partitions we have A364671, complement A364672.
The strict case (no differences of 0) is counted by A364673.
For submultisets instead of subsets we have A364675.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A236912 counts sum-free partitions w/o re-used parts, complement A237113.
A325325 counts partitions with distinct first differences.
Cf. A002865, A007862, A025065, A229816, A237667, A320347, A326083, A363225, A364272, A364466.

Table[Length[Select[IntegerPartitions[n], SubsetQ[#,Differences[Union[#]]]&]],{n,0,30}]

A364752 Number of subsets of {1..n} containing n and all first differences.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 9, 11, 24, 38, 75, 131, 263, 476, 928, 1750, 3386, 6439, 12455, 23853, 46097, 88709, 171471, 330939, 640472, 1238755, 2400154, 4650857, 9022792, 17510820, 34015138, 66106492, 128571563, 250191929, 487175381, 949133736, 1850223956, 3608650389

Offset: 0

Gus Wiseman, Aug 06 2023

nonn

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

Rémy Sigrist, C++ program

Partial sums are A364671, complement A364672.
The complement is counted by A364753.
A054519 counts subsets containing differences, A326083 containing sums.
A364463 counts subsets disjoint from differences, complement A364466.
A364673 counts partitions containing differences, A364674, A364675.
Cf. A151897, A196723, A237668, A325325, A363225, A364345, A364464, A364537.

Table[If[n==0,1,Length[Select[Subsets[Range[n]], MemberQ[#,n]&&SubsetQ[#,Differences[#]]&]]],{n,0,10}]

More terms from Rémy Sigrist, Aug 06 2023

A365323 Number of integer partitions with sum < n whose distinct parts cannot be linearly combined using all positive coefficients to obtain n.

Original entry on oeis.org

0, 0, 1, 1, 4, 3, 9, 7, 15, 16, 29, 23, 47, 43, 74, 65, 114, 100, 174, 153, 257, 228, 368, 312, 530, 454, 736, 645, 1025, 902, 1402, 1184, 1909, 1626, 2618, 2184, 3412, 2895, 4551, 3887, 5966, 5055, 7796, 6509, 10244, 8462, 13060, 10881, 16834, 14021, 21471

Offset: 1

Gus Wiseman, Sep 12 2023

nonn

			The partition y = (3,3,2) has distinct parts {2,3}, and we have 9 = 3*2 + 1*3, so y is not counted under a(9).
The a(3) = 1 through a(10) = 16 partitions:
  (2)  (3)  (2)    (4)    (2)      (3)    (2)        (3)
            (3)    (5)    (3)      (5)    (4)        (4)
            (4)    (3,2)  (4)      (6)    (5)        (6)
            (2,2)         (5)      (7)    (6)        (7)
                          (6)      (3,3)  (7)        (8)
                          (2,2)    (4,3)  (8)        (9)
                          (3,3)    (5,2)  (2,2)      (3,3)
                          (4,2)           (4,2)      (4,4)
                          (2,2,2)         (4,3)      (5,2)
                                          (4,4)      (5,3)
                                          (5,3)      (5,4)
                                          (6,2)      (6,3)
                                          (2,2,2)    (7,2)
                                          (4,2,2)    (3,3,3)
                                          (2,2,2,2)  (4,3,2)
                                                     (5,2,2)

Chai Wah Wu, Table of n, a(n) for n = 1..95

Complement for subsets: A088314 or A365042, nonnegative A365073 or A365542.
For strict partitions we have A088528, nonnegative coefficients A365312.
For length-2 subsets we have A365321 (we use n instead of n-1).
For subsets we have A365322 or A365045, nonnegative coefficients A365380.
For nonnegative coefficients we have A365378, complement A365379.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A364350 counts combination-free strict partitions, non-strict A364915.
A364839 counts combination-full strict partitions, non-strict A364913.
Cf. A237668, A363225, A364272, A364345, A364914, A365320, A365382.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],combp[n,Union[#]]=={}&]],{n,10}]

from sympy.utilities.iterables import partitions
def A365323(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for k in range(1,n) for d in partitions(k) if tuple(sorted(set(d))) not in a) # Chai Wah Wu, Sep 12 2023

a(21)-a(51) from Chai Wah Wu, Sep 12 2023

A365383 Triangle read by rows where T(n,k) is the number of integer partitions of n that can be linearly combined with nonnegative coefficients to obtain k.

Original entry on oeis.org

1, 2, 1, 3, 2, 2, 5, 3, 4, 3, 7, 5, 6, 6, 6, 11, 7, 9, 8, 9, 7, 15, 11, 13, 13, 14, 13, 14, 22, 15, 19, 17, 20, 17, 20, 16, 30, 22, 26, 26, 27, 26, 28, 26, 27, 42, 30, 37, 34, 39, 33, 40, 34, 39, 34, 56, 42, 50, 49, 52, 50, 54, 51, 54, 53, 53

Offset: 0

Gus Wiseman, Sep 08 2023

Conjecture: The rows eventually become periodic with period n if extended further. For example, row n = 8 begins:
  22, 15, 19, 17, 20, 17, 20, 16,
  22, 17, 20, 17, 21, 17, 20, 17,
  22, 17, 20, 17, 21, 17, 20, 17, ...

			Triangle begins:
   1
   2   1
   3   2   2
   5   3   4   3
   7   5   6   6   6
  11   7   9   8   9   7
  15  11  13  13  14  13  14
  22  15  19  17  20  17  20  16
  30  22  26  26  27  26  28  26  27
  42  30  37  34  39  33  40  34  39  34
  56  42  50  49  52  50  54  51  54  53  53
  77  56  68  64  71  63  73  63  71  65  70  62
 101  77  91  89  95  90  97  93  97  97  98  94  99
 135 101 122 115 127 115 130 114 131 119 130 117 132 116
 176 135 159 156 165 157 170 161 167 168 166 165 172 164 166
Row n = 6 counts the following partitions:
  (6)       (51)      (51)      (51)      (51)      (51)
  (51)      (411)     (42)      (411)     (42)      (411)
  (42)      (321)     (411)     (33)      (411)     (321)
  (411)     (3111)    (321)     (321)     (321)     (3111)
  (33)      (2211)    (3111)    (3111)    (3111)    (2211)
  (321)     (21111)   (222)     (2211)    (222)     (21111)
  (3111)    (111111)  (2211)    (21111)   (2211)    (111111)
  (222)               (21111)   (111111)  (21111)
  (2211)              (111111)            (111111)
  (21111)
  (111111)

Column k = 0 is A000041, strict A000009.
The version for subsets is A365381, main diagonal A365376.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A364350 counts combination-free strict partitions, non-strict A364915.
A364839 counts combination-full strict partitions, non-strict A364913.
Cf. A088314, A088528, A237668, A363225, A364345, A365073, A365311, A365320, A365378, A365382.

combu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n],combu[k,#]!={}&]],{n,0,12},{k,0,n-1}]

cp's OEIS Frontend

A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A367401 Numbers m such that bigomega(m) is not the sum of prime indices of any semiprime divisor of m.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A364671 Number of subsets of {1..n} containing all of their own first differences.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A364672 Number of subsets of {1..n} not containing all of their own first differences.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A364675 Number of integer partitions of n whose nonzero first differences are a submultiset of the parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A364674 Number of integer partitions of n containing all of their own nonzero first differences.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A364752 Number of subsets of {1..n} containing n and all first differences.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A365323 Number of integer partitions with sum < n whose distinct parts cannot be linearly combined using all positive coefficients to obtain n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A365383 Triangle read by rows where T(n,k) is the number of integer partitions of n that can be linearly combined with nonnegative coefficients to obtain k.