A364914 -id:A364914 - cp's OEIS frontend

A366320 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.

1, 2, 2, 3, 4, 4, 3, 6, 6, 7, 8, 8, 6, 6, 9, 11, 11, 14, 14, 15, 16, 16, 12, 12, 9, 17, 17, 20, 20, 24, 27, 27, 30, 30, 31, 32, 32, 24, 24, 18, 17, 26, 31, 29, 35, 36, 43, 47, 50, 51, 56, 59, 59, 62, 62, 63

Offset: 1

Gus Wiseman, Oct 12 2023

			Triangle begins:
   1
   2  2  3
   4  4  3  6  6  7
   8  8  6  6  9 11 11 14 14 15
  16 16 12 12  9 17 17 20 20 24 27 27 30 30 31
  32 32 24 24 18 17 26 31 29 35 36 43 47 50 51 56 59 59 62 62 63
Row n = 3 counts the following subsets:
  {}     {}     {}   {}     {}     {}
  {2}    {1}    {1}  {1}    {1}    {1}
  {3}    {3}    {2}  {2}    {2}    {2}
  {2,3}  {1,3}       {3}    {3}    {3}
                     {1,2}  {1,2}  {1,2}
                     {2,3}  {1,3}  {1,3}
                                   {2,3}

Row lengths are A000217.
The diagonal T(n,n) is A365377, complement A365376.
The complement is counted by A365381.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 counts combination-free subsets, differences of A326083.
A365046 counts combination-full subsets, differences of A364914.
Cf. A007865, A085489, A093971, A103580, A151897, A326080, A364534, A365073, A365380.

Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#],k]&]],{n,8},{k,n*(n+1)/2}]

A364910 Number of integer partitions of 2n whose distinct parts sum to n.

Original entry on oeis.org

1, 1, 1, 3, 3, 4, 12, 11, 19, 23, 54, 55, 103, 115, 178, 289, 389, 507, 757, 970, 1343, 2033, 2579, 3481, 4840, 6312, 8317, 10998, 15459, 19334, 26368, 33480, 44709, 56838, 74878, 93369, 128109, 157024, 206471, 258357, 338085, 417530, 544263, 669388, 859570, 1082758, 1367068

Offset: 0

Gus Wiseman, Aug 16 2023

nonn

Also the number of ways to write n as a nonnegative linear combination of the parts of a strict integer partition of n.

			The a(0) = 1 through a(7) = 11 partitions:
  ()  (11)  (22)  (33)     (44)      (55)       (66)         (77)
                  (2211)   (3311)    (3322)     (4422)       (4433)
                  (21111)  (311111)  (4411)     (5511)       (5522)
                                     (4111111)  (33321)      (6611)
                                                (42222)      (442211)
                                                (322221)     (4222211)
                                                (332211)     (4421111)
                                                (3222111)    (42221111)
                                                (3321111)    (422111111)
                                                (32211111)   (611111111)
                                                (51111111)   (4211111111)
                                                (321111111)
The a(0) = 1 through a(7) = 11 linear combinations:
  0  1*1  1*2  1*3      1*4      1*5      1*6          1*7
               0*2+3*1  0*3+4*1  0*4+5*1  0*4+3*2      0*6+7*1
               1*2+1*1  1*3+1*1  1*3+1*2  0*5+6*1      1*4+1*3
                                 1*4+1*1  1*4+1*2      1*5+1*2
                                          1*5+1*1      1*6+1*1
                                          0*3+0*2+6*1  0*4+0*2+7*1
                                          0*3+1*2+4*1  0*4+1*2+5*1
                                          0*3+2*2+2*1  0*4+2*2+3*1
                                          0*3+3*2+0*1  0*4+3*2+1*1
                                          1*3+0*2+3*1  1*4+0*2+3*1
                                          1*3+1*2+1*1  1*4+1*2+1*1
                                          2*3+0*2+0*1

Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 91 terms from David A. Corneth)

