A364911 -id:A364911 - cp's OEIS frontend

A367404 Triangle read by rows where T(n,k) is the number of integer partitions of n with a semi-sum k.

1, 1, 1, 2, 1, 2, 3, 2, 2, 2, 5, 3, 4, 2, 3, 7, 5, 6, 4, 3, 3, 11, 7, 9, 6, 6, 3, 4, 15, 11, 13, 10, 9, 6, 4, 4, 22, 15, 20, 13, 15, 9, 8, 4, 5, 30, 22, 27, 21, 21, 15, 12, 8, 5, 5, 42, 30, 39, 28, 30, 21, 20, 12, 10, 5, 6, 56, 42, 53, 41, 42, 33, 28, 20, 15, 10, 6, 6

Offset: 2

Gus Wiseman, Nov 17 2023

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 = (3,2,1,1) has semi-sum 3 = 2+1, but no semi-sum 6, so y is counted under T(7,3) but not under T(7,6).
Triangle begins:
   1
   1   1
   2   1   2
   3   2   2   2
   5   3   4   2   3
   7   5   6   4   3   3
  11   7   9   6   6   3   4
  15  11  13  10   9   6   4   4
  22  15  20  13  15   9   8   4   5
  30  22  27  21  21  15  12   8   5   5
  42  30  39  28  30  21  20  12  10   5   6
  56  42  53  41  42  33  28  20  15  10   6   6
  77  56  73  55  60  42  44  28  25  15  12   6   7
Row n = 7 counts the following partitions:
  (511)      (421)     (331)    (421)   (511)  (61)
  (4111)     (3211)    (322)    (4111)  (421)  (52)
  (3211)     (2221)    (3211)   (322)   (331)  (43)
  (31111)    (22111)   (31111)  (3211)
  (22111)    (211111)  (2221)
  (211111)             (22111)
  (1111111)

Column k = 0 is A000041.
Column n = k is A004526.
The complement for all submultisets is A046663, strict A365663.
For subsets instead of partitions we have A365541, non-binary A365381.
The non-binary version is A365543, strict A365661.
Row sums are A366738.
The strict case is A367405.
Cf. A122768, A108917, A299701, A304792, A364272, A364911, A365658.

