login
Array read by antidiagonals downwards where A(n,k) is the number of ways to write n as a nonnegative linear combination of an integer partition of k.
13

%I #15 Jan 28 2024 20:41:21

%S 1,1,0,2,1,0,3,2,1,0,5,4,4,1,0,7,7,8,4,1,0,11,12,17,13,6,1,0,15,19,30,

%T 28,18,6,1,0,22,30,53,58,50,24,8,1,0,30,45,86,109,108,70,33,8,1,0,42,

%U 67,139,194,223,179,107,40,10,1,0,56,97,213,328,420,394,286,143,50,10,1,0

%N Array read by antidiagonals downwards where A(n,k) is the number of ways to write n as a nonnegative linear combination of an integer partition of k.

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

%H Alois P. Heinz, <a href="/A365004/b365004.txt">Rows n = 0..200, flattened</a>

%F Also the number of ways to write n-k as a *positive* linear combination of an integer partition of k.

%e Array begins:

%e 1 1 2 3 5 7 11

%e 0 1 2 4 7 12 19

%e 0 1 4 8 17 30 53

%e 0 1 4 13 28 58 109

%e 0 1 6 18 50 108 223

%e 0 1 6 24 70 179 394

%e 0 1 8 33 107 286 696

%e 0 1 8 40 143 428 1108

%e 0 1 10 50 199 628 1754

%e 0 1 10 61 254 882 2622

%e 0 1 12 72 332 1215 3857

%e 0 1 12 84 410 1624 5457

%e 0 1 14 99 517 2142 7637

%e The A(4,2) = 6 ways:

%e 2*2

%e 0*1+4*1

%e 1*1+3*1

%e 2*1+2*1

%e 3*1+1*1

%e 4*1+0*1

%p b:= proc(n, i, m) option remember; `if`(n=0, `if`(m=0, 1, 0),

%p `if`(i<1, 0, b(n, i-1, m)+add(b(n-i, min(i, n-i), m-i*j), j=0..m/i)))

%p end:

%p A:= (n, k)-> b(k$2, n):

%p seq(seq(A(n, d-n), n=0..d), d=0..12); # _Alois P. Heinz_, Jan 28 2024

%t nn=5;

%t combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];

%t tabv=Table[Length[Join@@Table[combs[n,ptn],{ptn,IntegerPartitions[k]}]],{n,0,nn},{k,0,nn}]

%t Table[tabv[[k+1,n-k+1]],{n,0,nn},{k,0,n}]

%Y Row n = 0 is A000041, strict A000009.

%Y Row n = 1 is A000070.

%Y Column k = 0 is A000007.

%Y Column k = 1 is A000012.

%Y Column k = 2 is A052928 except initial terms.

%Y Antidiagonal sums are A006951.

%Y The case of strict integer partitions is A116861.

%Y Main diagonal is A364907.

%Y The transpose is A364912, also the positive version.

%Y A008284 counts partitions by length, strict A008289.

%Y A364350 counts combination-free strict partitions, complement A364839.

%Y A364913 counts combination-full partitions.

%Y Cf. A066328, A108917, A237113, A364272, A364910, A364911, A364915, A365002.

%K nonn,tabl

%O 0,4

%A _Gus Wiseman_, Aug 23 2023

%E Antidiagonals 8-11 from _Alois P. Heinz_, Jan 28 2024