login
A364912
Triangle read by rows where T(n,k) is the number of ways to write n as a positive linear combination of an integer partition of k.
15
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
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
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.
A000041 counts integer partitions, strict A000009.
A008284 counts partitions by length, strict A008289.
A364350 counts combination-free strict partitions, complement A364839.
A364913 counts combination-full partitions.
Sequence in context: A108456 A089107 A361756 * A321449 A180279 A179968
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Aug 20 2023
STATUS
approved