A039822 Number of different coefficient values in expansion of Product_{i=1..n} (1+q^i).

1, 1, 1, 2, 2, 3, 5, 8, 14, 18, 24, 30, 37, 43, 50, 58, 66, 74, 83, 93, 103, 113, 124, 136, 148, 160, 173, 187, 201, 215, 230, 246, 262, 278, 295, 313, 331, 349, 368, 388, 408, 428, 449, 471, 493, 515, 538, 562, 586, 610, 635, 661, 687, 713, 740, 768, 796, 824

Offset

0,4

Links

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Formula

It appears that for n>11, a(n) = floor((n^2+3n-6)/4). - Ralf Stephan, Jun 10 2005

Prog

(PARI) a(n) = #Set(Vec(prod(k=1, n, 1+x^k))); \\ Seiichi Manyama, Feb 01 2024
(Python)
from collections import Counter
def A039822(n):
    c = {0:1}
    for k in range(1, n+1):
        d = Counter(c)
        for j in c:
            d[j+k] += c[j]
        c = d
    return len(set(c.values()))+int(max(c)+1>len(c)) # Chai Wah Wu, Feb 04 2024

Crossrefs

Cf. A000009.

Sequence in context: A022863 A236393 A350504 * A025591 A028409 A348850

Adjacent sequences: A039819 A039820 A039821 * A039823 A039824 A039825

Keyword

nonn

Author

Olivier Gérard

Extensions

a(0)=1 prepended by Seiichi Manyama, Feb 01 2024

Status

approved