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

Author

Gus Wiseman, Aug 18 2023

Keywords

• nonn

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

Examples

			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
		

Links

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

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.

Programs

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}]

Formula

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

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

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

Extensions

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