A276024 -id:A276024 - cp's OEIS frontend

A367403 Number of integer partitions of n whose semi-sums do not cover an interval of positive integers.

0, 0, 0, 0, 0, 1, 2, 5, 9, 13, 22, 30, 46, 63, 91, 118, 167, 216, 290, 374, 490, 626, 810, 1022, 1297, 1628, 2051, 2551, 3176, 3929, 4845, 5963, 7311, 8932, 10892, 13227, 16035, 19395, 23397, 28156, 33803, 40523, 48439, 57832, 68876, 81903, 97212, 115198

Offset: 0

Gus Wiseman, Nov 17 2023

nonn

We define a semi-sum of a multiset to be any sum of a 2-element submultiset. This is different from sums of pairs of elements. For example, 2 is the sum of a pair of elements of {1}, but there are no semi-sums.

			The a(0) = 0 through a(9) = 13 partitions:
  .  .  .  .  .  (311)  (411)   (331)    (422)     (441)
                        (3111)  (421)    (431)     (522)
                                (511)    (521)     (531)
                                (4111)   (611)     (621)
                                (31111)  (3311)    (711)
                                         (4211)    (4311)
                                         (5111)    (5211)
                                         (41111)   (6111)
                                         (311111)  (33111)
                                                   (42111)
                                                   (51111)
                                                   (411111)
                                                   (3111111)

The complement for parts instead of sums is A034296, ranks A073491.
The complement for all sub-sums is A126796, ranks A325781, strict A188431.
For parts instead of sums we have A239955, ranks A073492.
For all subset-sums we have A365924, ranks A365830, strict A365831.
The complement is counted by A367402.
The strict case is A367411, complement A367410.
A000009 counts partitions covering an initial interval, ranks A055932.
A086971 counts semi-sums of prime indices.
A261036 counts complete partitions by maximum.
A276024 counts positive subset-sums of partitions, strict A284640.
Cf. A000041, A002033, A046663, A108917, A264401, A304792, A365543, A365658.

