OFFSET
0,6
COMMENTS
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.
LINKS
S. R. Finch, Monoids of natural numbers, March 17, 2009.
FORMULA
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).
EXAMPLE
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
MATHEMATICA
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}]
CROSSREFS
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.
A364913 counts combination-full partitions.
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Aug 20 2023
STATUS
approved