Displaying 1-10 of 56 results found.
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.
Triangle read by rows: T(n,k) is the number of partitions of n such that the sum of the parts, counted without multiplicities, is equal to k (n>=1, k>=1).
+10
72
1, 1, 1, 1, 0, 2, 1, 1, 1, 2, 1, 0, 2, 1, 3, 1, 1, 3, 1, 1, 4, 1, 0, 3, 2, 2, 2, 5, 1, 1, 3, 3, 2, 4, 2, 6, 1, 0, 5, 2, 3, 4, 4, 3, 8, 1, 1, 4, 3, 4, 7, 4, 5, 3, 10, 1, 0, 5, 3, 4, 7, 7, 6, 6, 5, 12, 1, 1, 6, 4, 3, 12, 6, 8, 7, 9, 5, 15, 1, 0, 6, 4, 5, 10, 10, 9, 10, 11, 10, 7, 18, 1, 1, 6, 4, 5, 15, 11, 13, 9, 16, 11, 13, 8, 22
COMMENTS
Conjecture: Reverse the rows of the table to get an infinite lower-triangular matrix b with 1's on the main diagonal. The third diagonal of the inverse of b is minus A137719. - George Beck, Oct 26 2019
Proof: The reversed rows yield the matrix I+N where N is strictly lower triangular, N[i,j] = 0 for j >= i, having its 2nd diagonal equal to the 2nd column (1, 0, 1, 0, 1, ...): N[i+1,i] = A000035(i), i >= 1, and 3rd diagonal equal to the 3rd column of this triangle, (2, 1, 2, 3, 3, 3, ...): N[i+2,i] = A137719(i), i >= 1. It is known that (I+N)^-1 = 1 - N + N^2 - N^3 +- .... Here N^2 has not only the second but also the 3rd diagonal zero, because N^2[i+2,i] = N[i+2,i+1]*N[i+1,i] = A000035(i+1)* A000035(i) = 0. Therefore the 3rd diagonal of (I+N)^-1 is equal to - A137719 without leading 0. - M. F. Hasler, Oct 27 2019
Also the number of ways to write n-k as a nonnegative linear combination of a strict integer partition of k. Also the number of ways to write n as a (strictly) positive linear combination of a strict integer partition of k. Row n=7 counts the following:
7*1 . 1*2+5*1 1*3+4*1 1*3+2*2 1*5+2*1 1*7
2*2+3*1 2*3+1*1 1*4+3*1 1*3+1*2+2*1 1*4+1*3
3*2+1*1 1*5+1*2
1*6+1*1
1*4+1*2+1*1
(End)
FORMULA
G.f.: -1 + Product_{j>=1} (1 + t^j*x^j/(1-x^j)).
Sum_{k=1..n} k*T(n,k) = A014153(n-1).
EXAMPLE
T(10,7) = 4 because we have [6,1,1,1,1], [4,3,3], [4,2,2,1,1] and [4,2,1,1,1,1] (6+1=4+3=4+2+1=7).
Triangle starts:
1;
1, 1;
1, 0, 2;
1, 1, 1, 2;
1, 0, 2, 1, 3;
1, 1, 3, 1, 1, 4;
1, 0, 3, 2, 2, 2, 5;
1, 1, 3, 3, 2, 4, 2, 6;
1, 0, 5, 2, 3, 4, 4, 3, 8;
1, 1, 4, 3, 4, 7, 4, 5, 3, 10;
1, 0, 5, 3, 4, 7, 7, 6, 6, 5, 12;
1, 1, 6, 4, 3, 12, 6, 8, 7, 9, 5, 15;
...
MAPLE
g:= -1+product(1+t^j*x^j/(1-x^j), j=1..40): gser:= simplify(series(g, x=0, 18)): for n from 1 to 14 do P[n]:=sort(coeff(gser, x^n)) od: for n from 1 to 14 do seq(coeff(P[n], t^j), j=1..n) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, i) option remember; local f, g, j;
if n=0 then [1] elif i<1 then [ ] else f:= b(n, i-1);
for j to n/i do
f:= zip((x, y)->x+y, f, [0$i, b(n-i*j, i-1)[]], 0)
od; f
fi
end:
T:= n-> subsop(1=NULL, b(n, n))[]:
MATHEMATICA
max = 14; s = Series[-1+Product[1+t^j*x^j/(1-x^j), {j, 1, max}], {x, 0, max}, {t, 0, max}] // Normal; t[n_, k_] := SeriesCoefficient[s, {x, 0, n}, {t, 0, k}]; Table[t[n, k], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 17 2014 *)
Table[Length[Select[IntegerPartitions[n], Total[Union[#]]==k&]], {n, 0, 10}, {k, 0, n}] (* Gus Wiseman, Aug 29 2023 *)
PROG
(PARI) A116861(n, k, s=0)={forpart(X=n, vecsum(Set(X))==k&&s++, k); s} \\ M. F. Hasler, Oct 27 2019
CROSSREFS
Cf. A114638 (count partitions with #parts = sum(distinct parts)).
For subsets instead of partitions we have A026820.
This statistic is ranked by A066328.
Partial sums of columns are columns of A364911.
Same as A364916 (offset 0) with rows reversed.
A364912 counts linear combinations of partitions.
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.
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 some part is a sum of two or more other parts.
+10
52
0, 0, 0, 0, 1, 1, 4, 4, 10, 13, 23, 27, 49, 60, 93, 115, 170, 210, 300, 370, 510, 632, 846, 1031, 1359, 1670, 2159, 2630, 3355, 4082, 5130, 6220, 7739, 9360, 11555, 13889, 16991, 20402, 24824, 29636, 35855, 42707, 51309, 60955, 72896, 86328, 102826, 121348
COMMENTS
These are partitions containing the sum of some non-singleton submultiset of the parts, a variation of non-binary sum-full partitions where parts cannot be re-used, ranked by A364532. The complement is counted by A237667. The binary version is A237113, or A363225 with re-usable parts. This sequence is weakly increasing. - Gus Wiseman, Aug 12 2023
EXAMPLE
a(6) = 4 counts these partitions: 123, 1113, 1122, 11112.
The a(0) = 0 through a(9) = 13 partitions:
. . . . (211) (2111) (321) (3211) (422) (3321)
(2211) (22111) (431) (4221)
(3111) (31111) (3221) (4311)
(21111) (211111) (4211) (5211)
(22211) (32211)
(32111) (33111)
(41111) (42111)
(221111) (222111)
(311111) (321111)
(2111111) (411111)
(2211111)
(3111111)
(21111111)
(End)
MATHEMATICA
z = 20; m = Map[Count[Map[MemberQ[#, Apply[Alternatives, Map[Apply[Plus, #] &, DeleteDuplicates[DeleteCases[Subsets[#], _?(Length[#] < 2 &)]]]]] &, IntegerPartitions[#]], False] &, Range[z]]; PartitionsP[Range[z]] - m
Table[Length[Select[IntegerPartitions[n], Intersection[#, Total/@Subsets[#, {2, Length[#]}]]!={}&]], {n, 0, 15}] (* Gus Wiseman, Aug 12 2023 *)
CROSSREFS
These partitions have ranks A364532.
For subsets instead of partitions we have A364534, complement A151897.
A299701 counts distinct subset-sums of prime indices.
Number of subsets of {1..n} containing some element equal to the sum of two or more distinct other elements. A variation of sum-full subsets without re-used elements.
+10
52
0, 0, 0, 1, 3, 10, 27, 68, 156, 357, 775, 1667, 3505, 7303, 15019, 30759, 62489, 126619, 255542, 514721, 1034425, 2076924, 4164650, 8346306, 16715847, 33467324, 66982798, 134040148, 268179417, 536510608, 1073226084, 2146759579, 4293930436, 8588485846, 17177799658
EXAMPLE
The a(0) = 0 through a(5) = 10 subsets:
. . . {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}
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], Intersection[#, Total/@Subsets[#, {2, Length[#]}]]!={}&]], {n, 0, 10}]
CROSSREFS
The complement is counted by A151897.
A236912 counts sum-free partitions w/o re-used parts, complement A237113.
Cf. A007865, A093971, A323092, A325862, A326083, A363225, A364345, A364346, A364348, A364350, A364533, A364670.
Number of integer partitions of n containing three parts (a,b,c) (repeats allowed) such that a + b = c. A variation of sum-full partitions.
+10
50
0, 0, 0, 1, 1, 2, 4, 5, 9, 14, 21, 29, 43, 58, 81, 109, 148, 195, 263, 339, 445, 574, 744, 942, 1209, 1515, 1923, 2399, 3005, 3721, 4629, 5693, 7024, 8589, 10530, 12804, 15596, 18876, 22870, 27538, 33204, 39816, 47766, 57061, 68161, 81099, 96510, 114434, 135634
COMMENTS
Note that, by this definition, the partition (2,1) is sum-full, because (1,1,2) is a triple satisfying a + b = c.
EXAMPLE
The a(3) = 1 through a(9) = 14 partitions:
(21) (211) (221) (42) (421) (422) (63)
(2111) (321) (2221) (431) (432)
(2211) (3211) (521) (621)
(21111) (22111) (3221) (3321)
(211111) (4211) (4221)
(22211) (4311)
(32111) (5211)
(221111) (22221)
(2111111) (32211)
(42111)
(222111)
(321111)
(2211111)
(21111111)
MATHEMATICA
Table[Length[Select[IntegerPartitions[n], Select[Tuples[#, 3], #[[1]]+#[[2]]==#[[3]]&]!={}&]], {n, 0, 15}]
PROG
(Python)
from collections import Counter
from itertools import combinations_with_replacement
from sympy.utilities.iterables import partitions
def A363225(n): return sum(1 for p in partitions(n) if any(q[0]+q[1]==q[2] for q in combinations_with_replacement(sorted(Counter(p).elements()), 3))) # Chai Wah Wu, Sep 21 2023
CROSSREFS
For subsets of {1..n} we have A093971, A088809 without re-using parts.
The complement for subsets is A007865, A085489 without re-using parts.
For sums of any length > 1 (without re-usable parts) we have A237668, complement A237667.
The strict linear combination-free version is A364350.
Search completed in 0.050 seconds
|