A316706 Number of solutions to k_1 + 2*k_2 + ... + n*k_n = n, where k_i are from {-1,0,1}, i=1..n.

1, 1, 1, 2, 5, 12, 27, 69, 178, 457, 1194, 3178, 8538, 23062, 62726, 171804, 473069, 1308397, 3634075, 10133154, 28352421, 79575702, 223981549, 632101856, 1788172541, 5069879063, 14403962756, 41001479103, 116921037003, 333971884899, 955443681814, 2737387314548, 7853533625522, 22560919253095, 64890249175438, 186854616134794

Offset: 0

Author

Paul D. Hanna, Jul 10 2018

Keywords

• nonn

Comments

a(n) is the coefficient of both x^n and 1/x^n in Product_{k=1..n} (1/x^k + 1 + x^k), while A007576 gives the constant term in the symmetric product.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..700 (first 501 terms from Vaclav Kotesovec)

Crossrefs

Cf. A007576, A059529.

Programs

Mathematica

nmax = 40; p = 1; Flatten[{1, Table[Coefficient[p = Expand[p*(1/x^n + 1 + x^n)], x^n], {n, 1, nmax}]}] (* Vaclav Kotesovec, Jul 11 2018 *)

PARI

{a(n) = polcoeff( prod(k=1,n, 1/x^k + 1 + x^k) + x*O(x^n),n)}
for(n=0,40, print1(a(n),", "))

Python

from collections import Counter
def A316706(n):
    c = {0:1}
    for k in range(1,n+1):
        b = Counter(c)
        for j in c:
            a = c[j]
            b[j+k] += a
            b[j-k] += a
        c = b
    return c[n] # Chai Wah Wu, Feb 05 2024

Formula

a(n) = [x^n] Product_{k=1..n} (1/x^k + 1 + x^k).

a(n) = [x^(n*(n-1)/2)] Product_{k=1..n} (1 + x^k + x^(2*k)).

a(n) = [x^(n*(n+3)/2)] Product_{k=1..n} (1 + x^k + x^(2*k)).

a(n) ~ 3^(n + 1) / (2 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 11 2018