login
A364908
Number of ways to write n as a nonnegative linear combination of an integer composition of n.
4
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,3
COMMENTS
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).
LINKS
EXAMPLE
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
MAPLE
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
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, Join@@Permutations /@ IntegerPartitions[n]}]], {n, 0, 5}]
CROSSREFS
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.
Sequence in context: A039625 A020020 A000882 * A098614 A367040 A356407
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 22 2023
EXTENSIONS
a(8)-a(24) from Alois P. Heinz, Jan 28 2024
STATUS
approved