login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #13 Jan 28 2024 20:57:10

%S 1,1,4,15,70,314,1542,7428,36860,182911,917188,4612480,23323662,

%T 118273428,601762636,3069070533,15689123386,80356953555,412300910566,

%U 2118715503962,10902791722490,56175374185014,289766946825180,1496239506613985,7733302967423382

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

%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="/A364908/b364908.txt">Table of n, a(n) for n = 0..500</a>

%e The a(3) = 15 ways to write 3 as a nonnegative linear combination of an integer composition of 3:

%e 1*3 0*2+3*1 1*1+1*2 0*1+0*1+3*1

%e 1*2+1*1 3*1+0*2 0*1+1*1+2*1

%e 0*1+2*1+1*1

%e 0*1+3*1+0*1

%e 1*1+0*1+2*1

%e 1*1+1*1+1*1

%e 1*1+2*1+0*1

%e 2*1+0*1+1*1

%e 2*1+1*1+0*1

%e 3*1+0*1+0*1

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

%p add(add(b(n-i, m-i*j), j=0..m/i), i=1..n))

%p end:

%p a:= n-> b(n$2):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Jan 28 2024

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

%t Table[Length[Join@@Table[combs[n,ptn],{ptn,Join@@Permutations /@ IntegerPartitions[n]}]],{n,0,5}]

%Y The case with no zero coefficients is A011782.

%Y The version for partitions is A364907, strict A364910.

%Y The strict case is A364909.

%Y A000041 counts integer partitions, strict A000009.

%Y A011782 counts compositions, strict A032020.

%Y A097805 counts compositions by length, strict A072574.

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

%Y A365067 = nonnegative linear combinations of strict partitions of k.

%Y A364912 = positive linear combinations of partitions of k.

%Y A364916 = positive linear combinations of strict partitions of k.

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Aug 22 2023

%E a(8)-a(24) from _Alois P. Heinz_, Jan 28 2024