[go: up one dir, main page]

login
A364907
Number of ways to write n as a nonnegative linear combination of an integer partition of n.
11
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
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.
Sequence in context: A101125 A284336 A230081 * A299699 A056275 A149455
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 18 2023
EXTENSIONS
a(9)-a(26) from Alois P. Heinz, Jan 28 2024
STATUS
approved