A124506 -id:A124506 - cp's OEIS frontend

A364914 Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.

0, 0, 1, 3, 9, 20, 48, 101, 219, 454, 944, 1917, 3925, 7915, 16004, 32188, 64751, 129822, 260489, 521672, 1045060, 2091808, 4187047, 8377255, 16762285, 33531228, 67077485, 134170217, 268371678, 536772231, 1073611321, 2147282291, 4294697258, 8589527163, 17179321094

Offset: 0

Gus Wiseman, Aug 17 2023

nonn

A variation of non-binary combination-full sets where parts can be re-used. The complement is counted by A326083. The binary version is A093971. For non-re-usable parts we have A364534. First differences are A365046.

			The set {3,4,5,17} has 17 = 1*3 + 1*4 + 2*5, so is counted under a(17).
The a(0) = 0 through a(5) = 20 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}
                        {2,3,4}    {1,2,5}
                        {1,2,3,4}  {1,3,4}
                                   {1,3,5}
                                   {1,4,5}
                                   {2,3,4}
                                   {2,3,5}
                                   {2,4,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}

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

The binary complement is A007865.
The binary version without re-usable parts is A088809.
The binary version is A093971.
The complement without re-usable parts is A151897.
The complement is counted by A326083.
The version without re-usable parts is A364534.
The version for strict partitions is A364839, complement A364350.
The version for partitions is A364913.
The version for positive combinations is A365043, complement A365044.
First differences are A365046.
Cf. A011782, A085489, A103580, A116861, A124506, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364756.

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]],Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,10}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A364914(n):
    c, mlist = 0, []
    for m in range(1,n+1):
        t = set()
        for p in partitions(m,k=m-1):
            t.add(tuple(sorted(p.keys())))
        mlist.append([set(d) for d in t])
    for k in range(2,n+1):
        for w in combinations(range(1,n+1),k):
            ws = set(w)
            for d in w:
                for s in mlist[d-1]:
                    if s <= ws:
                        c += 1
                        break
                else:
                    continue
                break
    return c # Chai Wah Wu, Nov 17 2023

a(12)-a(34) from Chai Wah Wu, Nov 17 2023

A365663 Triangle read by rows where T(n,k) is the number of strict integer partitions of n without a subset summing to k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 3, 5, 3, 4, 3, 5, 5, 4, 5, 5, 4, 5, 5, 5, 6, 5, 6, 7, 6, 5, 6, 5, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 8, 8, 8, 11, 8, 8, 8, 9, 8, 10, 11, 10, 10, 10, 10, 10, 10, 10, 10, 11, 10, 12, 13, 11, 13, 11, 12, 15, 12, 11, 13, 11, 13, 12

Offset: 2

Gus Wiseman, Sep 17 2023

Warning: Do not confuse with the non-strict version A046663.

Rows are palindromes.

			Triangle begins:
  1
  1  1
  1  2  1
  2  2  2  2
  2  2  3  2  2
  3  3  3  3  3  3
  3  4  3  5  3  4  3
  5  5  4  5  5  4  5  5
  5  6  5  6  7  6  5  6  5
  7  7  7  7  7  7  7  7  7  7
  8  9  8  8  8 11  8  8  8  9  8
Row n = 8 counts the following strict partitions:
  (8)    (8)      (8)    (8)      (8)    (8)      (8)
  (6,2)  (7,1)    (7,1)  (7,1)    (7,1)  (7,1)    (6,2)
  (5,3)  (5,3)    (6,2)  (6,2)    (6,2)  (5,3)    (5,3)
         (4,3,1)         (5,3)           (4,3,1)
                         (5,2,1)

Robert Price, Table of n, a(n) for n = 2..1226
P. Erdős, J. L. Nicolas and A. Sárközy, On the number of partitions of n without a given subsum (I), Discrete Math., 75 (1989), 155-166 = Annals Discrete Math. Vol. 43, Graph Theory and Combinatorics 1988, ed. B. Bollobas.