Table[Length[Select[IntegerPartitions[n], MemberQ[Total/@Subsets[#, {2}],k]&]], {n,2,10}, {k,2,n}]

A367405 Triangle read by rows where T(n,k) is the number of strict integer partitions of n with two distinct parts summing to k.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 1, 1, 1, 2, 1, 0, 1, 1, 3, 1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 4, 2, 2, 3, 2, 3, 2, 3, 4, 2, 2, 3, 2, 3, 3, 3, 3, 5, 3, 2, 4, 3, 4, 4, 5, 3, 4, 5, 3, 3, 5, 4, 4, 5, 5, 5, 4, 4, 6, 4, 3, 6, 5, 6, 5, 7, 5, 7, 4, 5, 6, 5, 5, 7, 7, 8, 7, 8, 8, 7, 7, 5, 5, 7

Offset: 3

Gus Wiseman, Nov 18 2023

			Triangle begins:
  1
  0  1
  0  0  2
  1  1  1  2
  1  0  1  1  3
  1  1  1  1  2  3
  1  1  1  2  2  2  4
  2  2  3  2  3  2  3  4
  2  2  3  2  3  3  3  3  5
  3  2  4  3  4  4  5  3  4  5
  3  3  5  4  4  5  5  5  4  4  6
  4  3  6  5  6  5  7  5  7  4  5  6
  5  5  7  7  8  7  8  8  7  7  5  5  7
  6  5  9  8 10  7 10  9 10  7  9  5  6  7
  7  7 10 10 12 11 11 11 12 10  9  9  6  6  8
  9  7 13 11 15 12 13 13 15 13 13  9 11  6  7  8
Row n = 9 counts the following strict partitions:
  (6,2,1)  (5,3,1)  (4,3,2)  (5,3,1)  (6,2,1)  (6,2,1)  (8,1)
                             (4,3,2)  (4,3,2)  (5,3,1)  (7,2)
                                                        (6,3)
                                                        (5,4)
Row n = 13 counts the following strict partitions (A=10, B=11, C=12):
  A21   931   841   751   652   751   841   931   A21  A21  C1
  7321  7321  832   742   643   7321  742   832   832  931  B2
  6421  5431  7321  6421  6421  652   7321  7321  742  841  A3
              6421  5431  5431  6421  643   643   652  751  94
              5431              5431  5431  6421            85
                                                            76

Column n = k is A004526.
Column k = 3 is A025148.
For subsets instead of partitions we have A365541, non-binary A365381.
The non-binary version is A365661, non-strict A365543.
The non-binary complement is A365663, non-strict A046663.
Row sums are A366741, non-strict A366738.
The non-strict version is A367404.
Cf. A000041, A088809, A093971, A122768, A108917, A284640, A304792, A364272, A364911, A365658.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&MemberQ[Total/@Subsets[#,{2}], k]&]], {n,3,10}, {k,3,n}]

A365068 Number of integer partitions of n with some part that can be written as a nonnegative linear combination of the other distinct parts.

Original entry on oeis.org

0, 0, 0, 1, 2, 4, 7, 10, 16, 23, 34, 44, 67, 85, 119, 157, 210, 268, 360, 453, 592, 748, 956, 1195, 1520, 1883, 2365, 2920, 3628, 4451, 5494, 6702, 8211, 9976, 12147, 14666, 17776, 21389, 25774, 30887, 37035, 44224, 52819, 62836, 74753, 88614, 105062, 124160

Offset: 0

Gus Wiseman, Aug 27 2023

nonn

These may be called "non-binary nonnegative combination-full" partitions.

Does not necessarily include all non-strict partitions (A047967).

			The partition (5,4,3,3) has no part that can be written as a nonnegative linear combination of the others, so is not counted under a(15).
The partition (6,4,3,2) has 6 = 1*2 + 1*4, so is counted under a(15). The combinations 6 = 2*3 = 3*2 and 4 = 2*2 can also be used.
The a(3) = 1 through a(8) = 16 partitions:
  (21)  (31)   (41)    (42)     (61)      (62)
        (211)  (221)   (51)     (331)     (71)
               (311)   (321)    (421)     (422)
               (2111)  (411)    (511)     (431)
                       (2211)   (2221)    (521)
                       (3111)   (3211)    (611)
                       (21111)  (4111)    (3221)
                                (22111)   (3311)
                                (31111)   (4211)
                                (211111)  (5111)
                                          (22211)
                                          (32111)
                                          (41111)
                                          (221111)
                                          (311111)
                                          (2111111)

The complement for sums instead of combinations is A237667, binary A236912.
For sums instead of combinations we have A237668, binary A237113.
The strict case is A364839, complement A364350.
Allowing equal parts in the combination gives A364913.
For subsets instead of partitions we have A364914, complement A326083.
The complement is A364915.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A323092 counts double-free partitions, ranks A320340.
A364912 counts linear combinations of partitions of k.
Cf. A108917, A151897, A364272, A364910, A364911, A365006.

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], Function[ptn,Or@@Table[combs[ptn[[k]], DeleteCases[ptn,ptn[[k]]]]!={}, {k,Length[ptn]}]]]],{n,0,5}]

from sympy.utilities.iterables import partitions
def A365068(n):
    if n <= 1: return 0
    alist, c = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)], 0
    for p in partitions(n,k=n-1):
        s = set(p)
        if any(set(t).issubset(s-{q}) for q in s for t in alist[q]):
            c += 1
    return c # Chai Wah Wu, Sep 20 2023

a(31)-a(47) from Chai Wah Wu, Sep 20 2023

A364908 Number of ways to write n as a nonnegative linear combination of an integer composition of n.

Original entry on oeis.org

1, 1, 4, 15, 70, 314, 1542, 7428, 36860, 182911, 917188, 4612480, 23323662, 118273428, 601762636, 3069070533, 15689123386, 80356953555, 412300910566, 2118715503962, 10902791722490, 56175374185014, 289766946825180, 1496239506613985, 7733302967423382

Offset: 0

Gus Wiseman, Aug 22 2023

nonn

A way of writing n as a (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).

			The a(3) = 15 ways to write 3 as a nonnegative linear combination of an integer composition of 3:
  1*3  0*2+3*1  1*1+1*2  0*1+0*1+3*1
       1*2+1*1  3*1+0*2  0*1+1*1+2*1
                         0*1+2*1+1*1
                         0*1+3*1+0*1
                         1*1+0*1+2*1
                         1*1+1*1+1*1
                         1*1+2*1+0*1
                         2*1+0*1+1*1
                         2*1+1*1+0*1
                         3*1+0*1+0*1

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

The case with no zero coefficients is A011782.
The version for partitions is A364907, strict A364910.
The strict case is A364909.
A000041 counts integer partitions, strict A000009.
A011782 counts compositions, strict A032020.
A097805 counts compositions by length, strict A072574.
A116861 = positive linear combinations of strict ptns of k, reverse A364916.
A365067 = nonnegative linear combinations of strict partitions of k.
A364912 = positive linear combinations of partitions of k.
A364916 = positive linear combinations of strict partitions of k.
Cf. A364350, A364839, A364906, A364911, A364914, A365002, A365004.

b:= proc(n, m) option remember; `if`(n=0, `if`(m=0, 1, 0),
      add(add(b(n-i, m-i*j), j=0..m/i), i=1..n))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 28 2024

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

a(8)-a(24) from Alois P. Heinz, Jan 28 2024

A365003 Heinz numbers of integer partitions where the sum of all parts is twice the sum of distinct parts.

Original entry on oeis.org

1, 4, 9, 25, 36, 48, 49, 100, 121, 160, 169, 196, 225, 289, 361, 441, 448, 484, 529, 567, 676, 750, 810, 841, 900, 961, 1080, 1089, 1156, 1200, 1225, 1369, 1408, 1440, 1444, 1521, 1681, 1764, 1849, 1920, 2116, 2209, 2268, 2352, 2601, 2809, 3024, 3025, 3159

Offset: 1

Gus Wiseman, Aug 23 2023

nonn

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The prime indices of 750 are {1,2,3,3,3}, with sum 12, while the distinct prime indices {1,2,3} have sum 6, so 750 is in the sequence.
The terms together with their prime indices begin:
     1: {}
     4: {1,1}
     9: {2,2}
    25: {3,3}
    36: {1,1,2,2}
    48: {1,1,1,1,2}
    49: {4,4}
   100: {1,1,3,3}
   121: {5,5}
   160: {1,1,1,1,1,3}
   169: {6,6}
   196: {1,1,4,4}
   225: {2,2,3,3}
   289: {7,7}
   361: {8,8}
   441: {2,2,4,4}
   448: {1,1,1,1,1,1,4}

The LHS is A056239 (sum of prime indices).
The RHS is twice A066328.
Partitions of this type are counted by A364910.
A000041 counts integer partitions, strict A000009.
A001222 counts prime indices, distinct A001221.
A112798 lists prime indices, distinct A304038.
A116861 counts partitions by sum and sum of distinct parts.
A323092 counts double-free partitions, ranks A320340.
Cf. A364350, A364839, A364906, A364907, A364911, A364916.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],Total[prix[#]]==2*Total[Union[prix[#]]]&]

A056239(a(n)) = 2*A066328(a(n)).

A365072 Number of integer partitions of n such that no distinct part can be written as a (strictly) positive linear combination of the other distinct parts.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 5, 6, 8, 9, 17, 15, 31, 34, 53, 65, 109, 117, 196, 224, 328, 405, 586, 673, 968, 1163, 1555, 1889, 2531, 2986, 3969, 4744, 6073, 7333, 9317, 11053, 14011, 16710, 20702, 24714, 30549, 36127, 44413, 52561, 63786, 75583, 91377, 107436, 129463

Offset: 0

Gus Wiseman, Aug 31 2023

nonn

We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.

			The a(1) = 1 through a(8) = 6 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (32)     (33)      (43)       (44)
                    (1111)  (11111)  (222)     (52)       (53)
                                     (111111)  (322)      (332)
                                               (1111111)  (2222)
                                                          (11111111)
The a(11) = 17 partitions:
  (11)  (9,2)  (7,2,2)  (5,3,2,1)  (4,3,2,1,1)  (1,1,1,1,1,1,1,1,1,1,1)
        (8,3)  (6,3,2)  (5,2,2,2)  (3,2,2,2,2)
        (7,4)  (5,4,2)  (4,3,2,2)
        (6,5)  (5,3,3)  (3,3,3,2)
               (4,4,3)

The nonnegative version is A364915, strict A364350.
The strict case is A365006.
For subsets instead of partitions we have A365044, complement A365043.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A237667 counts sum-free partitions, binary A236912.
A364912 counts positive linear combinations of partitions.
A365068 counts combination-full partitions, strict A364839.
Cf. A085489, A108917, A151897, A325862, A364272, A364910, A364911, A364913.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]}, Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Union/@IntegerPartitions[n], Function[ptn,!Or@@Table[combp[ptn[[k]],Delete[ptn,k]]!={}, {k,Length[ptn]}]]@*Union]],{n,0,15}]

