cp's OEIS Frontend

A364907 Number of ways to write n as a nonnegative linear combination of an integer partition of n.

%I A364907 #16 Jan 28 2024 20:57:15
%S A364907 1,1,4,13,50,179,696,2619,10119,38867,150407,582065,2260367,8786919,
%T A364907 34225256,133471650,521216494,2037608462,7974105052,31235316275,
%U A364907 122457794193,480473181271,1886555402750,7412471695859,29142658077266,114643347181003,451237737215201
%N A364907 Number of ways to write n as a nonnegative linear combination of an integer partition of n.
%C A364907 A way of writing n as a (presumed 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 A364907 Alois P. Heinz, <a href="/A364907/b364907.txt">Table of n, a(n) for n = 0..500</a>
%F A364907 a(n) = Sum_{m:A056239(m)=n} A364906(m).
%F A364907 a(n) = A364912(2n,n).
%F A364907 a(n) = A365004(n,n).
%e A364907 The a(0) = 1 through a(3) = 13 ways:
%e A364907   0  1*1  1*2      1*3
%e A364907           0*1+2*1  0*2+3*1
%e A364907           1*1+1*1  1*2+1*1
%e A364907           2*1+0*1  0*1+0*1+3*1
%e A364907                    0*1+1*1+2*1
%e A364907                    0*1+2*1+1*1
%e A364907                    0*1+3*1+0*1
%e A364907                    1*1+0*1+2*1
%e A364907                    1*1+1*1+1*1
%e A364907                    1*1+2*1+0*1
%e A364907                    2*1+0*1+1*1
%e A364907                    2*1+1*1+0*1
%e A364907                    3*1+0*1+0*1
%p A364907 b:= proc(n, i, m) option remember; `if`(n=0, `if`(m=0, 1, 0),
%p A364907      `if`(i<1, 0, b(n, i-1, m)+add(b(n-i, min(i, n-i), m-i*j), j=0..m/i)))
%p A364907     end:
%p A364907 a:= n-> b(n$3):
%p A364907 seq(a(n), n=0..27);  # _Alois P. Heinz_, Jan 28 2024
%t A364907 combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A364907 Table[Length[Join@@Table[combs[n,ptn],{ptn,IntegerPartitions[n]}]],{n,0,5}]
%Y A364907 The case with no zero coefficients is A000041.
%Y A364907 A finer version is A364906.
%Y A364907 The version for compositions is A364908, strict A364909.
%Y A364907 Using just strict partitions we get A364910, main diagonal of A364916.
%Y A364907 Main diagonal of A365004.
%Y A364907 A000041 counts integer partitions, strict A000009.
%Y A364907 A008284 counts partitions by length, strict A008289.
%Y A364907 A323092 counts double-free partitions, ranks A320340.
%Y A364907 Cf. A116861, A364350, A364839, A364911, A364912, A364913, A364914, A364915, A365002, A365003.
%K A364907 nonn
%O A364907 0,3
%A A364907 _Gus Wiseman_, Aug 18 2023
%E A364907 a(9)-a(26) from _Alois P. Heinz_, Jan 28 2024