Table[Length[Select[IntegerPartitions[n], (d=Total/@Subsets[#,{2}];If[d=={}, {}, Range[Min@@d,Max@@d]]!=Union[d])&]], {n,0,15}]

A367410 Number of strict integer partitions of n whose semi-sums cover an interval of positive integers.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 4, 4, 6, 6, 7, 7, 8, 8, 11, 9, 11, 11, 12, 12, 15, 14, 15, 16, 16, 16, 19, 18, 19, 22, 21, 21, 24, 22, 25, 26, 26, 26, 30, 28, 29, 32, 31, 32, 37, 35, 36, 38, 39, 39, 43, 42, 43, 47, 46, 49, 51, 52, 51, 58

Offset: 0

Gus Wiseman, Nov 18 2023

nonn

We define a semi-sum of a multiset to be any sum of a 2-element submultiset. This is different from sums of pairs of elements. For example, 2 is the sum of a pair of elements of {1}, but there are no semi-sums.

			The partition y = (4,2,1) has semi-sums {3,5,6} which are missing 4, so y is not counted under a(7).
The a(1) = 1 through a(9) = 6 partitions:
  (1)  (2)  (3)    (4)    (5)    (6)      (7)    (8)    (9)
            (2,1)  (3,1)  (3,2)  (4,2)    (4,3)  (5,3)  (5,4)
                          (4,1)  (5,1)    (5,2)  (6,2)  (6,3)
                                 (3,2,1)  (6,1)  (7,1)  (7,2)
                                                        (8,1)
                                                        (4,3,2)

For parts instead of sums we have A001227:
- non-strict A034296, ranks A073491
- complement A238007
- non-strict complement A239955, ranks A073492
The non-binary version is A188431:
- non-strict A126796, ranks A325781
- complement A365831
- non-strict complement A365924, ranks A365830
The non-strict version is A367402.
The non-strict complement is A367403.
The complement is counted by A367411.
A000009 counts partitions covering an initial interval, ranks A055932.
A046663 counts partitions w/o submultiset summing to k, strict A365663.
A365543 counts partitions w/ submultiset summing to k, strict A365661.
Cf. A000041, A002033, A261036, A264401, A276024, A284640, A304792, A364272.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&(d=Total/@Subsets[#,{2}]; If[d=={},{}, Range[Min@@d, Max@@d]]==Union[d])&]], {n,0,30}]

A367411 Number of strict integer partitions of n whose semi-sums do not cover an interval of positive integers.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 4, 5, 8, 10, 14, 16, 23, 27, 35, 42, 52, 61, 75, 89, 106, 126, 149, 173, 204, 237, 274, 319, 369, 424, 490, 560, 642, 734, 838, 952, 1085, 1231, 1394, 1579, 1784, 2011, 2269, 2554, 2872, 3225, 3619, 4054, 4540, 5077, 5671, 6332

Offset: 0

Gus Wiseman, Nov 17 2023

nonn

We define a semi-sum of a multiset to be any sum of a 2-element submultiset. This is different from sums of pairs of elements. For example, 2 is the sum of a pair of elements of {1}, but there are no semi-sums.

			The partition y = (4,2,1) has semi-sums {3,5,6} which are missing 4, so y is counted under a(7).
The a(7) = 1 through a(13) = 10 partitions:
  (4,2,1)  (4,3,1)  (5,3,1)  (5,3,2)  (5,4,2)  (6,4,2)    (6,4,3)
           (5,2,1)  (6,2,1)  (5,4,1)  (6,3,2)  (6,5,1)    (6,5,2)
                             (6,3,1)  (6,4,1)  (7,3,2)    (7,4,2)
                             (7,2,1)  (7,3,1)  (7,4,1)    (7,5,1)
                                      (8,2,1)  (8,3,1)    (8,3,2)
                                               (9,2,1)    (8,4,1)
                                               (5,4,2,1)  (9,3,1)
                                               (6,3,2,1)  (10,2,1)
                                                          (6,4,2,1)
                                                          (7,3,2,1)

For parts instead of sums we have A238007:
- complement A001227
- non-strict complement A034296, ranks A073491
- non-strict  A239955, ranks A073492
The non-strict version is A367403.
The non-strict complement is A367402.
The complement is counted by A367410.
The non-binary version is A365831:
- non-strict complement A126796, ranks A325781
- complement A188431
- non-strict A365924, ranks A365830
A000009 counts partitions covering an initial interval, ranks A055932.
A046663 counts partitions w/o submultiset summing to k, strict A365663.
A365543 counts partitions w/ submultiset summing to k, strict A365661.
Cf. A000041, A002033, A261036, A264401, A276024, A284640, A304792, A364272.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&(d=Total/@Subsets[#, {2}];If[d=={},{}, Range[Min@@d,Max@@d]]!=Union[d])&]], {n,0,30}]

A301934 Number of positive subset-sum trees of weight n.

Original entry on oeis.org

1, 3, 14, 85, 586, 4331, 33545, 268521, 2204249

Offset: 1

Gus Wiseman, Mar 28 2018

A positive subset-sum tree with root x is either the symbol x itself, or is obtained by first choosing a positive subset-sum x <= (y_1,...,y_k) with k > 1 and then choosing a positive subset-sum tree with root y_i for each i = 1...k. The weight is the sum of the leaves. We write positive subset-sum trees in the form rootsum(branch,...,branch). For example, 4(1(1,3),2,2(1,1)) is a positive subset-sum tree with composite 4(1,1,1,2,3) and weight 8.

			The a(3) = 14 positive subset-sum trees:
3           3(1,2)       3(1,1,1)     3(1,2(1,1))
2(1,2)      2(1,1,1)     2(1,1(1,1))  2(1(1,1),1)  2(1,2(1,1))
1(1,2)      1(1,1,1)     1(1,1(1,1))  1(1(1,1),1)  1(1,2(1,1))

Cf. A000108, A000712, A108917, A122768, A262671, A262673, A275972, A276024, A284640, A299701, A301854, A301855, A301856, A301935.

A307699 Numbers k such that there is no integer partition of k with exactly k-1 submultisets.

Original entry on oeis.org

0, 1, 2, 6, 8, 12, 14, 18, 20, 24, 26, 30, 32, 38, 42, 44, 48, 50, 54, 60, 62, 66, 68, 72, 74, 80, 84, 86, 90, 92, 98, 102, 104, 108, 110, 114, 122, 126, 128, 132, 134, 138, 140, 146, 150, 152, 158, 164, 168, 170, 174, 180, 182, 186, 192, 194, 198, 200, 206

Offset: 1

Gus Wiseman, May 30 2019

nonn

After a(1) = 0, first differs from A229488 in lacking 56.
The number of submultisets of a partition is the product of its multiplicities, each plus one.
{a(n)-1} contains all odd numbers m = p*q*... such that gcd(p-1, q-1, ...) > 2. In particular, {a(n)-1} contains all powers of all primes > 3. Proof: If g is the greatest common divisor, then all factors of k are congruent to 1 modulo g, and thus all multiplicities of any valid multiset are divisible by g. However, the required sum is congruent to 2 modulo g, and so no such multiset can exist. - Charlie Neder, Jun 06 2019

			The sequence of positive terms together with their prime indices begins:
   1: {}
   2: {1}
   6: {1,2}
   8: {1,1,1}
  12: {1,1,2}
  14: {1,4}
  18: {1,2,2}
  20: {1,1,3}
  24: {1,1,1,2}
  26: {1,6}
  30: {1,2,3}
  32: {1,1,1,1,1}
  38: {1,8}
  42: {1,2,4}
  44: {1,1,5}
  48: {1,1,1,1,2}
  50: {1,3,3}
  54: {1,2,2,2}
  60: {1,1,2,3}
Partitions realizing the desired number of submultisets for each non-term are:
   3: (3)
   4: (22)
   5: (41)
   7: (511)
   9: (621)
  10: (4411)
  11: (71111)
  13: (9211)
  15: (9111111)
  16: (661111)
  17: (9521)
  19: (94411)
  21: (981111)
  22: (88111111)
  23: (32222222222)
  25: (99421)
  27: (3222222222222)
  28: (994411)
  29: (98222222)

Positions of zeros in A325836.

Cf. A002033, A088880, A088881, A098859, A108917, A126796, A276024, A325694, A325792, A325798, A325828, A325830, A325833, A325834, A325835.

Select[Range[50],Function[n,Select[IntegerPartitions[n], Times@@(1+Length/@Split[#])==n-1&]=={}]]

More terms from Alois P. Heinz, May 30 2019

A326035 Number of uniform knapsack partitions of n.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 6, 6, 9, 10, 12, 12, 17, 16, 20, 25, 27, 29, 35, 39, 44, 57, 53, 66, 75, 84, 84, 114, 112, 131, 133, 162, 167, 209, 192, 242, 250, 289, 279, 363, 348, 417, 404, 502, 487, 608, 557, 706, 682, 835, 773, 1004, 922, 1149, 1059, 1344, 1257, 1595

Offset: 0

Gus Wiseman, Jun 04 2019

nonn

An integer partition is uniform if all parts appear with the same multiplicity, and knapsack if every distinct submultiset has a different sum.

			The a(1) = 1 through a(8) = 9 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (32)     (33)      (43)       (44)
             (111)  (31)    (41)     (42)      (52)       (53)
                    (1111)  (11111)  (51)      (61)       (62)
                                     (222)     (421)      (71)
                                     (111111)  (1111111)  (521)
                                                          (2222)
                                                          (3311)
                                                          (11111111)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..650

Cf. A002033, A047966, A072774, A108917, A275972, A276024, A299702.

Cf. A325592, A325858, A326015, A326016, A326017, A326036, A326037.

sums[ptn_]:=sums[ptn]=If[Length[ptn]==1,ptn,Union@@(Join[sums[#],sums[#]+Total[ptn]-Total[#]]&/@Union[Table[Delete[ptn,i],{i,Length[ptn]}]])];
ks[n_]:=Select[IntegerPartitions[n],Length[sums[Sort[#]]]==Times@@(Length/@Split[#]+1)-1&];
Table[Length[Select[ks[n],SameQ@@Length/@Split[#]&]],{n,30}]

A347707 Number of distinct possible integer reverse-alternating products of integer partitions of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 8, 8, 9, 9, 11, 11, 13, 12, 14, 14, 15, 15, 18, 17, 19, 18, 20, 20, 22, 21, 25, 23, 26, 25, 28, 26, 29, 27, 31, 29, 32, 31, 34, 33, 35, 34, 38, 35, 41, 37, 42, 40, 43, 41, 45, 42, 46, 44, 48, 45, 50, 46, 52, 49, 53

Offset: 0

Gus Wiseman, Oct 13 2021

nonn

We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)). The reverse-alternating product is the alternating product of the reversed sequence.

			Representative partitions for each of the a(16) = 11 alternating products:
         (16) -> 16
     (14,1,1) -> 14
     (12,2,2) -> 12
     (10,3,3) -> 10
      (8,4,4) -> 8
  (9,3,2,1,1) -> 6
     (10,4,2) -> 5
     (12,3,1) -> 4
  (6,4,2,2,2) -> 3
     (10,5,1) -> 2
        (8,8) -> 1

The even-length version is A000035.
The non-reverse version is A028310.
The version for factorizations has special cases:
- no changes: A046951
- non-reverse: A046951
- non-integer: A038548
- odd-length: A046951 + A010052
- non-reverse non-integer: A347460
- non-integer odd-length: A347708
- non-reverse odd-length: A046951 + A010052
- non-reverse non-integer odd-length: A347708
The odd-length version is a(n) - A059841(n).
These partitions are counted by A347445, non-reverse A347446.
Counting non-integers gives A347462, non-reverse A347461.
A000041 counts partitions.
A027187 counts partitions of even length.
A027193 counts partitions of odd length.
A103919 counts partitions by sum and alternating sum, reverse A344612.
A119620 counts partitions with alternating product 1, ranked by A028982.
A276024 counts distinct positive subset-sums of partitions, strict A284640.
A304792 counts distinct subset-sums of partitions.
A325534 counts separable partitions, complement A325535.
A345926 counts possible alternating sums of permutations of prime indices.
Cf. A000070, A002033, A002219, A108917, A122768, A325765, A344654, A344740, A347443, A347444, A347448, A347449.

revaltprod[q_]:=Product[Reverse[q][[i]]^(-1)^(i-1),{i,Length[q]}];
Table[Length[Select[Union[revaltprod/@IntegerPartitions[n]],IntegerQ]],{n,0,30}]

A304796 Number of special sums of integer partitions of n.

Original entry on oeis.org

1, 2, 5, 10, 18, 32, 51, 82, 122, 188, 262, 392, 529, 750, 997, 1404, 1784, 2452, 3123, 4164, 5239, 6916, 8499, 11112, 13693, 17482, 21257, 27162, 32581, 41114, 49606, 61418, 73474, 91086, 107780, 132874, 157359, 191026, 225159, 274110, 320691, 386722, 453875

Offset: 0

Gus Wiseman, May 18 2018

nonn

A special sum of an integer partition y is a number n >= 0 such that exactly one submultiset of y sums to n.

			The a(4) = 18 special positive subset-sums:
0<=(4), 4<=(4),
0<=(22), 2<=(22), 4<=(22),
0<=(31), 1<=(31), 3<=(31), 4<=(31),
0<=(211), 1<=(211), 3<=(211), 4<=(211),
0<=(1111), 1<=(1111), 2<=(1111), 3<=(1111), 4<=(1111).

Cf. A000712, A108917, A122768, A275972, A276024, A284640, A299701, A299702, A299729, A301829, A301830, A301854.

uqsubs[y_]:=Join@@Select[GatherBy[Union[Subsets[y]],Total],Length[#]===1&];
Table[Total[Length/@uqsubs/@IntegerPartitions[n]],{n,25}]

a(n) = A301854(n) + A000041(n).

More terms from Alois P. Heinz, May 18 2018

a(36)-a(42) from Chai Wah Wu, Sep 26 2023

A316222 Number of positive subset-sum triangles whose composite is a positive subset-sum of an integer partition of n.

Original entry on oeis.org

1, 5, 20, 74, 258, 855, 2736, 8447

Offset: 1

Gus Wiseman, Jun 27 2018

A positive subset-sum is a pair (h,g), where h is a positive integer and g is an integer partition, such that some submultiset of g sums to h. A triangle consists of a root sum r and a sequence of positive subset-sums ((h_1,g_1),...,(h_k,g_k)) such that the sequence (h_1,...,h_k) is weakly decreasing and has a submultiset summing to r.

			We write positive subset-sum triangles in the form rootsum(branch,...,branch). The a(2) = 5 positive subset-sum triangles:
  2(2(2))
  1(1(1,1))
  2(2(1,1))
  1(1(1),1(1))
  2(1(1),1(1))

Cf. A063834, A262671, A269134, A276024, A281113, A301934, A301935, A316219, A316220.

A316399 Number of strict integer partitions of n such that not every subset has a different average.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 2, 1, 1, 5, 3, 5, 9, 10, 10, 20, 20, 27, 32, 39, 43, 69, 65, 83, 99, 133, 136, 176, 191, 252, 274, 332, 363, 475, 503, 602, 677, 832, 893, 1067, 1186, 1418, 1561, 1797, 2000, 2384, 2602, 2992, 3315, 3853, 4226, 4826, 5383, 6121, 6763

Offset: 1

Gus Wiseman, Jul 01 2018

nonn

			The a(12) = 5 partitions are (5,4,3), (6,4,2), (7,4,1), (5,4,2,1), (6,3,2,1).

Cf. A000009, A108917, A275972, A276024, A284640, A299702, A301899, A301900, A316271, A316313, A316314, A316400, A316402.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!UnsameQ@@Mean/@Union[Subsets[#]]&]],{n,60}]

a(n) = A000009(n) - A316313(n).

cp's OEIS Frontend

A367403 Number of integer partitions of n whose semi-sums do not cover an interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367410 Number of strict integer partitions of n whose semi-sums cover an interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367411 Number of strict integer partitions of n whose semi-sums do not cover an interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A301934 Number of positive subset-sum trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A307699 Numbers k such that there is no integer partition of k with exactly k-1 submultisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A326035 Number of uniform knapsack partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A347707 Number of distinct possible integer reverse-alternating products of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A304796 Number of special sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A316222 Number of positive subset-sum triangles whose composite is a positive subset-sum of an integer partition of n.

Views

Author

Keywords

Comments