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

%I #16 Jan 28 2024 20:57:15

%S 1,1,4,13,50,179,696,2619,10119,38867,150407,582065,2260367,8786919,

%T 34225256,133471650,521216494,2037608462,7974105052,31235316275,

%U 122457794193,480473181271,1886555402750,7412471695859,29142658077266,114643347181003,451237737215201

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

%C 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 Alois P. Heinz, <a href="/A364907/b364907.txt">Table of n, a(n) for n = 0..500</a>

%F a(n) = Sum_{m:A056239(m)=n} A364906(m).

%F a(n) = A364912(2n,n).

%F a(n) = A365004(n,n).

%e The a(0) = 1 through a(3) = 13 ways:

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

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

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

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

%e 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, i, m) option remember; `if`(n=0, `if`(m=0, 1, 0),

%p `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 end:

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

%p seq(a(n), n=0..27); # _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,IntegerPartitions[n]}]],{n,0,5}]

%Y The case with no zero coefficients is A000041.

%Y A finer version is A364906.

%Y The version for compositions is A364908, strict A364909.

%Y Using just strict partitions we get A364910, main diagonal of A364916.

%Y Main diagonal of A365004.

%Y A000041 counts integer partitions, strict A000009.

%Y A008284 counts partitions by length, strict A008289.

%Y A323092 counts double-free partitions, ranks A320340.

%Y Cf. A116861, A364350, A364839, A364911, A364912, A364913, A364914, A364915, A365002, A365003.

%K nonn

%O 0,3

%A _Gus Wiseman_, Aug 18 2023

%E a(9)-a(26) from _Alois P. Heinz_, Jan 28 2024