from sympy.utilities.iterables import partitions
def A365072(n):
    if n <= 1: return 1
    alist = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)]
    c = 1
    for p in partitions(n,k=n-1):
        s = set(p)
        for q in s:
            if tuple(sorted(s-{q})) in alist[q]:
                break
        else:
            c += 1
    return c # Chai Wah Wu, Sep 20 2023

a(31)-a(49) from Chai Wah Wu, Sep 20 2023

A365660 Number of integer partitions of 2n with exactly n distinct sums of nonempty submultisets.

Original entry on oeis.org

1, 1, 1, 3, 2, 6, 6, 16, 12, 20, 26, 59, 45, 79, 94, 186, 142, 231, 244, 442, 470, 616, 746, 1340, 1053, 1548, 1852, 2780, 2826, 3874, 4320, 6617, 6286, 7924, 9178, 13180, 13634, 17494, 20356, 28220, 29176, 37188, 41932, 56037

Offset: 0

Gus Wiseman, Sep 16 2023

Are n = 1, 2, 4 the only n such that none of these partitions has 1?

Are n = 2, 4, 5, 8, 9 the only n such that none of these partitions is strict?

			The partition (433) has sums 3, 4, 6, 7, 10 so is counted under a(5).
The a(1) = 1 through a(7) = 16 partitions:
(2)  (2,2)  (4,2)    (4,2,2)    (4,3,3)      (6,4,2)        (6,5,3)
            (5,1)    (2,2,2,2)  (4,4,2)      (6,5,1)        (8,4,2)
            (2,2,2)             (6,2,2)      (4,4,2,2)      (8,5,1)
                                (8,1,1)      (6,2,2,2)      (9,3,2)
                                (4,2,2,2)    (4,2,2,2,2)    (9,4,1)
                                (2,2,2,2,2)  (2,2,2,2,2,2)  (10,3,1)
                                                            (11,2,1)
                                                            (4,4,4,2)
                                                            (5,3,3,3)
                                                            (6,4,2,2)
                                                            (8,2,2,2)
                                                            (11,1,1,1)
                                                            (4,4,2,2,2)
                                                            (6,2,2,2,2)
                                                            (4,2,2,2,2,2)
                                                            (2,2,2,2,2,2,2)

For n instead of 2n we have A126796.
Central column n = 2k of A365658.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A002219 counts partitions of 2n with a submultiset summing to n.
A046663 counts partitions of n w/o a submultiset of sum k, strict A365663.
A122768 counts distinct nonempty submultisets of partitions.
A299701 counts sums of submultisets of prime indices, of partitions A304792.
A364272 counts sum-full strict partitions, sum-free A364349.
A365543 counts partitions of n w/ a submultiset of sum k, strict A365661.
Cf. A000041, A008967, A095944, A364911, A365376, A365377.

msubs[y_]:=primeMS/@Divisors[Times@@Prime/@y];
Table[Length[Select[IntegerPartitions[2n], Length[Union[Total/@Rest[msubs[#]]]]==n&]],{n,0,10}]

from collections import Counter
from sympy.utilities.iterables import partitions, multiset_combinations
def A365660(n):
    c = 0
    for p in partitions(n<<1):
        q, s = list(Counter(p).elements()), set()
        for l in range(1,len(q)+1):
            for k in multiset_combinations(q,l):
                s.add(sum(k))
                if len(s) > n:
                    break
            else:
                continue
            break
        if len(s)==n:
            c += 1
    return c # Chai Wah Wu, Sep 20 2023

a(21)-a(38) from Chai Wah Wu, Sep 20 2023

a(39)-a(43) from Chai Wah Wu, Sep 21 2023

A367108 Triangle read by rows where T(n,k) is the number of integer partitions of n with a unique submultiset summing to k.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 2, 2, 3, 5, 3, 2, 3, 5, 7, 5, 4, 4, 5, 7, 11, 7, 6, 3, 6, 7, 11, 15, 11, 8, 7, 7, 8, 11, 15, 22, 15, 12, 10, 4, 10, 12, 15, 22, 30, 22, 16, 14, 12, 12, 14, 16, 22, 30, 42, 30, 22, 17, 17, 6, 17, 17, 22, 30, 42, 56, 42, 30, 25, 23, 20, 20, 23, 25, 30, 42, 56

Offset: 1

Gus Wiseman, Nov 18 2023

			Triangle begins:
   1
   1   1
   2   1   2
   3   2   2   3
   5   3   2   3   5
   7   5   4   4   5   7
  11   7   6   3   6   7  11
  15  11   8   7   7   8  11  15
  22  15  12  10   4  10  12  15  22
  30  22  16  14  12  12  14  16  22  30
  42  30  22  17  17   6  17  17  22  30  42
  56  42  30  25  23  20  20  23  25  30  42  56
  77  56  40  31  30  27   7  27  30  31  40  56  77
Row n = 5 counts the following partitions:
  (5)      (41)     (32)     (32)     (41)     (5)
  (41)     (311)    (311)    (311)    (311)    (41)
  (32)     (221)    (221)    (221)    (221)    (32)
  (311)    (2111)   (11111)  (11111)  (2111)   (311)
  (221)    (11111)                    (11111)  (221)
  (2111)                                       (2111)
  (11111)                                      (11111)
Row n = 6 counts the following partitions:
  (6)       (51)      (42)      (33)      (42)      (51)      (6)
  (51)      (411)     (411)     (2211)    (411)     (411)     (51)
  (42)      (321)     (321)     (111111)  (321)     (321)     (42)
  (411)     (3111)    (3111)              (3111)    (3111)    (411)
  (33)      (2211)    (222)               (222)     (2211)    (33)
  (321)     (21111)   (111111)            (111111)  (21111)   (321)
  (3111)    (111111)                                (111111)  (3111)
  (222)                                                       (222)
  (2211)                                                      (2211)
  (21111)                                                     (21111)
  (111111)                                                    (111111)

Columns k = 0 and k = n are A000041(n).
Column k = 1 and k = n-1 are A000041(n-1).
Column k = 2 appears to be 2*A027336(n).
The version for non-subset-sums is A046663, strict A365663.
Diagonal n = 2k is A108917, complement A366754.
Row sums are A304796, non-unique version A304792.
The non-unique version is A365543.
Cf. A002219, A122768, A275972, A299702, A299729, A301854, A364272, A364911, A365658, A365661, A367094.

Table[Length[Select[IntegerPartitions[n], Count[Total/@Union[Subsets[#]], k]==1&]], {n,0,10}, {k,0,n}]

A367094(n,1) = A108917(n).

cp's OEIS Frontend

A367404 Triangle read by rows where T(n,k) is the number of integer partitions of n with a semi-sum k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A367405 Triangle read by rows where T(n,k) is the number of strict integer partitions of n with two distinct parts summing to k.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A365068 Number of integer partitions of n with some part that can be written as a nonnegative linear combination of the other distinct parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A364908 Number of ways to write n as a nonnegative linear combination of an integer composition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A365003 Heinz numbers of integer partitions where the sum of all parts is twice the sum of distinct parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A365072 Number of integer partitions of n such that no distinct part can be written as a (strictly) positive linear combination of the other distinct parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A365660 Number of integer partitions of 2n with exactly n distinct sums of nonempty submultisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A367108 Triangle read by rows where T(n,k) is the number of integer partitions of n with a unique submultiset summing to k.

Views

Author

Keywords

Examples

Crossrefs

Programs