A365004 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.

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, 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, 67, 139, 194, 223, 179, 107, 40, 10, 1, 0, 56, 97, 213, 328, 420, 394, 286, 143, 50, 10, 1, 0

Offset

0,4

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

Alois P. Heinz, Rows n = 0..200, flattened

Formula

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

Example

Array begins:
  1  1  2   3   5    7     11
  0  1  2   4   7    12    19
  0  1  4   8   17   30    53
  0  1  4   13  28   58    109
  0  1  6   18  50   108   223
  0  1  6   24  70   179   394
  0  1  8   33  107  286   696
  0  1  8   40  143  428   1108
  0  1  10  50  199  628   1754
  0  1  10  61  254  882   2622
  0  1  12  72  332  1215  3857
  0  1  12  84  410  1624  5457
  0  1  14  99  517  2142  7637
The A(4,2) = 6 ways:
  2*2
  0*1+4*1
  1*1+3*1
  2*1+2*1
  3*1+1*1
  4*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, k)-> b(k$2, n):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Jan 28 2024

Mathematica

nn=5;
combs[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 0, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
tabv=Table[Length[Join@@Table[combs[n, ptn], {ptn, IntegerPartitions[k]}]], {n, 0, nn}, {k, 0, nn}]
Table[tabv[[k+1, n-k+1]], {n, 0, nn}, {k, 0, n}]

Crossrefs

Row n = 0 is A000041, strict A000009.

Row n = 1 is A000070.

Column k = 0 is A000007.

Column k = 1 is A000012.

Column k = 2 is A052928 except initial terms.

Antidiagonal sums are A006951.

The case of strict integer partitions is A116861.

Main diagonal is A364907.

The transpose is A364912, also the positive version.

A008284 counts partitions by length, strict A008289.

A364350 counts combination-free strict partitions, complement A364839.

A364913 counts combination-full partitions.

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

Sequence in context: A180653 A259100 A368091 * A096652 A322133 A274183

Adjacent sequences: A365001 A365002 A365003 * A365005 A365006 A365007

Keyword

nonn,tabl

Author

Gus Wiseman, Aug 23 2023

Extensions

Antidiagonals 8-11 from Alois P. Heinz, Jan 28 2024

Status

approved