A365045
Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.
Original entry on oeis.org
0, 1, 1, 2, 4, 11, 23, 53, 111, 235, 483, 988, 1998, 4036, 8114, 16289, 32645, 65389, 130887, 261923, 524014, 1048251, 2096753, 4193832, 8388034, 16776544, 33553622, 67107919, 134216597, 268434140, 536869355, 1073740012, 2147481511, 4294964834, 8589931700
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is not counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. {1} {2} {3} {4} {5}
{2,3} {3,4} {2,5}
{2,3,4} {3,5}
{1,2,3,4} {4,5}
{2,4,5}
{3,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
Without re-usable parts we have
A365071, first differences of
A151897.
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[combp[#[[k]],Union[Delete[#,k]]]=={},{k,Length[#]}]&]],{n,0,10}]
A365044
Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
1, 2, 3, 5, 9, 20, 43, 96, 207, 442, 925, 1913, 3911, 7947, 16061, 32350, 64995, 130384, 261271, 523194, 1047208, 2095459, 4192212, 8386044, 16774078, 33550622, 67104244, 134212163, 268428760, 536862900, 1073732255, 2147472267, 4294953778, 8589918612, 17179850312
Offset: 0
The subset S = {3,5,6,8} has 6 = 2*3 + 0*5 + 0*8 and 8 = 1*3 + 1*5 + 0*6 but neither of these is strictly positive, so S is counted under a(8).
The a(0) = 1 through a(5) = 20 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{3} {3} {3}
{2,3} {4} {4}
{2,3} {5}
{3,4} {2,3}
{2,3,4} {2,5}
{1,2,3,4} {3,4}
{3,5}
{4,5}
{2,3,4}
{2,4,5}
{3,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}
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
Cf.
A006951,
A237113,
A237668,
A308546,
A324736,
A326020,
A326080,
A364272,
A364349,
A364534,
A365069.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365044(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
return n+1+sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] not in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023
A365071
Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.
Original entry on oeis.org
0, 1, 2, 3, 6, 9, 15, 23, 40, 55, 94, 132, 210, 298, 476, 644, 1038, 1406, 2149, 2965, 4584, 6077, 9426, 12648, 19067, 25739, 38958, 51514, 78459, 104265, 155436, 208329, 312791, 411886, 620780, 823785, 1224414, 1631815, 2437015, 3217077, 4822991
Offset: 0
The subset {1,3,4,6} has 4 = 1 + 3 so is not counted under a(6).
The subset {2,3,4,5,6} has 6 = 2 + 4 and 4 = 1 + 3 so is not counted under a(6).
The a(0) = 0 through a(6) = 15 subsets:
. {1} {2} {3} {4} {5} {6}
{1,2} {1,3} {1,4} {1,5} {1,6}
{2,3} {2,4} {2,5} {2,6}
{3,4} {3,5} {3,6}
{1,2,4} {4,5} {4,6}
{2,3,4} {1,2,5} {5,6}
{1,3,5} {1,2,6}
{2,4,5} {1,3,6}
{3,4,5} {1,4,6}
{2,3,6}
{2,5,6}
{3,4,6}
{3,5,6}
{4,5,6}
{3,4,5,6}
The version with re-usable parts is
A288728 first differences of
A007865.
The complement w/ re-usable parts is
A365070, first differences of
A093971.
A364350 counts combination-free strict partitions, complement
A364839.
-
Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#,{2,Length[#]}]]=={}&]], {n,0,10}]
Showing 1-3 of 3 results.
Comments