The case with no zero coefficients is A000009.
Central diagonal of A116861.
A version based on Heinz numbers is A364906.
Using all partitions (not just strict) we get A364907.
The version for compositions is A364908, strict A364909.
Main diagonal of A364916.
Using strict partitions of any number from 1 to n gives A365002.
These partitions have ranks A365003.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A323092 counts double-free partitions, ranks A320340.
Cf. A237113, A364350, A364839, A364911, A364912, A364914.

Table[Length[Select[IntegerPartitions[2n],Total[Union[#]]==n&]],{n,0,15}]

a(n) = {my(res = 0); forpart(p = 2*n,s = Set(p); if(vecsum(s) == n, res++)); res} \\ David A. Corneth, Aug 20 2023

from sympy.utilities.iterables import partitions
def A364910(n): return sum(1 for d in partitions(n<<1,k=n) if sum(set(d))==n) # Chai Wah Wu, Sep 13 2023

a(n) = A116861(2n,n).

a(n) = A364916(n,n).

More terms from David A. Corneth, Aug 20 2023

A365043 Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.

Original entry on oeis.org

0, 0, 1, 3, 7, 12, 21, 32, 49, 70, 99, 135, 185, 245, 323, 418, 541, 688, 873, 1094, 1368, 1693, 2092, 2564, 3138, 3810, 4620, 5565, 6696, 8012, 9569, 11381, 13518, 15980, 18872, 22194, 26075, 30535, 35711, 41627, 48473, 56290, 65283, 75533, 87298, 100631, 115911, 133219

Offset: 0

Gus Wiseman, Aug 25 2023

nonn

Sets of this type may be called "positive combination-full".

Also subsets of {1..n} such that some element can be written as a (strictly) positive linear combination of the others.

			The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
The a(0) = 0 through a(5) = 12 subsets:
  .  .  {1,2}  {1,2}    {1,2}    {1,2}
               {1,3}    {1,3}    {1,3}
               {1,2,3}  {1,4}    {1,4}
                        {2,4}    {1,5}
                        {1,2,3}  {2,4}
                        {1,2,4}  {1,2,3}
                        {1,3,4}  {1,2,4}
                                 {1,2,5}
                                 {1,3,4}
                                 {1,3,5}
                                 {1,4,5}
                                 {2,3,5}

Bert Dobbelaere, Table of n, a(n) for n = 0..100
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The binary complement is A007865, first differences A288728.
The binary version is A093971, first differences A365070.
The nonnegative complement is A326083, first differences A124506.
The nonnegative version is A364914, first differences A365046.
First differences are A365042.
The complement is counted by A365044, first differences A365045.
Without re-usable parts we have A364534, first differences A365069.
A085489 and A364755 count subsets with no sum of two distinct elements.
A088809 and A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A151897, A237113, A237668, A308546, A324736, A326020, A326080, A364272.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n]]],combp[Last[#],Union[Most[#]]]!={}&]],{n,0,10}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A365043(n):
    mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
    return sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023

a(n) = 2^n - A365044(n).

a(15)-a(35) from Chai Wah Wu, Nov 20 2023

More terms from Bert Dobbelaere, Apr 28 2025

A365312 Number of strict integer partitions with sum <= n that cannot be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 2, 6, 4, 8, 7, 16, 6, 24, 17, 24, 20, 46, 22, 62, 31, 63, 57, 106, 35, 122, 90, 137, 88, 212, 74, 262, 134, 267, 206, 345, 121, 476, 294, 484, 232, 698, 242, 837, 389, 763, 571, 1185, 318, 1327, 634, 1392, 727, 1927, 640, 2056, 827, 2233, 1328

Offset: 0

Gus Wiseman, Sep 05 2023

nonn

			The strict partition (7,3,2) has 19 = 1*7 + 2*3 + 3*2 so is not counted under a(19).
The strict partition (9,6,3) cannot be linearly combined to obtain 19, so is counted under a(19).
The a(0) = 0 through a(11) = 16 strict partitions:
  .  .  .  (2)  (3)  (2)  (4)  (2)    (3)  (2)    (3)    (2)
                     (3)  (5)  (3)    (5)  (4)    (4)    (3)
                     (4)       (4)    (6)  (5)    (6)    (4)
                               (5)    (7)  (6)    (7)    (5)
                               (6)         (7)    (8)    (6)
                               (4,2)       (8)    (9)    (7)
                                           (4,2)  (6,3)  (8)
                                           (6,2)         (9)
                                                         (10)
                                                         (4,2)
                                                         (5,4)
                                                         (6,2)
                                                         (6,3)
                                                         (6,4)
                                                         (7,3)
                                                         (8,2)

The complement for positive coefficients is counted by A088314.
For positive coefficients we have A088528.
The complement is counted by A365311.
For non-strict partitions we have A365378, complement A365379.
The version for subsets is A365380, complement A365073.
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. A093971, A237113, A237668, A326080, A363225, A364272, A364534, A364914, A365043, A365314, A365320.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Join@@Array[IntegerPartitions,n], UnsameQ@@#&],combs[n,#]=={}&]],{n,0,10}]

from math import isqrt
from sympy.utilities.iterables import partitions
def A365312(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n+1) for b in partitions(m,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023

a(26)-a(58) from Chai Wah Wu, Sep 13 2023

A365311 Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 11, 12, 20, 24, 35, 38, 63, 63, 92, 112, 148, 160, 230, 244, 339, 383, 478, 533, 726, 781, 978, 1123, 1394, 1526, 1960, 2112, 2630, 2945, 3518, 3964, 4856, 5261, 6307, 7099, 8464, 9258, 11140, 12155, 14419, 16093, 18589, 20565, 24342, 26597, 30948

Offset: 0

Gus Wiseman, Sep 04 2023

nonn

			The strict partition (6,3) cannot be linearly combined to obtain 10, so is not counted under a(10).
The strict partition (4,2) has 6 = 1*4 + 1*2 so is counted under a(6), but (4,2) cannot be linearly combined to obtain 7 so is not counted under a(7).
The a(1) = 1 through a(7) = 12 strict partitions:
  (1)  (1)  (1)    (1)    (1)    (1)      (1)
       (2)  (3)    (2)    (5)    (2)      (7)
            (2,1)  (4)    (2,1)  (3)      (2,1)
                   (2,1)  (3,1)  (6)      (3,1)
                   (3,1)  (3,2)  (2,1)    (3,2)
                          (4,1)  (3,1)    (4,1)
                                 (3,2)    (4,3)
                                 (4,1)    (5,1)
                                 (4,2)    (5,2)
                                 (5,1)    (6,1)
                                 (3,2,1)  (3,2,1)
                                          (4,2,1)

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

For positive coefficients we have A088314.
The positive complement is counted by A088528.
The version for subsets is A365073.
The complement is counted by A365312.
For non-strict partitions we have 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. A093971, A237113, A237668, A326080, A363225, A364272, A364534, A364914, A365043, A365314, A365320.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Join@@Array[IntegerPartitions,n],UnsameQ@@#&],combs[n,#]!={}&]],{n,10}]

from math import isqrt
from sympy.utilities.iterables import partitions
def A365311(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n+1) for b in partitions(m,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023

a(26)-a(50) from Chai Wah Wu, Sep 13 2023

A365377 Number of subsets of {1..n} without a subset summing to n.

Original entry on oeis.org

0, 1, 2, 3, 6, 9, 17, 26, 49, 72, 134, 201, 366, 544, 984, 1436, 2614, 3838, 6770, 10019, 17767, 25808, 45597, 66671, 116461, 169747, 295922, 428090, 750343, 1086245, 1863608, 2721509, 4705456, 6759500, 11660244, 16877655, 28879255, 41778027, 71384579, 102527811, 176151979

Offset: 0

Gus Wiseman, Sep 08 2023

nonn

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

David A. Corneth, Table of n, a(n) for n = 0..60

The complement w/ re-usable parts is A365073.
The complement is counted by A365376.
The version with re-usable parts is A365380.
A000009 counts sets summing to n, multisets A000041.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of A326083.
A364350 counts combination-free strict partitions, complement A364839.
A365046 counts combination-full subsets, differences of A364914.
A365381 counts subsets of {1..n} with a subset summing to k.
Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237113, A237668, A326080, A364349, A364534.

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

isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(0))); return(1);
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023

from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365377(n):
    if n == 0: return 0
    nset = set(range(1,n+1))
    s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
    for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
        if sum(a) >= n:
            aset = set(a)
            for p in s:
                if p.issubset(aset):
                    c += 1
                    break
    return (1<Chai Wah Wu, Sep 09 2023

a(n) = 2^n-A365376(n). - Chai Wah Wu, Sep 09 2023

a(16)-a(27) from Michel Marcus, Sep 09 2023
a(28)-a(32) from Chai Wah Wu, Sep 09 2023
a(33)-a(35) from Chai Wah Wu, Sep 10 2023
More terms from David A. Corneth, Sep 10 2023

A364912 Triangle read by rows where T(n,k) is the number of ways to write n as a positive linear combination of an integer partition of k.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 4, 4, 5, 0, 1, 4, 8, 7, 7, 0, 1, 6, 13, 17, 12, 11, 0, 1, 6, 18, 28, 30, 19, 15, 0, 1, 8, 24, 50, 58, 53, 30, 22

Offset: 0

Gus Wiseman, Aug 20 2023

A way of writing n as a positive linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i > 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(2,2)) are a way of writing 8 as a positive linear combination of (1,1,2), namely 8 = 3*1 + 1*1 + 2*2.

			Triangle begins:
  1
  0  1
  0  1  2
  0  1  2  3
  0  1  4  4  5
  0  1  4  8  7  7
  0  1  6 13 17 12 11
  0  1  6 18 28 30 19 15
  0  1  8 24 50 58 53 30 22
Row n = 4 counts the following linear combinations:
  .  1*4  2*2      2*1+1*2      4*1
          1*1+1*3  1*1+1*1+1*2  3*1+1*1
          1*2+1*2  1*1+1*2+1*1  2*1+2*1
          1*3+1*1  1*2+1*1+1*1  2*1+1*1+1*1
                                1*1+1*1+1*1+1*1
Row n = 5 counts the following linear combinations:
  .  1*5  1*1+1*4  2*1+1*3      3*1+1*2          5*1
          1*2+1*3  2*2+1*1      2*1+1*1+1*2      4*1+1*1
          1*3+1*2  1*1+1*1+1*3  2*1+1*2+1*1      3*1+2*1
          1*4+1*1  1*1+1*2+1*2  1*1+1*1+1*1+1*2  3*1+1*1+1*1
                   1*1+1*3+1*1  1*1+1*1+1*2+1*1  2*1+2*1+1*1
                   1*2+1*1+1*2  1*1+1*2+1*1+1*1  2*1+1*1+1*1+1*1
                   1*2+1*2+1*1  1*2+1*1+1*1+1*1  1*1+1*1+1*1+1*1+1*1
                   1*3+1*1+1*1
Array begins:
  1   0   0   0    0    0    0     0
  1   1   1   1    1    1    1     1
  2   2   4   4    6    6    8     8
  3   4   8   13   18   24   33    40
  5   7   17  28   50   70   107   143
  7   12  30  58   108  179  286   428
  11  19  53  109  223  394  696   1108
  15  30  86  194  420  812  1512  2619

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Row k = 0 is A000007.
Row k = 1 is A000012.
Column n = 0 is A000041.
Column n = 1 is A000070.
Row sums are A006951.
Row k = 2 is A052928 except initial terms.
The case of strict integer partitions is A116861.
Central column is T(2n,n) = A(n,n) = A364907(n).
With rows reversed we have the nonnegative version A365004.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A237113, A364272, A364910, A364911, A364914, A364915, A365002.

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

As an array, also the number of ways to write n-k as a nonnegative linear combination of an integer partition of k (see programs).

A365320 Number of pairs of distinct positive integers <= n that cannot be linearly combined with nonnegative coefficients to obtain n.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 1, 7, 5, 12, 12, 27, 14, 42, 36, 47, 47, 83, 58, 109, 80, 116, 126, 172, 111, 195, 192, 219, 202, 294, 210, 342, 286, 354, 369, 409, 324, 509, 480, 523, 452, 640, 507, 711, 622, 675, 747, 865, 654, 916, 842, 964, 922, 1124, 940, 1147, 1029

Offset: 0

Gus Wiseman, Sep 06 2023

nonn

Are there only two cases of nonzero adjacent equal parts, at positions n = 9, 15?

			The pair p = (3,6) cannot be linearly combined to obtain 8 or 10, so p is counted under a(8) and a(10), but we have 9 = 1*3 + 1*6 or 9 = 3*3 + 0*6, so p not counted under a(9).
The a(5) = 2 through a(10) = 12 pairs:
  (2,4)  (4,5)  (2,4)  (3,6)  (2,4)  (3,6)
  (3,4)         (2,6)  (3,7)  (2,6)  (3,8)
                (3,5)  (5,6)  (2,8)  (3,9)
                (3,6)  (5,7)  (4,6)  (4,7)
                (4,5)  (6,7)  (4,7)  (4,8)
                (4,6)         (4,8)  (4,9)
                (5,6)         (5,6)  (6,7)
                              (5,7)  (6,8)
                              (5,8)  (6,9)
                              (6,7)  (7,8)
                              (6,8)  (7,9)
                              (7,8)  (8,9)

The unrestricted version is A000217, ranks A001358.
For strict partitions we have A365312, complement A365311.
The (binary) complement is A365314, positive A365315.
The case of positive coefficients is A365321, for all subsets A365322.
For partitions we have A365378, complement A365379.
For all subsets instead of just pairs we have A365380, complement A365073.
A004526 counts partitions of length 2, shift right for strict.
A007865 counts sum-free subsets, complement A093971.
A179822 and A326080 count sum-closed subsets.
A326083 and A124506 appear to count combination-free subsets.
A364350 counts combination-free strict partitions.
A364914 and A365046 count combination-full subsets.
Cf. A070880, A088314, A088809, A151897, A326020, A364839.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n],{2}],combs[n,#]=={}&]],{n,0,30}]

from itertools import count
from sympy import divisors
def A365320(n):
    a = set()
    for i in range(1,n+1):
        if not n%i:
            a.update(tuple(sorted((i,j))) for j in range(1,n+1) if j!=i)
        else:
            for j in count(0,i):
                if j > n:
                    break
                k = n-j
                for d in divisors(k):
                    if d>=i:
                        break
                    a.add((d,i))
    return (n*(n-1)>>1)-len(a) # Chai Wah Wu, Sep 13 2023

A365322 Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.

Original entry on oeis.org

0, 1, 2, 5, 11, 26, 54, 116, 238, 490, 994, 2011, 4045, 8131, 16305, 32672, 65412, 130924, 261958, 524066, 1048301, 2096826, 4193904, 8388135, 16776641, 33553759, 67108053, 134216782, 268434324, 536869595, 1073740266, 2147481835, 4294965158, 8589932129

Offset: 0

Gus Wiseman, Sep 04 2023

nonn

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

			The set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
The a(1) = 1 through a(4) = 11 subsets:
  {}  {}     {}       {}
      {1,2}  {2}      {3}
             {1,3}    {1,4}
             {2,3}    {2,3}
             {1,2,3}  {2,4}
                      {3,4}
                      {1,2,3}
                      {1,2,4}
                      {1,3,4}
                      {2,3,4}
                      {1,2,3,4}

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The complement is counted by A088314.
The version for strict partitions is A088528.
The nonnegative complement is counted by A365073, without n A365542.
The binary complement is A365315, nonnegative A365314.
The binary version is A365321, nonnegative A365320.
For nonnegative coefficients we have A365380.
A085489 and A364755 count subsets without the sum of two distinct elements.
A124506 appears to count combination-free subsets, differences of A326083.
A179822 counts sum-closed subsets, first differences of A326080.
A364350 counts combination-free strict partitions, non-strict A364915.
A365046 counts combination-full subsets, first differences of A364914.
Cf. A070880, A088809, A093971, A151897, A326020, A364272, A364839, A365043, A365381.

b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
      {b(n, i-1)[], seq(map(x->{x[], i}, b(n-i*j, i-1))[], j=1..n/i)}))
    end:
a:= n-> 2^n-nops(b(n$2)):
seq(a(n), n=0..33);  # Alois P. Heinz, Sep 04 2023

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

from sympy.utilities.iterables import partitions
def A365322(n): return (1<Chai Wah Wu, Sep 14 2023

a(n) = 2^n - A088314(n).

a(n) = A070880(n) + 2^(n-1) for n>=1.

More terms from Alois P. Heinz, Sep 04 2023

A364907 Number of ways to write n as a nonnegative linear combination of an integer partition of n.

Original entry on oeis.org

1, 1, 4, 13, 50, 179, 696, 2619, 10119, 38867, 150407, 582065, 2260367, 8786919, 34225256, 133471650, 521216494, 2037608462, 7974105052, 31235316275, 122457794193, 480473181271, 1886555402750, 7412471695859, 29142658077266, 114643347181003, 451237737215201

Offset: 0

Gus Wiseman, Aug 18 2023

nonn

A way of writing n as a (presumed nonnegative) linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i >= 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(1,1),(0,2)) are a way of writing 5 as a linear combination of (1,1,1,2), namely 5 = 3*1 + 1*1 + 1*1 + 0*2. Of course, there are A000041(n) ways to write n as a linear combination of (1..n).

			The a(0) = 1 through a(3) = 13 ways:
  0  1*1  1*2      1*3
          0*1+2*1  0*2+3*1
          1*1+1*1  1*2+1*1
          2*1+0*1  0*1+0*1+3*1
                   0*1+1*1+2*1
                   0*1+2*1+1*1
                   0*1+3*1+0*1
                   1*1+0*1+2*1
                   1*1+1*1+1*1
                   1*1+2*1+0*1
                   2*1+0*1+1*1
                   2*1+1*1+0*1
                   3*1+0*1+0*1

Alois P. Heinz, Table of n, a(n) for n = 0..500

The case with no zero coefficients is A000041.
A finer version is A364906.
The version for compositions is A364908, strict A364909.
Using just strict partitions we get A364910, main diagonal of A364916.
Main diagonal of A365004.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A323092 counts double-free partitions, ranks A320340.
Cf. A116861, A364350, A364839, A364911, A364912, A364913, A364914, A364915, A365002, A365003.

b:= proc(n, i, m) option remember; `if`(n=0, `if`(m=0, 1, 0),
     `if`(i<1, 0, b(n, i-1, m)+add(b(n-i, min(i, n-i), m-i*j), j=0..m/i)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..27);  # Alois P. Heinz, Jan 28 2024

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Join@@Table[combs[n,ptn],{ptn,IntegerPartitions[n]}]],{n,0,5}]

a(n) = Sum_{m:A056239(m)=n} A364906(m).
a(n) = A364912(2n,n).
a(n) = A365004(n,n).

a(9)-a(26) from Alois P. Heinz, Jan 28 2024

cp's OEIS Frontend

A366320 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A364910 Number of integer partitions of 2n whose distinct parts sum to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A365043 Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A365312 Number of strict integer partitions with sum <= n that cannot be linearly combined using nonnegative coefficients to obtain n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A365311 Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A365377 Number of subsets of {1..n} without a subset summing to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A364912 Triangle read by rows where T(n,k) is the number of ways to write n as a positive linear combination of an integer partition of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica