A364907 Number of ways to write n as a nonnegative linear combination of an integer partition of n.

1, 1, 4, 13, 50, 179, 696, 2619, 10119, 38867, 150407, 582065, 2260367, 8786919, 34225256, 133471650, 521216494, 2037608462, 7974105052, 31235316275, 122457794193, 480473181271, 1886555402750, 7412471695859, 29142658077266, 114643347181003, 451237737215201

Offset

0,3

Comments

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

Links

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

Formula

a(n) = Sum_{m:A056239(m)=n} A364906(m).

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

a(n) = A365004(n,n).

Example

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

Maple

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-> b(n$3):
seq(a(n), n=0..27);  # Alois P. Heinz, Jan 28 2024

Mathematica

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, IntegerPartitions[n]}]], {n, 0, 5}]

Crossrefs

The case with no zero coefficients is A000041.

A finer version is A364906.

The version for compositions is A364908, strict A364909.

Using just strict partitions we get A364910, main diagonal of A364916.

Main diagonal of A365004.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A323092 counts double-free partitions, ranks A320340.

Cf. A116861, A364350, A364839, A364911, A364912, A364913, A364914, A364915, A365002, A365003.

Sequence in context: A101125 A284336 A230081 * A299699 A056275 A149455

Adjacent sequences: A364904 A364905 A364906 * A364908 A364909 A364910

Keyword

nonn

Author

Gus Wiseman, Aug 18 2023

Extensions

a(9)-a(26) from Alois P. Heinz, Jan 28 2024

Status

approved