Displaying 1-10 of 103 results found.
page
1
2
3
4
5
6
7
8
9
10
11
Number of subsets of {1..n} containing all of their pairwise sums <= n.
+10
92
1, 2, 3, 5, 7, 12, 16, 27, 37, 58, 80, 131, 171, 277, 380, 580, 785, 1250, 1655, 2616, 3516, 5344, 7257, 11353, 14931, 23204, 31379, 47511, 63778, 98681, 130503, 201357, 270038, 407429, 548090, 840171, 1110429, 1701872, 2284325, 3440337, 4601656
COMMENTS
The summands are allowed to be equal. The case where they must be distinct is A326080. If A007865 counts sum-free sets, this sequence counts sum-closed sets. This is different from sum-full sets ( A093971). Also the number of subsets of {1..n} containing no sum of any multiset of the elements. For example, the a(0) = 1 through a(6) = 16 subsets are:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{2,3} {4} {4} {4}
{2,3} {5} {5}
{3,4} {2,3} {6}
{2,5} {2,3}
{3,4} {2,5}
{3,5} {3,4}
{4,5} {3,5}
{3,4,5} {4,5}
{4,6}
{5,6}
{3,4,5}
{4,5,6}
(End)
EXAMPLE
The a(0) = 1 through a(6) = 16 subsets:
{} {} {} {} {} {} {}
{1} {2} {2} {3} {3} {4}
{1,2} {3} {4} {4} {5}
{2,3} {2,4} {5} {6}
{1,2,3} {3,4} {2,4} {3,6}
{2,3,4} {3,4} {4,5}
{1,2,3,4} {3,5} {4,6}
{4,5} {5,6}
{2,4,5} {2,4,6}
{3,4,5} {3,4,6}
{2,3,4,5} {3,5,6}
{1,2,3,4,5} {4,5,6}
{2,4,5,6}
{3,4,5,6}
{2,3,4,5,6}
{1,2,3,4,5,6}
The a(7) = 27 subsets:
{} {4} {36} {246} {2467} {24567} {234567} {1234567}
{5} {45} {356} {3467} {34567}
{6} {46} {367} {3567}
{7} {47} {456} {4567}
{56} {457}
{57} {467}
{67} {567}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], SubsetQ[#, Select[Plus@@@Tuples[#, 2], #<=n&]]&]], {n, 0, 10}]
CROSSREFS
Cf. A007865, A050291, A051026, A054519, A085489, A093971, A103580, A120641, A151897, A326020, A326023, A326076, A326080.
Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.
+10
81
1, 1, 1, 1, 1, 2, 1, 3, 2, 3, 3, 5, 3, 6, 5, 7, 6, 9, 7, 11, 10, 14, 12, 16, 15, 20, 17, 24, 22, 27, 29, 32, 30, 41, 36, 49, 45, 50, 52, 65, 63, 70, 77, 80, 83, 104, 98, 107, 116, 126, 134, 152, 148, 162, 180, 196, 195, 227, 227, 238, 272, 271, 293, 333, 325
COMMENTS
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).
EXAMPLE
The a(16) = 6 through a(22) = 12 strict partitions:
(16) (17) (18) (19) (20) (21) (22)
(9,7) (9,8) (10,8) (10,9) (11,9) (12,9) (13,9)
(10,6) (10,7) (11,7) (11,8) (12,8) (13,8) (14,8)
(11,5) (11,6) (13,5) (12,7) (13,7) (15,6) (15,7)
(13,3) (12,5) (14,4) (13,6) (14,6) (16,5) (16,6)
(7,5,4) (13,4) (7,6,5) (14,5) (17,3) (17,4) (17,5)
(14,3) (8,7,3) (15,4) (8,7,5) (19,2) (18,4)
(15,2) (16,3) (9,6,5) (11,10) (19,3)
(7,6,4) (17,2) (9,7,4) (8,7,6) (12,10)
(8,6,5) (11,5,4) (9,7,5) (9,7,6)
(9,6,4) (10,7,4) (9,8,5)
(10,8,3) (7,6,5,4)
(11,6,4)
(11,7,3)
MATHEMATICA
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], UnsameQ@@#&&And@@Table[combs[#[[k]], Delete[#, k]]=={}, {k, Length[#]}]&]], {n, 0, 15}]
PROG
(Python)
from sympy.utilities.iterables import partitions
if n <= 1: return 1
alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 1
for p in partitions(n, k=n-1):
if max(p.values(), default=0)==1:
s = set(p)
if not any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
c += 1
CROSSREFS
For sums of subsets instead of combinations of partitions we have A151897. For subsets instead of partitions we have A326083, complement A364914. A more strict variation is A364915. The case of all positive coefficients is A365006. A364912 counts linear combinations of partitions of k.
Cf. A007865, A085489, A237113, A275972, A363226, A364272, A364533, A364910, A364911, A365002, A365004.
Number of strict integer partitions of n containing the sum of some subset of the parts. A variation of sum-full strict partitions.
+10
78
0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 3, 1, 4, 3, 8, 6, 11, 10, 17, 16, 26, 25, 39, 39, 54, 60, 82, 84, 116, 126, 160, 177, 222, 242, 302, 337, 402, 453, 542, 601, 722, 803, 936, 1057, 1234, 1373, 1601, 1793, 2056, 2312, 2658, 2950, 3395, 3789, 4281, 4814, 5452, 6048
COMMENTS
First differs from A316402 at a(16) = 11 due to (7,5,3,1).
EXAMPLE
The a(6) = 1 through a(16) = 11 partitions (A=10):
(321) . (431) . (532) (5321) (642) (5431) (743) (6432) (853)
(541) (651) (6421) (752) (6531) (862)
(4321) (5421) (7321) (761) (7431) (871)
(6321) (5432) (7521) (6532)
(6431) (9321) (6541)
(6521) (54321) (7432)
(7421) (7621)
(8321) (8431)
(8521)
(A321)
(64321)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&Intersection[#, Total/@Subsets[#, {2, Length[#]}]]!={}&]], {n, 0, 30}]
CROSSREFS
The linear combination-free version is A364350.
Number of sum-full subsets of {1,...,n}; subsets A such that there is a solution to x+y=z for x,y,z in A.
+10
75
0, 1, 2, 7, 16, 40, 86, 195, 404, 873, 1795, 3727, 7585, 15537, 31368, 63582, 127933, 257746, 517312, 1038993, 2081696, 4173322, 8355792, 16731799, 33484323, 67014365, 134069494, 268234688, 536562699, 1073326281, 2146849378, 4294117419, 8588623348, 17178130162
COMMENTS
In sumset notation, number of subsets A of {1,...,n} such that the intersection of A and 2A is nonempty.
A variation of binary sum-full sets where parts can be re-used, this sequence counts subsets of {1..n} containing a part equal to the sum of two other (possibly equal) parts. The complement is counted by A007865. The non-binary version is A364914. For non-re-usable parts we have A088809. - Gus Wiseman, Aug 14 2023
EXAMPLE
The a(1) = 0 through a(5) = 16 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}
{2,3,4} {1,3,4}
{1,2,3,4} {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}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Intersection[#, Total/@Tuples[#, 2]]!={}&]], {n, 0, 10}] (* Gus Wiseman, Aug 14 2023 *)
CROSSREFS
The complement is counted by A007865. The non-binary version w/o re-usable parts is A364534, complement A151897. The version for partitions is A363225: - non-binary without re-usable parts A237668. The complement for partitions is A364345: - non-binary without re-usable parts A237667.
Number of subsets of {1, 2, ..., n} such that no member is a sum of distinct other members.
+10
70
1, 2, 4, 7, 13, 22, 37, 60, 100, 155, 249, 381, 591, 889, 1365, 2009, 3047, 4453, 6602, 9567, 14151, 20228, 29654, 42302, 61369, 87108, 126066, 177580, 256039, 360304, 515740, 724069, 1036860, 1448746, 2069526, 2893311, 4117725, 5749540, 8186555
COMMENTS
This sequence and A085489 first differ at n = 7. a(7) = 60, A085489(7) = 61. A085489(7) includes {1, 2, 4, 7}, which is excluded from a(7) because 1+2+4 = 7. If this sequence counts sum-free sets, A326080 counts sum-closed sets, which are different from sum-full sets ( A093971). - Gus Wiseman, Jun 07 2019
EXAMPLE
a(4) = 13, including all subsets of {1, 2, 3, 4} except {1, 2, 3} (excluded
because 1+2 = 3), {1, 3, 4} (excluded because 1+3 = 4), and {1, 2, 3, 4} (excluded for both reasons.)
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,2,4}
{2,3,4}
(End)
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Intersection[#, Plus@@@Subsets[#, {2, Length[#]}]]=={}&]], {n, 0, 10}] (* Gus Wiseman, Jun 07 2019 *)
Number of partitions of n such that some part is a sum of two other parts.
+10
65
0, 0, 0, 0, 1, 1, 3, 3, 8, 10, 17, 22, 37, 47, 71, 91, 133, 170, 236, 301, 408, 515, 686, 860, 1119, 1401, 1798, 2232, 2829, 3495, 4378, 5381, 6682, 8165, 10060, 12238, 14958, 18116, 22018, 26533, 32071, 38490, 46265, 55318, 66193, 78843, 93949, 111503, 132326
COMMENTS
These are partitions containing the sum of some 2-element submultiset of the parts, a variation of binary sum-full partitions where parts cannot be re-used, ranked by A364462. The complement is counted by A236912. The non-binary version is A237668. For re-usable parts we have A363225. - Gus Wiseman, Aug 10 2023
EXAMPLE
Of the 11 partitions of 6, only these 3 include a part that is a sum of two other parts: [3,2,1], [2,2,1,1], [2,1,1,1,1]. Thus, a(6) = 3.
The a(0) = 0 through a(9) = 10 partitions:
. . . . (211) (2111) (321) (3211) (422) (3321)
(2211) (22111) (431) (4221)
(21111) (211111) (3221) (4311)
(4211) (5211)
(22211) (32211)
(32111) (42111)
(221111) (222111)
(2111111) (321111)
(2211111)
(21111111)
(End)
MATHEMATICA
z = 20; t = Map[Count[Map[Length[Cases[Map[Total[#] &, Subsets[#, {2}]], Apply[Alternatives, #]]] &, IntegerPartitions[#]], 0] &, Range[z]] (* A236912 *) Table[Length[Select[IntegerPartitions[n], Intersection[#, Total/@Subsets[#, {2}]]!={}&]], {n, 0, 30}] (* Gus Wiseman, Aug 09 2023 *)
CROSSREFS
These partitions have ranks A364462.
Number of subsets of {1, ..., n} that are not sum-free.
+10
62
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
COMMENTS
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
EXAMPLE
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)
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Intersection[#, Total/@Subsets[#, {2}]]!={}&]], {n, 0, 10}] (* Gus Wiseman, Aug 10 2023 *)
CROSSREFS
The complement for partitions is A236912: The version for partitions is A237113: Cf. A000079, A007865, A050291, A051026, A103580, A288728, A326020, A326080, A326083, A364272, A364349.
a(n) is the number of subsets of {1,...,n} containing no solutions to x+y=z with x and y distinct (one version of "sum-free subsets").
+10
60
1, 2, 4, 7, 13, 22, 37, 61, 102, 162, 261, 410, 646, 1001, 1553, 2370, 3645, 5515, 8303, 12470, 18713, 27811, 41244, 60962, 89733, 131870, 192522, 281125, 408680, 593880, 855661, 1238592, 1779614, 2563476, 3660084, 5255913, 7473380, 10696444, 15137517
LINKS
Eric Weisstein's World of Mathematics, Sum-Free Set [Strictly speaking this link is not relevant, since it uses a different definition of "sum-free".]
EXAMPLE
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,2,4}
{2,3,4}
The a(5) = 22 subsets:
{} {1} {1,2} {1,2,4}
{2} {1,3} {1,2,5}
{3} {1,4} {1,3,5}
{4} {1,5} {2,3,4}
{5} {2,3} {2,4,5}
{2,4} {3,4,5}
{2,5}
{3,4}
{3,5}
{4,5}
(End)
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Intersection[ #, Select[ Plus@@@ Subsets[ #, {2}], #<=n&]]=={}&]], {n, 0, 10}] (* Gus Wiseman, Jun 07 2019 *)
Number of partitions of n such that no part is a sum of two other parts.
+10
58
1, 1, 2, 3, 4, 6, 8, 12, 14, 20, 25, 34, 40, 54, 64, 85, 98, 127, 149, 189, 219, 277, 316, 395, 456, 557, 638, 778, 889, 1070, 1226, 1461, 1667, 1978, 2250, 2645, 3019, 3521, 3997, 4652, 5267, 6093, 6909, 7943, 8982, 10291, 11609, 13251, 14947, 16984, 19104
COMMENTS
These are partitions containing the sum of no 2-element submultiset of the parts, a variation of binary sum-free partitions where parts cannot be re-used, ranked by A364461. The complement is counted by A237113. The non-binary version is A237667. For re-usable parts we have A364345. - Gus Wiseman, Aug 09 2023
EXAMPLE
Of the 11 partitions of 6, only these 3 include a part that is a sum of two other parts: [3,2,1], [2,2,1,1], [2,1,1,1,1]. Thus, a(6) = 11 - 3 = 8.
The a(1) = 1 through a(8) = 14 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (21) (22) (32) (33) (43) (44)
(111) (31) (41) (42) (52) (53)
(1111) (221) (51) (61) (62)
(311) (222) (322) (71)
(11111) (411) (331) (332)
(3111) (421) (521)
(111111) (511) (611)
(2221) (2222)
(4111) (3311)
(31111) (5111)
(1111111) (41111)
(311111)
(11111111)
(End)
MATHEMATICA
z = 20; t = Map[Count[Map[Length[Cases[Map[Total[#] &, Subsets[#, {2}]], Apply[Alternatives, #]]] &, IntegerPartitions[#]], 0] &, Range[z]] (* A236912 *) Table[Length[Select[IntegerPartitions[n], Intersection[#, Total/@Subsets[#, {2}]]=={}&]], {n, 0, 15}] (* Gus Wiseman, Aug 09 2023 *)
CROSSREFS
The (strict) version for linear combinations of parts is A364350. These partitions have ranks A364461.
Number of partitions of n such that no part is a sum of two or more other parts.
+10
57
1, 1, 2, 3, 4, 6, 7, 11, 12, 17, 19, 29, 28, 41, 42, 61, 61, 87, 85, 120, 117, 160, 156, 224, 216, 288, 277, 380, 363, 483, 474, 622, 610, 783, 755, 994, 986, 1235, 1191, 1549, 1483, 1876, 1865, 2306, 2279, 2806, 2732, 3406, 3413, 4091, 4013, 4991, 4895, 5872
COMMENTS
Includes all knapsack partitions ( A108917), but first differs at a(12) = 28, A108917(12) = 25. The difference is accounted for by the non-knapsack partitions: (4332), (5331), (33222). These are partitions not containing the sum of any non-singleton submultiset of the parts, a variation of non-binary sum-free partitions where parts cannot be re-used, ranked by A364531. The complement is counted by A237668. The binary version is A236912. For re-usable parts we have A364350. (End)
EXAMPLE
For n = 6, the nonqualifiers are 123, 1113, 1122, 11112, leaving a(6) = 7.
The partition y = (5,3,1,1) has submultiset (3,1,1) with sum in y, so is not counted under a(10).
The partition y = (5,3,3,1) has no non-singleton submultiset with sum in y, so is counted under a(12).
The a(1) = 1 through a(8) = 12 partitions:
(1) (2) (3) (4) (5) (6) (7) (8)
(11) (21) (22) (32) (33) (43) (44)
(111) (31) (41) (42) (52) (53)
(1111) (221) (51) (61) (62)
(311) (222) (322) (71)
(11111) (411) (331) (332)
(111111) (421) (521)
(511) (611)
(2221) (2222)
(4111) (3311)
(1111111) (5111)
(11111111)
(End)
MATHEMATICA
Map[Count[Map[MemberQ[#, Apply[Alternatives, Map[Apply[Plus, #]&, DeleteDuplicates[DeleteCases[Subsets[#], _?(Length[#]<2&)]]]]]&, IntegerPartitions[#]], False]&, Range[20]] (* Peter J. C. Moses, Feb 10 2014 *) Table[Length[Select[IntegerPartitions[n], Intersection[#, Total/@Subsets[#, {2, Length[#]}]]=={}&]], {n, 0, 15}] (* Gus Wiseman, Aug 09 2023 *)
CROSSREFS
These partitions have ranks A364531.
Search completed in 0.099 seconds
| 