Columns k = 0 and k = n are A025147.
The non-strict version is A046663, central column A006827.
Central column n = 2k is A321142.
The complement for subsets instead of strict partitions is A365381.
The complement is A365661, non-strict A365543, central column A237258.
Row sums are A365922.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of A326083.
A364272 counts sum-full strict partitions, sum-free A364349.
A364350 counts combination-free strict partitions, complement A364839.
Cf. A002219, A108796, A108917, A122768, A275972, A299701, A304792, A364916, A365311, A365376, A365541.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&FreeQ[Total/@Subsets[#],k]&]], {n,2,15},{k,1,n-1}]

A088314 Cardinality of set of sets of parts of all partitions of n.

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 10, 12, 18, 22, 30, 37, 51, 61, 79, 96, 124, 148, 186, 222, 275, 326, 400, 473, 575, 673, 811, 946, 1132, 1317, 1558, 1813, 2138, 2463, 2893, 3323, 3882, 4461, 5177, 5917, 6847, 7818, 8994, 10251, 11766, 13334, 15281, 17309, 19732, 22307

Offset: 0

Naohiro Nomoto, Nov 05 2003

Number of different values of A007947(m) when A056239(m) is equal to n.
From Gus Wiseman, Sep 11 2023: (Start)
Also the number of finite sets of positive integers that can be linearly combined using all positive coefficients to obtain n. For example, the a(1) = 1 through a(7) = 12 sets are:
  {1}  {1}  {1}    {1}    {1}    {1}      {1}
       {2}  {3}    {2}    {5}    {2}      {7}
            {1,2}  {4}    {1,2}  {3}      {1,2}
                   {1,2}  {1,3}  {6}      {1,3}
                   {1,3}  {1,4}  {1,2}    {1,4}
                          {2,3}  {1,3}    {1,5}
                                 {1,4}    {1,6}
                                 {1,5}    {2,3}
                                 {2,4}    {2,5}
                                 {1,2,3}  {3,4}
                                          {1,2,3}
                                          {1,2,4}
Cf. A365073, A365311, A365312, A365322, A365380.
(End)

			The 7 partitions of 5 and their sets of parts are
[ #]  partition      set of parts
[ 1]  [ 1 1 1 1 1 ]  {1}
[ 2]  [ 2 1 1 1 ]    {1, 2}
[ 3]  [ 2 2 1 ]      {1, 2}  (same as before)
[ 4]  [ 3 1 1 ]      {1, 3}
[ 5]  [ 3 2 ]        {2, 3}
[ 6]  [ 4 1 ]        {1, 4}
[ 7]  [ 5 ]          {5}
so we have a(5) = |{{1}, {1, 2}, {1, 3}, {2, 3}, {1, 4}, {5}}| = 6.

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

Cf. A182410.
The complement in subsets of {1..n-1} is A070880(n) = A365045(n) - 1.
The case of pairs is A365315, see also A365314, A365320, A365321.
A116861 and A364916 count linear combinations of strict partitions.
A179822 and A326080 count sum-closed subsets.
A326083 and A124506 appear to count combination-free subsets.
A364914 and A365046 count combination-full subsets.
Cf. A000009, A007865, A088528, A088809, A093971, A326020, A364272, A364534, A365043, A364350.

a066186 = sum . concat . ps 1 where
   ps _ 0 = [[]]
   ps i j = [t:ts | t <- [i..j], ts <- ps t (j - t)]
-- Reinhard Zumkeller, Jul 13 2013

list2set := L -> {op(L)};
a:= N -> list2set(map( list2set, combinat[partition](N) ));
seq(nops(a(n)), n=0..30);
#  Yogy Namara (yogy.namara(AT)gmail.com), Jan 13 2010
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-> nops(b(n, n)):
seq(a(n), n=0..40);
# Alois P. Heinz, Aug 09 2012

Table[Length[Union[Map[Union,IntegerPartitions[n]]]],{n,1,30}] (* Geoffrey Critzer, Feb 19 2013 *)
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, {{}}, If[i < 1, {},
     Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,
     Append[#, i]]& /@ b[n - i*j, i - 1], {j, 1, n/i}]}]];
a[n_] := Length[b[n, n]];
a /@ Range[0, 40] (* Jean-François Alcover, Jun 04 2021, after Alois P. Heinz *)
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@@Array[IntegerPartitions,n], UnsameQ@@#&&combp[n,#]!={}&]], {n,0,15}] (* Gus Wiseman, Sep 11 2023 *)

from sympy.utilities.iterables import partitions
def A088314(n): return len({tuple(sorted(set(p))) for p in partitions(n)}) # Chai Wah Wu, Sep 10 2023

a(n) = 2^(n-1) - A070880(n). - Alois P. Heinz, Feb 08 2019

a(n) = A365042(n) + 1. - Gus Wiseman, Sep 13 2023

More terms and clearer definition from Vladeta Jovovic, Apr 21 2005

A365046 Number of subsets of {1..n} containing n such that some element can be written as a nonnegative linear combination of the others.

Original entry on oeis.org

0, 0, 1, 2, 6, 11, 28, 53, 118, 235, 490, 973, 2008, 3990, 8089, 16184, 32563, 65071, 130667, 261183, 523388, 1046748, 2095239, 4190208, 8385030, 16768943, 33546257, 67092732, 134201461, 268400553, 536839090, 1073670970, 2147414967, 4294829905, 8589793931

Offset: 0

Gus Wiseman, Aug 24 2023

nonn

Includes all subsets containing both 1 and n.

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

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

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

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]],MemberQ[#,n]&&Or@@Table[combs[#[[k]],Union[Delete[#,k]]]!={},{k,Length[#]}]&]],{n,0,10}]

a(n+1) = 2^n - A124506(n).

A365073 Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

1, 1, 3, 6, 14, 26, 60, 112, 244, 480, 992, 1944, 4048, 7936, 16176, 32320, 65088, 129504, 261248, 520448, 1046208, 2090240, 4186624, 8365696, 16766464, 33503744, 67064064, 134113280, 268347392, 536546816, 1073575936, 2146703360, 4294425600, 8588476416, 17178349568

Offset: 0

Gus Wiseman, Sep 01 2023

nonn

			The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
The a(1) = 1 through a(4) = 14 subsets:
  {1}  {1}    {1}      {1}
       {2}    {3}      {2}
       {1,2}  {1,2}    {4}
              {1,3}    {1,2}
              {2,3}    {1,3}
              {1,2,3}  {1,4}
                       {2,3}
                       {2,4}
                       {3,4}
                       {1,2,3}
                       {1,2,4}
                       {1,3,4}
                       {2,3,4}
                       {1,2,3,4}

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

The case of positive coefficients is A088314.
The case of subsets containing n is A131577.
The binary version is A365314, positive A365315.
The binary complement is A365320, positive A365321.
The positive complement is counted by A365322.
A version for partitions is A365379, strict A365311.
The complement is counted by A365380.
The case of subsets without n is A365542.
A326083 and A124506 appear to count combination-free subsets.
A179822 and A326080 count sum-closed subsets.
A364350 counts combination-free strict partitions.
A364914 and A365046 count combination-full subsets.
Cf. A007865, A088809, A093971, A151897, A237668, A308546, A326020, A364534, A364839, A365043, A365381.

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]],combs[n,#]!={}&]],{n,0,5}]

a(n)={
  my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
  my(recurse(k,b)=
    if(bittest(b,0), 2^(n+1-k),
    if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
    self()(k+1, b) + self()(k+1, comb(k,b)) )));
  recurse(1, 1<Andrew Howroyd, Sep 04 2023

Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023

A367213 Number of integer partitions of n whose length (number of parts) is not equal to the sum of any submultiset.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 5, 4, 7, 8, 12, 13, 19, 21, 29, 33, 45, 49, 67, 73, 97, 108, 139, 152, 196, 217, 274, 303, 379, 420, 523, 579, 709, 786, 960, 1061, 1285, 1423, 1714, 1885, 2265, 2498, 2966, 3280, 3881, 4268, 5049, 5548, 6507, 7170, 8391, 9194, 10744, 11778, 13677

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

These partitions are necessarily incomplete (A365924).

Are there any decreases after the initial terms?

			The a(3) = 1 through a(9) = 8 partitions:
  (3)  (4)    (5)    (6)      (7)      (8)        (9)
       (3,1)  (4,1)  (3,3)    (4,3)    (4,4)      (5,4)
                     (5,1)    (6,1)    (5,3)      (6,3)
                     (2,2,2)  (5,1,1)  (7,1)      (8,1)
                     (4,1,1)           (4,2,2)    (4,4,1)
                                       (6,1,1)    (5,2,2)
                                       (5,1,1,1)  (7,1,1)
                                                  (6,1,1,1)

Chai Wah Wu, Table of n, a(n) for n = 0..65

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213*   A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217    A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000041 counts partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A007865/A085489/A151897 count certain types of sum-free subsets.
A108917 counts knapsack partitions, non-knapsack A366754.
A126796 counts complete partitions, incomplete A365924.
A237667 counts sum-free partitions, sum-full A237668.
A304792 counts subset-sums of partitions, strict A365925.
Triangles:
A008284 counts partitions by length, strict A008289.
A046663 counts partitions of n without a subset-sum k, strict A365663.
A365543 counts partitions of n with a subset-sum k, strict A365661.
A365658 counts partitions by number of subset-sums, strict A365832.
Cf. A000700, A124506, A238628, A240861, A364349, A364531, A365045, A365381, A365918, A366320.

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

a(41)-a(54) from Chai Wah Wu, Nov 13 2023

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

Original entry on oeis.org

1, 1, 2, 2, 6, 4, 16, 12, 32, 32, 104, 48, 256, 208, 448, 448, 1568, 896, 3840, 2368, 6912, 7680, 22912, 10752, 50688, 44800, 104448, 88064, 324096, 165888, 780288, 541696, 1458176, 1519616, 4044800, 2220032, 10838016, 8744960, 20250624, 16433152, 62267392, 34865152

Offset: 1

Gus Wiseman, Sep 04 2023

nonn

			The set {4,5,6} cannot be linearly combined to obtain 7 so is counted under a(7), but we have 8 = 2*4 + 0*5 + 0*6, so it is not counted under a(8).
The a(1) = 1 through a(8) = 12 subsets:
  {}  {}  {}   {}   {}     {}     {}       {}
          {2}  {3}  {2}    {4}    {2}      {3}
                    {3}    {5}    {3}      {5}
                    {4}    {4,5}  {4}      {6}
                    {2,4}         {5}      {7}
                    {3,4}         {6}      {3,6}
                                  {2,4}    {3,7}
                                  {2,6}    {5,6}
                                  {3,5}    {5,7}
                                  {3,6}    {6,7}
                                  {4,5}    {3,6,7}
                                  {4,6}    {5,6,7}
                                  {5,6}
                                  {2,4,6}
                                  {3,5,6}
                                  {4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 1..100
Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The complement is counted by A365073, without n A365542.
The binary complement is A365314, positive A365315.
The binary case is A365320, positive A365321.
For positive coefficients we have A365322, complement A088314.
A124506 appears to count combination-free subsets, differences of A326083.
A179822 counts sum-closed subsets, first differences of A326080.
A288728 counts binary sum-free subsets, first differences of A007865.
A365046 counts combination-full subsets, first differences of A364914.
A365071 counts sum-free subsets, first differences of A151897.
Cf. A050291, A085489, A088528, A088809, A093971, A326020, A364350, A364534, A365043, A365045.

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-1]],combs[n,#]=={}&]],{n,5}]

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

Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023

A367215 Number of strict integer partitions of n whose length (number of parts) is not equal to the sum of any subset.

Original entry on oeis.org

0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 8, 10, 12, 15, 18, 21, 25, 29, 34, 40, 46, 53, 62, 71, 82, 95, 109, 124, 143, 162, 185, 210, 240, 270, 308, 347, 393, 443, 500, 562, 634, 711, 798, 895, 1002, 1120, 1252, 1397, 1558, 1735, 1930, 2146, 2383, 2644, 2930, 3245

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

These partitions have Heinz numbers A367225 /\ A005117.

			The a(2) = 1 through a(11) = 7 strict partitions:
  (2)  (3)  (4)    (5)    (6)    (7)    (8)    (9)    (10)     (11)
            (3,1)  (4,1)  (5,1)  (4,3)  (5,3)  (5,4)  (6,4)    (6,5)
                                 (6,1)  (7,1)  (6,3)  (7,3)    (7,4)
                                               (8,1)  (9,1)    (8,3)
                                                      (5,4,1)  (10,1)
                                                               (5,4,2)
                                                               (6,4,1)
The a(2) = 1 through a(15) = 15 strict partitions (A..F = 10..15):
  2  3  4   5   6   7   8   9   A    B    C    D    E     F
        31  41  51  43  53  54  64   65   75   76   86    87
                    61  71  63  73   74   84   85   95    96
                            81  91   83   93   94   A4    A5
                                541  A1   B1   A3   B3    B4
                                     542  642  C1   D1    C3
                                     641  651  652  752   E1
                                          741  742  761   654
                                               751  842   762
                                               841  851   852
                                                    941   861
                                                    6521  942
                                                          951
                                                          A41
                                                          7521

Chai Wah Wu, Table of n, a(n) for n = 0..118

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215*   A367220    A367221
  subsets:     A367216    A367217    A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000041 counts integer partitions, strict A000009.
A007865/A085489/A151897 count certain types of sum-free subsets.
A124506 appears to count combination-free subsets, differences of A326083.
A188431 counts complete strict partitions, incomplete A365831.
A237667 counts sum-free partitions, ranks A364531.
A240861 counts strict partitions with length not a part, complement A240855.
A275972 counts strict knapsack partitions, non-strict A108917.
A364349 counts sum-free strict partitions, sum-full A364272.
Triangles:
A008289 counts strict partitions by length, non-strict A008284.
A365661 counts strict partitions with a subset-sum k, non-strict A365543.
A365663 counts strict partitions without a subset-sum k, non-strict A046663.
A365832 counts strict partitions by subset-sums, non-strict A365658.
Cf. A002865, A229816, A238628, A364346, A364350, A365312, A365922, A366320.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,30}]

A367217 Number of subsets of {1..n} whose cardinality is not equal to the sum of any subset.

Original entry on oeis.org

0, 0, 1, 3, 6, 12, 24, 46, 87, 164, 308, 577, 1080, 2021, 3779, 7058, 13166, 24533, 45674, 84978, 158026, 293737, 545747, 1013467, 1881032, 3489303, 6468910, 11985988, 22195905, 41080751, 75994642, 140514019, 259693004, 479749492, 885910870, 1635281386

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

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

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217*   A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A229816 counts partitions whose length is not a part, complement A002865.
A007865/A085489/A151897 count certain types of sum-free subsets.
A088809/A093971/A364534 count certain types of sum-full subsets.
A124506 appears to count combination-free subsets, differences of A326083.
A237667 counts sum-free partitions, ranks A364531.
Triangles:
A046663 counts partitions of n without a subset-sum k, strict A365663.
A365381 counts sets with a subset summing to k, without A366320.
A365541 counts sets containing two distinct elements summing to k.
Cf. A068911, A103580, A240861, A288728, A326080, A326083, A364346, A364349, A365046, A365376, A365377.

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

a(n) = 2^n - A367216(n). - Chai Wah Wu, Nov 14 2023

a(16)-a(28) from Chai Wah Wu, Nov 14 2023

a(29)-a(35) from Max Alekseyev, Feb 25 2025

A367219 Number of integer partitions of n whose length cannot be written as a nonnegative linear combination of the distinct parts.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 3, 2, 4, 4, 7, 6, 11, 9, 16, 16, 23, 22, 35, 33, 48, 50, 69, 70, 99, 99, 136, 142, 187, 194, 261, 267, 346, 367, 468, 489, 626, 650, 824, 870, 1081, 1135, 1421, 1485, 1833, 1942, 2374, 2501, 3062, 3220, 3915, 4145, 4987, 5274, 6363, 6709, 8027

Offset: 0

Gus Wiseman, Nov 14 2023

nonn

			3 cannot be written as a nonnegative linear combination of 2 and 5, so (5,2,2) is counted under a(9).
The a(2) = 1 through a(10) = 7 partitions:
  (2)  (3)  (4)  (5)  (6)      (7)    (8)      (9)      (10)
                      (3,3)    (4,3)  (4,4)    (5,4)    (5,5)
                      (2,2,2)         (5,3)    (6,3)    (6,4)
                                      (4,2,2)  (5,2,2)  (7,3)
                                                        (4,4,2)
                                                        (6,2,2)
                                                        (2,2,2,2,2)

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219*
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217    A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000041 counts integer partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A008284 counts partitions by length, strict A008289.
A124506 appears to count combination-free subsets, differences of A326083.
A365046 counts combination-full subsets, differences of A364914.
Cf. A068911, A088314, A116861, A364345, A364350, A365073, A365312, A365380.

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

a(31)-a(56) from Chai Wah Wu, Nov 15 2023

cp's OEIS Frontend

A364914 Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A365663 Triangle read by rows where T(n,k) is the number of strict integer partitions of n without a subset summing to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A088314 Cardinality of set of sets of parts of all partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Formula

Extensions

A365046 Number of subsets of {1..n} containing n such that some element can be written as a nonnegative linear combination of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A365073 Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A367213 Number of integer partitions of n whose length (number of parts) is not equal to the sum of any submultiset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica