A364907 -id:A364907 - 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

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

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 2, 0, 1, 0, 2, 1, 1, 1, 0, 3, 1, 2, 0, 1, 0, 4, 1, 1, 3, 1, 1, 0, 5, 2, 2, 2, 3, 0, 1, 0, 6, 2, 4, 2, 3, 3, 1, 1, 0, 8, 3, 4, 4, 3, 2, 5, 0, 1, 0, 10, 3, 5, 4, 7, 4, 3, 4, 1, 1, 0, 12, 5, 6, 6, 7, 7, 4, 3, 5, 0, 1, 0, 15, 5, 9, 7, 8, 6, 12, 3, 4, 6, 1, 1, 0

Offset: 0

Gus Wiseman, Aug 17 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).

As a triangle, also the number of ways to write n as a *positive* linear combination of the parts of a strict integer partition of k.

			Array begins:
  1  1  1  2  2  3  4   5   6   8   10   12  15   18   22   27
  0  1  0  1  1  1  2   2   3   3   5    5   7    8    10   12
  0  1  1  2  1  2  4   4   5   6   9    10  13   15   19   23
  0  1  0  3  2  2  4   4   6   7   11   11  15   17   22   27
  0  1  1  3  3  3  7   7   8   10  16   17  23   27   33   42
  0  1  0  3  2  4  7   6   9   9   17   17  23   26   33   43
  0  1  1  5  3  4  12  10  13  16  26   27  36   42   52   68
  0  1  0  4  3  3  10  11  13  13  27   25  35   40   51   67
  0  1  1  5  4  5  15  13  19  20  36   37  51   58   72   97
  0  1  0  6  4  5  14  13  18  23  42   39  54   61   78   105
  0  1  1  6  4  6  20  17  23  25  54   50  69   80   98   138
  0  1  0  6  4  5  19  16  23  24  54   55  71   80   103  144
  0  1  1  8  6  7  27  23  30  35  72   70  103  113  139  199
  0  1  0  7  5  6  24  21  29  31  75   68  95   115  139  201
  0  1  1  8  5  7  31  27  36  39  90   86  122  137  178  255
  0  1  0  9  6  8  31  27  38  42  100  93  129  148  187  289
Triangle begins:
   1
   1  0
   1  1  0
   2  0  1  0
   2  1  1  1  0
   3  1  2  0  1  0
   4  1  1  3  1  1  0
   5  2  2  2  3  0  1  0
   6  2  4  2  3  3  1  1  0
   8  3  4  4  3  2  5  0  1  0
  10  3  5  4  7  4  3  4  1  1  0
  12  5  6  6  7  7  4  3  5  0  1  0
  15  5  9  7  8  6 12  3  4  6  1  1  0
  18  7 10 11 10  9 10 10  5  4  6  0  1  0
  22  8 13 11 16  9 13 11 15  5  4  6  1  1  0
  27 10 15 15 17 17 16 13 13 14  6  4  8  0  1  0

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

Same as A116861 with offset 0 and rows reversed, non-strict version A364912.
Row n = 0 is A000009.
Row n = 1 is A096765.
Row n = 2 is A365005.
Column k = 0 is A000007.
Column k = 1 is A000012.
Column k = 2 is A000035.
Column k = 3 is A137719.
The main diagonal is A364910.
Left half has row sums A365002.
For not just strict partitions we have A365004, diagonal A364907.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A066328 adds up distinct prime indices.
A364350 counts combination-free strict partitions, complement A364839.
Cf. A007865, A085489, A108917, A237113, A323092, A364272, A364533, A364670, A364911, A364913.

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

A364910 Number of integer partitions of 2n whose distinct parts sum to n.

Original entry on oeis.org

1, 1, 1, 3, 3, 4, 12, 11, 19, 23, 54, 55, 103, 115, 178, 289, 389, 507, 757, 970, 1343, 2033, 2579, 3481, 4840, 6312, 8317, 10998, 15459, 19334, 26368, 33480, 44709, 56838, 74878, 93369, 128109, 157024, 206471, 258357, 338085, 417530, 544263, 669388, 859570, 1082758, 1367068

Offset: 0

Gus Wiseman, Aug 16 2023

nonn

Also the number of ways to write n as a nonnegative linear combination of the parts of a strict integer partition of n.

			The a(0) = 1 through a(7) = 11 partitions:
  ()  (11)  (22)  (33)     (44)      (55)       (66)         (77)
                  (2211)   (3311)    (3322)     (4422)       (4433)
                  (21111)  (311111)  (4411)     (5511)       (5522)
                                     (4111111)  (33321)      (6611)
                                                (42222)      (442211)
                                                (322221)     (4222211)
                                                (332211)     (4421111)
                                                (3222111)    (42221111)
                                                (3321111)    (422111111)
                                                (32211111)   (611111111)
                                                (51111111)   (4211111111)
                                                (321111111)
The a(0) = 1 through a(7) = 11 linear combinations:
  0  1*1  1*2  1*3      1*4      1*5      1*6          1*7
               0*2+3*1  0*3+4*1  0*4+5*1  0*4+3*2      0*6+7*1
               1*2+1*1  1*3+1*1  1*3+1*2  0*5+6*1      1*4+1*3
                                 1*4+1*1  1*4+1*2      1*5+1*2
                                          1*5+1*1      1*6+1*1
                                          0*3+0*2+6*1  0*4+0*2+7*1
                                          0*3+1*2+4*1  0*4+1*2+5*1
                                          0*3+2*2+2*1  0*4+2*2+3*1
                                          0*3+3*2+0*1  0*4+3*2+1*1
                                          1*3+0*2+3*1  1*4+0*2+3*1
                                          1*3+1*2+1*1  1*4+1*2+1*1
                                          2*3+0*2+0*1

Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 91 terms from David A. Corneth)

The case with no zero coefficients is A000009.
Central diagonal of A116861.
A version based on Heinz numbers is A364906.
Using all partitions (not just strict) we get A364907.
The version for compositions is A364908, strict A364909.
Main diagonal of A364916.
Using strict partitions of any number from 1 to n gives A365002.
These partitions have ranks A365003.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A323092 counts double-free partitions, ranks A320340.
Cf. A237113, A364350, A364839, A364911, A364912, A364914.

Table[Length[Select[IntegerPartitions[2n],Total[Union[#]]==n&]],{n,0,15}]

a(n) = {my(res = 0); forpart(p = 2*n,s = Set(p); if(vecsum(s) == n, res++)); res} \\ David A. Corneth, Aug 20 2023

from sympy.utilities.iterables import partitions
def A364910(n): return sum(1 for d in partitions(n<<1,k=n) if sum(set(d))==n) # Chai Wah Wu, Sep 13 2023

a(n) = A116861(2n,n).

a(n) = A364916(n,n).

More terms from David A. Corneth, Aug 20 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).

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

Original entry on oeis.org

1, 1, 2, 4, 8, 10, 26, 32, 63, 84, 157, 207, 383, 477, 768, 1108, 1710, 2261, 3536, 4605, 6869, 9339, 13343, 17653, 25785, 33463, 46752, 61549, 85614, 110861, 153719, 197345, 268623, 346845, 463513, 593363, 797082, 1011403, 1335625, 1703143, 2232161, 2820539

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

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

Row sums of lower-left half of A364916 as an array.
Column sums of right half of A364916 as a triangle.
For all positive coefficients we have A000041, non-strict A006951.
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. A066328, A116861, A364272, A364907, A364910, A364911, A364912, A365004.

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

from itertools import combinations
from collections import Counter
from sympy.utilities.iterables import partitions
def A365002(n):
    aset = Counter(tuple(sorted(set(p))) for p in partitions(n))
    return sum(sum(aset[t] for t in aset if set(t).issubset(set(q))) for l in range(1,n+1) for q in combinations(range(1,n+1),l) if sum(q)<=n) # Chai Wah Wu, Sep 20 2023

a(16)-a(34) from Chai Wah Wu, Sep 20 2023
a(35)-a(38) from Chai Wah Wu, Sep 21 2023
a(0)=1 and a(39)-a(41) from Alois P. Heinz, Jan 11 2024

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

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

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A364910 Number of integer partitions of 2n whose distinct parts sum to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples