A364915 -id:A364915 - cp's OEIS frontend

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

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

Offset: 1

Emeric Deutsch, Feb 27 2006

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
From Gus Wiseman, Aug 27 2023: (Start)
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)

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

Alois P. Heinz, Rows n = 1..141, flattened
P. J. Rossky, M. Karplus, The enumeration of Goldstone diagrams in many-body perturbation theory, J. Chem. Phys. 64 (1976) 1569, equation (16)(1).

Cf. A000041 (row sums), A000009 (diagonal), A014153.
Cf. A114638 (count partitions with #parts = sum(distinct parts)).
Column 1: A000012, column 2: A000035(1..), column 3: A137719(1..).
For subsets instead of partitions we have A026820.
This statistic is ranked by A066328.
The central diagonal is T(2n,n) = A364910(n), non-strict A364907.
Partial sums of columns are columns of A364911.
Same as A364916 (offset 0) with rows reversed.
A008284 counts partitions by length, strict A008289.
A364912 counts linear combinations of partitions.
A364913 counts combination-full partitions, strict A364839.
Cf. A237667, A364272, A364915, A365002, A365004, A365006.

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))[]:
seq(T(n), n=1..20);  # Alois P. Heinz, Feb 27 2013

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

A116861(n,k,s=0)={forpart(X=n,vecsum(Set(X))==k&&s++,k);s} \\ M. F. Hasler, Oct 27 2019

G.f.: -1 + Product_{j>=1} (1 + t^j*x^j/(1-x^j)).
Sum_{k=1..n} T(n,k) = A000041(n).
T(n,n) = A000009(n).
Sum_{k=1..n} k*T(n,k) = A014153(n-1).
T(n,1) = 1. T(n,2) = A000035(n+1). T(n,3) = A137719(n-2). - R. J. Mathar, Oct 27 2019
T(n,4) = A002264(n-1) + A121262(n). - R. J. Mathar, Oct 28 2019

A364350 Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Aug 15 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(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)

