A364910 -id:A364910 - cp's OEIS frontend

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

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

A364909 Number of ways to write n as a nonnegative linear combination of a strict integer composition of n.

Original entry on oeis.org

1, 1, 1, 5, 5, 7, 51, 45, 89, 109, 709, 733, 1495, 1935, 3119, 13785, 16611, 29035, 44611, 68733, 95193, 372897, 435007, 781345, 1177181, 1866659, 2600537, 3906561, 12052631, 14610799, 25407653, 37652265, 59943351, 84060993, 128112805, 172172117, 480353257, 578740011

Offset: 0

Gus Wiseman, Aug 18 2023

nonn

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).

			The a(0) = 1 through a(5) = 7 ways:
  .  1*1  1*2  1*3      1*4      1*5
               0*2+3*1  0*3+4*1  0*4+5*1
               1*1+1*2  1*1+1*3  1*1+1*4
               1*2+1*1  1*3+1*1  1*2+1*3
               3*1+0*2  4*1+0*3  1*3+1*2
                                 1*4+1*1
                                 5*1+0*4

The case with no zero coefficients is A032020.
The version for partitions is A364907, strict A364910(n) = A364916(n,n).
The non-strict version is A364908.
A000041 counts integer partitions, strict A000009.
A011782 counts compositions, strict A032020.
A008284 counts partitions by length, strict A008289.
A097805 counts compositions by length, strict A072574.
Cf. A116861, A364350, A364839, A364906, A364912, A364914, A365002, A365004.

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/@Select[IntegerPartitions[n],UnsameQ@@#&]}]],{n,0,5}]

from math import factorial
from sympy.utilities.iterables import partitions
def A364909(n):
    if n == 0: return 1
    aset = tuple(set(p) for p in partitions(n) if max(p.values(),default=0)==1)
    return sum(factorial(len(t)) for p in partitions(n) for t in aset if set(p).issubset(t)) # Chai Wah Wu, Sep 21 2023

a(18)-a(37) from Chai Wah Wu, Sep 21 2023

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

A374703 Number of integer compositions of 2n whose leaders of weakly decreasing runs sum to n. Center n = 2*k of the triangle A374748.

Original entry on oeis.org

1, 1, 2, 9, 24, 96, 343, 1242, 4700, 17352, 65995

Offset: 0

Gus Wiseman, Aug 12 2024

The weakly decreasing run-leaders of a sequence are obtained by splitting it into maximal weakly decreasing subsequences and taking the first term of each.

			The a(0) = 1 through a(4) = 24 compositions:
  ()  (11)  (22)   (33)     (44)
            (211)  (321)    (422)
                   (1122)   (431)
                   (1221)   (1133)
                   (3111)   (1322)
                   (11112)  (1331)
                   (11121)  (4211)
                   (11211)  (11132)
                   (12111)  (11321)
                            (13211)
                            (21122)
                            (21221)
                            (22112)
                            (22121)
                            (41111)
                            (111113)
                            (111131)
                            (111311)
                            (113111)
                            (131111)
                            (211112)
                            (211121)
                            (211211)
                            (212111)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For reversed partitions we have A364910.
For strictly decreasing runs we have the center of A374700.
Center n = 2*k of the triangle A374748.
A003242 counts anti-run compositions.
A011782 counts integer compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
Cf. A000041, A004526, A106356, A124766, A188900, A238343, A261982, A333213.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[2n],Total[First/@Split[#,GreaterEqual]]==n&]],{n,0,8}]

A365005 Number of ways to write 2 as a nonnegative linear combination of a strict integer partition of n.

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 4, 4, 5, 6, 9, 10, 13, 15, 19, 23, 28, 33, 40, 47, 56, 67, 78, 92, 108, 126, 146, 171, 198, 229, 264, 305, 350, 403, 460, 527, 603, 687, 781, 889, 1009, 1144, 1295, 1464, 1653, 1866, 2101, 2364, 2659, 2984, 3347, 3752, 4200, 4696, 5248, 5858

Offset: 0

Gus Wiseman, Aug 26 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(6) = 4 ways:
  0*5 + 2*1
  0*4 + 1*2
  0*3 + 0*2 + 2*1
  0*3 + 1*2 + 0*1

For 1 instead of 2 we have A096765.
Column k = n - 2 of A116861.
Row n = 2 of A364916.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A137719, A237113, A323092, A365004, A364272, A364907, A364910, A364914, A364915, A365002.

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[2,ptn], {ptn,Select[IntegerPartitions[n], UnsameQ@@#&]}]],{n,0,30}]

cp's OEIS Frontend

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

A364909 Number of ways to write n as a nonnegative linear combination of a strict integer composition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

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

A374703 Number of integer compositions of 2n whose leaders of weakly decreasing runs sum to n. Center n = 2*k of the triangle A374748.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A365005 Number of ways to write 2 as a nonnegative linear combination of a strict integer partition of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica