A364908 Number of ways to write n as a nonnegative linear combination of an integer composition of n.

1, 1, 4, 15, 70, 314, 1542, 7428, 36860, 182911, 917188, 4612480, 23323662, 118273428, 601762636, 3069070533, 15689123386, 80356953555, 412300910566, 2118715503962, 10902791722490, 56175374185014, 289766946825180, 1496239506613985, 7733302967423382

Offset: 0

Author

Gus Wiseman, Aug 22 2023

Keywords

• nonn

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

Examples

			The a(3) = 15 ways to write 3 as a nonnegative linear combination of an integer composition of 3:
  1*3  0*2+3*1  1*1+1*2  0*1+0*1+3*1
       1*2+1*1  3*1+0*2  0*1+1*1+2*1
                         0*1+2*1+1*1
                         0*1+3*1+0*1
                         1*1+0*1+2*1
                         1*1+1*1+1*1
                         1*1+2*1+0*1
                         2*1+0*1+1*1
                         2*1+1*1+0*1
                         3*1+0*1+0*1
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500

Crossrefs

The case with no zero coefficients is A011782.

The version for partitions is A364907, strict A364910.

The strict case is A364909.

A000041 counts integer partitions, strict A000009.

A011782 counts compositions, strict A032020.

A097805 counts compositions by length, strict A072574.

A116861 = positive linear combinations of strict ptns of k, reverse A364916.

A365067 = nonnegative linear combinations of strict partitions of k.

A364912 = positive linear combinations of partitions of k.

A364916 = positive linear combinations of strict partitions of k.

Cf. A364350, A364839, A364906, A364911, A364914, A365002, A365004.

Programs

Maple

b:= proc(n, m) option remember; `if`(n=0, `if`(m=0, 1, 0),
      add(add(b(n-i, m-i*j), j=0..m/i), i=1..n))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 28 2024

Mathematica

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,ptn],{ptn,Join@@Permutations /@ IntegerPartitions[n]}]],{n,0,5}]

Extensions

a(8)-a(24) from Alois P. Heinz, Jan 28 2024