cp's OEIS Frontend

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

%I A364908 #13 Jan 28 2024 20:57:10
%S A364908 1,1,4,15,70,314,1542,7428,36860,182911,917188,4612480,23323662,
%T A364908 118273428,601762636,3069070533,15689123386,80356953555,412300910566,
%U A364908 2118715503962,10902791722490,56175374185014,289766946825180,1496239506613985,7733302967423382
%N A364908 Number of ways to write n as a nonnegative linear combination of an integer composition of n.
%C A364908 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 A364908 Alois P. Heinz, <a href="/A364908/b364908.txt">Table of n, a(n) for n = 0..500</a>
%e A364908 The a(3) = 15 ways to write 3 as a nonnegative linear combination of an integer composition of 3:
%e A364908   1*3  0*2+3*1  1*1+1*2  0*1+0*1+3*1
%e A364908        1*2+1*1  3*1+0*2  0*1+1*1+2*1
%e A364908                          0*1+2*1+1*1
%e A364908                          0*1+3*1+0*1
%e A364908                          1*1+0*1+2*1
%e A364908                          1*1+1*1+1*1
%e A364908                          1*1+2*1+0*1
%e A364908                          2*1+0*1+1*1
%e A364908                          2*1+1*1+0*1
%e A364908                          3*1+0*1+0*1
%p A364908 b:= proc(n, m) option remember; `if`(n=0, `if`(m=0, 1, 0),
%p A364908       add(add(b(n-i, m-i*j), j=0..m/i), i=1..n))
%p A364908     end:
%p A364908 a:= n-> b(n$2):
%p A364908 seq(a(n), n=0..25);  # _Alois P. Heinz_, Jan 28 2024
%t A364908 combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]}, Select[Tuples[s],Total[Times@@@#]==n&]];
%t A364908 Table[Length[Join@@Table[combs[n,ptn],{ptn,Join@@Permutations /@ IntegerPartitions[n]}]],{n,0,5}]
%Y A364908 The case with no zero coefficients is A011782.
%Y A364908 The version for partitions is A364907, strict A364910.
%Y A364908 The strict case is A364909.
%Y A364908 A000041 counts integer partitions, strict A000009.
%Y A364908 A011782 counts compositions, strict A032020.
%Y A364908 A097805 counts compositions by length, strict A072574.
%Y A364908 A116861 = positive linear combinations of strict ptns of k, reverse A364916.
%Y A364908 A365067 = nonnegative linear combinations of strict partitions of k.
%Y A364908 A364912 = positive linear combinations of partitions of k.
%Y A364908 A364916 = positive linear combinations of strict partitions of k.
%Y A364908 Cf. A364350, A364839, A364906, A364911, A364914, A365002, A365004.
%K A364908 nonn
%O A364908 0,3
%A A364908 _Gus Wiseman_, Aug 22 2023
%E A364908 a(8)-a(24) from _Alois P. Heinz_, Jan 28 2024