A364912 -id:A364912 - cp's OEIS frontend

A364906 Number of ways to write A056239(n) as a nonnegative linear combination of the multiset of prime indices of n.

1, 1, 1, 3, 1, 2, 1, 10, 3, 2, 1, 9, 1, 2, 1, 35, 1, 6, 1, 9, 2, 2, 1, 34, 3, 2, 10, 10, 1, 7, 1, 126, 1, 2, 1, 30, 1, 2, 2, 39, 1, 6, 1, 11, 3, 2, 1, 130, 3, 6, 1, 12, 1, 20, 1, 46, 2, 2, 1, 31, 1, 2, 9, 462, 2, 7, 1, 13, 1, 6, 1, 120, 1, 2, 4, 14, 1, 7, 1

Offset: 1

Gus Wiseman, Aug 22 2023

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.
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).
Conjecture: Positions of 1's are numbers whose distinct divisors all have different GCDs of prime indices, listed by A319319, counted by A319318.

			The a(2) = 1 through a(10) = 2 ways:
  1*1  1*2  0*1+2*1  1*3  1*1+1*2  1*4  0*1+0*1+3*1  0*2+2*2  1*1+1*3
            1*1+1*1       3*1+0*2       0*1+1*1+2*1  1*2+1*2  4*1+0*3
            2*1+0*1                     0*1+2*1+1*1  2*2+0*2
                                        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

The case with no zero coefficients is A000012.
Positions of 1's appear to be A319319.
A001222 counts prime indices, distinct A001221.
A112798 lists prime indices, sum A056239.
A364910 counts nonnegative linear combinations of strict partitions.
Cf. A116861, A275972, A320340, A364350, A364839, A364912, A364914, A364916, A365002, A365003, A365004.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[combs[Total[prix[n]],prix[n]]],{n,100}]

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

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

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

cp's OEIS Frontend

A364906 Number of ways to write A056239(n) as a nonnegative linear combination of the multiset of prime indices of n.

Views

Author

Keywords

Comments

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

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

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