For sums of subsets instead of combinations of partitions we have A151897.
For sums instead of combinations we have A237667, binary A236912.
For subsets instead of partitions we have A326083, complement A364914.
The complement in strict partitions is A364839, non-strict A364913.
A more strict variation is A364915.
The case of all positive coefficients is A365006.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A108917 counts knapsack partitions, ranks A299702.
A116861 and A364916 count linear combinations of strict partitions.
A323092 (ranks A320340) and A120641 count double-free partitions.
A364912 counts linear combinations of partitions of k.
Cf. A007865, A085489, A237113, A275972, A363226, A364272, A364533, A364910, A364911, 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[Select[IntegerPartitions[n],UnsameQ@@#&&And@@Table[combs[#[[k]],Delete[#,k]]=={},{k,Length[#]}]&]],{n,0,15}]

from sympy.utilities.iterables import partitions
def A364350(n):
    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
    return c # Chai Wah Wu, Sep 23 2023

More terms and offset corrected by Martin Fuller, Sep 11 2023

A364839 Number of strict integer partitions of n such that some part can be written as a nonnegative linear combination of the others.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 3, 2, 4, 5, 7, 7, 12, 12, 17, 20, 26, 29, 39, 43, 54, 62, 77, 88, 107, 122, 148, 168, 200, 229, 267, 308, 360, 407, 476, 536, 623, 710, 812, 917, 1050, 1190, 1349, 1530, 1733, 1944, 2206, 2483, 2794, 3138, 3524

Offset: 0

Gus Wiseman, Aug 19 2023

nonn

			For y = (4,3,2) we can write 4 = 0*3 + 2*2, so y is counted under a(9).
For y = (11,5,3) we can write 11 = 1*5 + 2*3, so y is counted under a(19).
For y = (17,5,4,3) we can write 17 = 1*3 + 1*4 + 2*5, so y is counted under a(29).
The a(1) = 0 through a(12) = 12 strict partitions (A = 10, B = 11):
  .  .  (21)  (31)  (41)  (42)   (61)   (62)   (63)   (82)    (A1)    (84)
                          (51)   (421)  (71)   (81)   (91)    (542)   (93)
                          (321)         (431)  (432)  (532)   (632)   (A2)
                                        (521)  (531)  (541)   (641)   (B1)
                                               (621)  (631)   (731)   (642)
                                                      (721)   (821)   (651)
                                                      (4321)  (5321)  (732)
                                                                      (741)
                                                                      (831)
                                                                      (921)
                                                                      (5421)
                                                                      (6321)

For sums instead of combinations we have A364272, binary A364670.
The complement in strict partitions is A364350.
Non-strict versions are A364913 and the complement of A364915.
For subsets instead of partitions we have A364914, complement A326083.
The case of no all positive coefficients is A365006.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
Cf. A085489, A151897, A236912, A237113, A237667, A275972, A363226, A365002.

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@@#&&Or@@Table[combs[#[[k]], Delete[#,k]]!={}, {k,Length[#]}]&]],{n,0,15}]

from sympy.utilities.iterables import partitions
def A364839(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):
        if max(p.values(),default=0)==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 23 2023

A364913 Number of integer partitions of n having a part that can be written as a nonnegative linear combination of the other (possibly equal) parts.

Original entry on oeis.org

0, 0, 1, 2, 4, 5, 10, 12, 20, 27, 39, 51, 74, 95, 130, 169, 225, 288, 378, 479, 617, 778, 990, 1239, 1560, 1938, 2419, 2986, 3696, 4538, 5575, 6810, 8319, 10102, 12274, 14834, 17932, 21587, 25963, 31120, 37275, 44513, 53097, 63181, 75092, 89030, 105460, 124647

Offset: 0

Gus Wiseman, Aug 20 2023

nonn

Includes all non-strict partitions (A047967).

			The a(0) = 0 through a(7) = 12 partitions:
  .  .  (11)  (21)   (22)    (41)     (33)      (61)
              (111)  (31)    (221)    (42)      (322)
                     (211)   (311)    (51)      (331)
                     (1111)  (2111)   (222)     (421)
                             (11111)  (321)     (511)
                                      (411)     (2221)
                                      (2211)    (3211)
                                      (3111)    (4111)
                                      (21111)   (22111)
                                      (111111)  (31111)
                                                (211111)
                                                (1111111)
The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is not counted under a(12).
The partition (6,4,3,2) has 6 = 4+2, or 6 = 3+3, or 6 = 2+2+2, or 4 = 2+2, so is counted under a(15).

The strict case is A364839.
For sums instead of combinations we have A364272, binary A364670.
The complement in strict partitions is A364350.
For subsets instead of partitions we have A364914, complement A326083.
Allowing equal parts gives A365068, complement A364915.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A365006 = no strict partitions w/ pos linear combination.
Cf. A085489, A151897, A236912, A237113, A237667, A275972, A364346.

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@@#||Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,15}]

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

A364911 Triangle read by rows where T(n,k) is the number of integer partitions with sum <= n and with distinct parts summing to k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 1, 2, 1, 4, 2, 3, 2, 1, 5, 2, 5, 3, 3, 1, 6, 3, 8, 4, 4, 4, 1, 7, 3, 11, 6, 6, 6, 5, 1, 8, 4, 14, 9, 8, 10, 7, 6, 1, 9, 4, 19, 11, 11, 14, 11, 9, 8, 1, 10, 5, 23, 14, 15, 21, 15, 14, 11, 10, 1, 11, 5, 28, 17, 19, 28, 22, 20, 17, 15, 12

Offset: 0

Gus Wiseman, Aug 27 2023

Also the number of ways to write any number up to n as a positive linear combination of a strict integer partition of k.

			Triangle begins:
  1
  1  1
  1  2  1
  1  3  1  2
  1  4  2  3  2
  1  5  2  5  3  3
  1  6  3  8  4  4  4
  1  7  3 11  6  6  6  5
  1  8  4 14  9  8 10  7  6
  1  9  4 19 11 11 14 11  9  8
  1 10  5 23 14 15 21 15 14 11 10
  1 11  5 28 17 19 28 22 20 17 15 12
  1 12  6 34 21 22 40 28 28 24 24 17 15
  1 13  6 40 25 27 50 38 37 34 35 27 22 18
  1 14  7 46 29 32 65 49 50 43 51 38 35 26 22
  1 15  7 54 33 38 79 62 63 59 68 55 50 41 32 27
Row n = 5 counts the following partitions:
    .    1           2     3         4       5
         1+1         2+2   1+2       1+3     1+4
         1+1+1             1+1+2     1+1+3   2+3
         1+1+1+1           1+1+1+2
         1+1+1+1+1         1+2+2
Row n = 5 counts the following positive linear combinations:
  .  1*1  1*2  1*3      1*4      1*5
     2*1  2*2  1*2+1*1  1*3+1*1  1*3+1*2
     3*1       1*2+2*1  1*3+2*1  1*4+1*1
     4*1       1*2+3*1
     5*1       2*2+1*1

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Column n = k is A000009.
Column k = 0 is A000012.
Column k = 1 is A000027.
Row sums are A000070.
Column k = 2 is A008619.
Columns are partial sums of columns of A116861.
Column k = 3 appears to be the partial sums of A137719.
Diagonal n = 2k is A364910.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A114638 counts partitions where (length) = (sum of distinct parts).
A116608 counts partitions by number of distinct parts.
A364350 counts combination-free strict partitions, complement A364839.
Cf. A002865, A066328, A179009, A236912, A237113, A237667, A364912, A364913, A364915, A364916, A365002, A365004.

Table[Length[Select[Array[IntegerPartitions,n+1,0,Join],Total[Union[#]]==k&]],{n,0,9},{k,0,n}]

T(n)={[Vecrev(p) | p<-Vec(prod(k=1, n, 1 - y^k + y^k/(1 - x^k), 1/(1 - x) + O(x*x^n)))]}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Jan 11 2024

G.f.: A(x,y) = (1/(1 - x)) * Product_{k>=1} (1 - y^k + y^k/(1 - x^k)). - Andrew Howroyd, Jan 11 2024

A365312 Number of strict integer partitions with sum <= n that cannot be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 2, 6, 4, 8, 7, 16, 6, 24, 17, 24, 20, 46, 22, 62, 31, 63, 57, 106, 35, 122, 90, 137, 88, 212, 74, 262, 134, 267, 206, 345, 121, 476, 294, 484, 232, 698, 242, 837, 389, 763, 571, 1185, 318, 1327, 634, 1392, 727, 1927, 640, 2056, 827, 2233, 1328

Offset: 0

Gus Wiseman, Sep 05 2023

nonn

			The strict partition (7,3,2) has 19 = 1*7 + 2*3 + 3*2 so is not counted under a(19).
The strict partition (9,6,3) cannot be linearly combined to obtain 19, so is counted under a(19).
The a(0) = 0 through a(11) = 16 strict partitions:
  .  .  .  (2)  (3)  (2)  (4)  (2)    (3)  (2)    (3)    (2)
                     (3)  (5)  (3)    (5)  (4)    (4)    (3)
                     (4)       (4)    (6)  (5)    (6)    (4)
                               (5)    (7)  (6)    (7)    (5)
                               (6)         (7)    (8)    (6)
                               (4,2)       (8)    (9)    (7)
                                           (4,2)  (6,3)  (8)
                                           (6,2)         (9)
                                                         (10)
                                                         (4,2)
                                                         (5,4)
                                                         (6,2)
                                                         (6,3)
                                                         (6,4)
                                                         (7,3)
                                                         (8,2)

The complement for positive coefficients is counted by A088314.
For positive coefficients we have A088528.
The complement is counted by A365311.
For non-strict partitions we have A365378, complement A365379.
The version for subsets is A365380, complement A365073.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A364350 counts combination-free strict partitions, non-strict A364915.
A364839 counts combination-full strict partitions, non-strict A364913.
Cf. A093971, A237113, A237668, A326080, A363225, A364272, A364534, A364914, A365043, A365314, A365320.

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

from math import isqrt
from sympy.utilities.iterables import partitions
def A365312(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n+1) for b in partitions(m,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023

a(26)-a(58) from Chai Wah Wu, Sep 13 2023

A365311 Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 11, 12, 20, 24, 35, 38, 63, 63, 92, 112, 148, 160, 230, 244, 339, 383, 478, 533, 726, 781, 978, 1123, 1394, 1526, 1960, 2112, 2630, 2945, 3518, 3964, 4856, 5261, 6307, 7099, 8464, 9258, 11140, 12155, 14419, 16093, 18589, 20565, 24342, 26597, 30948

Offset: 0

Gus Wiseman, Sep 04 2023

nonn

			The strict partition (6,3) cannot be linearly combined to obtain 10, so is not counted under a(10).
The strict partition (4,2) has 6 = 1*4 + 1*2 so is counted under a(6), but (4,2) cannot be linearly combined to obtain 7 so is not counted under a(7).
The a(1) = 1 through a(7) = 12 strict partitions:
  (1)  (1)  (1)    (1)    (1)    (1)      (1)
       (2)  (3)    (2)    (5)    (2)      (7)
            (2,1)  (4)    (2,1)  (3)      (2,1)
                   (2,1)  (3,1)  (6)      (3,1)
                   (3,1)  (3,2)  (2,1)    (3,2)
                          (4,1)  (3,1)    (4,1)
                                 (3,2)    (4,3)
                                 (4,1)    (5,1)
                                 (4,2)    (5,2)
                                 (5,1)    (6,1)
                                 (3,2,1)  (3,2,1)
                                          (4,2,1)

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

For positive coefficients we have A088314.
The positive complement is counted by A088528.
The version for subsets is A365073.
The complement is counted by A365312.
For non-strict partitions we have A365379.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A116861 and A364916 count linear combinations of strict partitions.
A364350 counts combination-free strict partitions, non-strict A364915.
A364839 counts combination-full strict partitions, non-strict A364913.
Cf. A093971, A237113, A237668, A326080, A363225, A364272, A364534, A364914, A365043, A365314, A365320.

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

from math import isqrt
from sympy.utilities.iterables import partitions
def A365311(n):
    a = {tuple(sorted(set(p))) for p in partitions(n)}
    return sum(1 for m in range(1,n+1) for b in partitions(m,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023

a(26)-a(50) from Chai Wah Wu, Sep 13 2023

A364912 Triangle read by rows where T(n,k) is the number of ways to write n as a positive linear combination of an integer partition of k.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 4, 4, 5, 0, 1, 4, 8, 7, 7, 0, 1, 6, 13, 17, 12, 11, 0, 1, 6, 18, 28, 30, 19, 15, 0, 1, 8, 24, 50, 58, 53, 30, 22

Offset: 0

Gus Wiseman, Aug 20 2023

A way of writing n as a positive 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),(2,2)) are a way of writing 8 as a positive linear combination of (1,1,2), namely 8 = 3*1 + 1*1 + 2*2.

			Triangle begins:
  1
  0  1
  0  1  2
  0  1  2  3
  0  1  4  4  5
  0  1  4  8  7  7
  0  1  6 13 17 12 11
  0  1  6 18 28 30 19 15
  0  1  8 24 50 58 53 30 22
Row n = 4 counts the following linear combinations:
  .  1*4  2*2      2*1+1*2      4*1
          1*1+1*3  1*1+1*1+1*2  3*1+1*1
          1*2+1*2  1*1+1*2+1*1  2*1+2*1
          1*3+1*1  1*2+1*1+1*1  2*1+1*1+1*1
                                1*1+1*1+1*1+1*1
Row n = 5 counts the following linear combinations:
  .  1*5  1*1+1*4  2*1+1*3      3*1+1*2          5*1
          1*2+1*3  2*2+1*1      2*1+1*1+1*2      4*1+1*1
          1*3+1*2  1*1+1*1+1*3  2*1+1*2+1*1      3*1+2*1
          1*4+1*1  1*1+1*2+1*2  1*1+1*1+1*1+1*2  3*1+1*1+1*1
                   1*1+1*3+1*1  1*1+1*1+1*2+1*1  2*1+2*1+1*1
                   1*2+1*1+1*2  1*1+1*2+1*1+1*1  2*1+1*1+1*1+1*1
                   1*2+1*2+1*1  1*2+1*1+1*1+1*1  1*1+1*1+1*1+1*1+1*1
                   1*3+1*1+1*1
Array begins:
  1   0   0   0    0    0    0     0
  1   1   1   1    1    1    1     1
  2   2   4   4    6    6    8     8
  3   4   8   13   18   24   33    40
  5   7   17  28   50   70   107   143
  7   12  30  58   108  179  286   428
  11  19  53  109  223  394  696   1108
  15  30  86  194  420  812  1512  2619

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Row k = 0 is A000007.
Row k = 1 is A000012.
Column n = 0 is A000041.
Column n = 1 is A000070.
Row sums are A006951.
Row k = 2 is A052928 except initial terms.
The case of strict integer partitions is A116861.
Central column is T(2n,n) = A(n,n) = A364907(n).
With rows reversed we have the nonnegative version A365004.
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. A237113, A364272, A364910, A364911, A364914, A364915, A365002.

combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Join@@Table[combp[n,ptn],{ptn,IntegerPartitions[k]}]],{n,0,6},{k,0,n}]
- or -
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-k,ptn],{ptn,IntegerPartitions[k]}]],{n,0,6},{k,0,n}]

As an array, also the number of ways to write n-k as a nonnegative linear combination of an integer partition of k (see programs).

A365004 Array read by antidiagonals downwards where A(n,k) is the number of ways to write n as a nonnegative linear combination of an integer partition of k.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 3, 2, 1, 0, 5, 4, 4, 1, 0, 7, 7, 8, 4, 1, 0, 11, 12, 17, 13, 6, 1, 0, 15, 19, 30, 28, 18, 6, 1, 0, 22, 30, 53, 58, 50, 24, 8, 1, 0, 30, 45, 86, 109, 108, 70, 33, 8, 1, 0, 42, 67, 139, 194, 223, 179, 107, 40, 10, 1, 0, 56, 97, 213, 328, 420, 394, 286, 143, 50, 10, 1, 0

Offset: 0

Gus Wiseman, Aug 23 2023

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

			Array begins:
  1  1  2   3   5    7     11
  0  1  2   4   7    12    19
  0  1  4   8   17   30    53
  0  1  4   13  28   58    109
  0  1  6   18  50   108   223
  0  1  6   24  70   179   394
  0  1  8   33  107  286   696
  0  1  8   40  143  428   1108
  0  1  10  50  199  628   1754
  0  1  10  61  254  882   2622
  0  1  12  72  332  1215  3857
  0  1  12  84  410  1624  5457
  0  1  14  99  517  2142  7637
The A(4,2) = 6 ways:
  2*2
  0*1+4*1
  1*1+3*1
  2*1+2*1
  3*1+1*1
  4*1+0*1

Alois P. Heinz, Rows n = 0..200, flattened

Row n = 0 is A000041, strict A000009.
Row n = 1 is A000070.
Column k = 0 is A000007.
Column k = 1 is A000012.
Column k = 2 is A052928 except initial terms.
Antidiagonal sums are A006951.
The case of strict integer partitions is A116861.
Main diagonal is A364907.
The transpose is A364912, also the positive version.
A008284 counts partitions by length, strict A008289.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Cf. A066328, A108917, A237113, A364272, A364910, A364911, A364915, A365002.

b:= proc(n, i, m) option remember; `if`(n=0, `if`(m=0, 1, 0),
     `if`(i<1, 0, b(n, i-1, m)+add(b(n-i, min(i, n-i), m-i*j), j=0..m/i)))
    end:
A:= (n, k)-> b(k$2, n):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Jan 28 2024

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

Also the number of ways to write n-k as a *positive* linear combination of an integer partition of k.

Antidiagonals 8-11 from Alois P. Heinz, Jan 28 2024

A365322 Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.

Original entry on oeis.org

0, 1, 2, 5, 11, 26, 54, 116, 238, 490, 994, 2011, 4045, 8131, 16305, 32672, 65412, 130924, 261958, 524066, 1048301, 2096826, 4193904, 8388135, 16776641, 33553759, 67108053, 134216782, 268434324, 536869595, 1073740266, 2147481835, 4294965158, 8589932129

Offset: 0

Gus Wiseman, Sep 04 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 set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
The a(1) = 1 through a(4) = 11 subsets:
  {}  {}     {}       {}
      {1,2}  {2}      {3}
             {1,3}    {1,4}
             {2,3}    {2,3}
             {1,2,3}  {2,4}
                      {3,4}
                      {1,2,3}
                      {1,2,4}
                      {1,3,4}
                      {2,3,4}
                      {1,2,3,4}

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The complement is counted by A088314.
The version for strict partitions is A088528.
The nonnegative complement is counted by A365073, without n A365542.
The binary complement is A365315, nonnegative A365314.
The binary version is A365321, nonnegative A365320.
For nonnegative coefficients we have A365380.
A085489 and A364755 count subsets without the sum of two distinct elements.
A124506 appears to count combination-free subsets, differences of A326083.
A179822 counts sum-closed subsets, first differences of A326080.
A364350 counts combination-free strict partitions, non-strict A364915.
A365046 counts combination-full subsets, first differences of A364914.
Cf. A070880, A088809, A093971, A151897, A326020, A364272, A364839, A365043, A365381.

b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
      {b(n, i-1)[], seq(map(x->{x[], i}, b(n-i*j, i-1))[], j=1..n/i)}))
    end:
a:= n-> 2^n-nops(b(n$2)):
seq(a(n), n=0..33);  # Alois P. Heinz, Sep 04 2023

cpu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],cpu[n,#]=={}&]],{n,0,10}]

from sympy.utilities.iterables import partitions
def A365322(n): return (1<Chai Wah Wu, Sep 14 2023

a(n) = 2^n - A088314(n).

a(n) = A070880(n) + 2^(n-1) for n>=1.

More terms from Alois P. Heinz, Sep 04 2023

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A364350 Number of strict integer partitions of n such that no part can be written as a nonnegative linear combination of the others.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A364839 Number of strict integer partitions of n such that some part can be written as a nonnegative linear combination of the others.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

A364913 Number of integer partitions of n having a part that can be written as a nonnegative linear combination of the other (possibly equal) parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A364911 Triangle read by rows where T(n,k) is the number of integer partitions with sum <= n and with distinct parts summing to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A365312 Number of strict integer partitions with sum <= n that cannot be linearly combined using nonnegative coefficients to obtain n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A365311 Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A364912 Triangle read by rows where T(n,k) is the number of ways to write n as a positive linear combination of an integer partition of k.

Views

Author