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.

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

Table of n, a(n) for n=0..44.

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.

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.

Cf. A237113, A364272, A364910, A364911, A364914, A364915, A365002.

Sequence in context: A108456 A089107 A361756 * A321449 A180279 A179968

Adjacent sequences: A364909 A364910 A364911 * A364913 A364914 A364915

Keyword

nonn,tabl

Author

Gus Wiseman, Aug 20 2023

Status

approved