OFFSET
0,2
COMMENTS
Equivalently, a(n) is the number of partitions of n into parts of two kinds where the number of parts of each kind differ by at most one.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
G.f.: Sum_{k>=0} ([y^k] P(x,y))*([y^k] (1 + 2*y)*P(x,y)), where P(x,y) = Product_{k>=1} 1/(1 - y*x^k). - Andrew Howroyd, Jan 12 2025
EXAMPLE
For n = 3, the partitions are (000), (111), (00, 1), (0, 11), (0, 0, 1), (0, 1, 1).
MAPLE
g:= (n, i, t)-> `if`(t>1+n, 0, `if`(n=0, 1, b(n, i, t))):
b:= proc(n, i, t) option remember; add(add(g(n-i*j,
min(n-i*j, i-1), abs(t+2*h-j)), h=0..j), j=`if`(i=1, n, 0..n/i))
end:
a:= n-> g(n$2, 0):
seq(a(n), n=0..42); # Alois P. Heinz, Jan 15 2025
MATHEMATICA
g[n_, i_, t_] := If[t > 1+n, 0, If[n == 0, 1, b[n, i, t]]];
b[n_, i_, t_] := b[n, i, t] = Sum[Sum[g[n-i*j,
Min[n-i*j, i-1], Abs[t+2*h-j]], {h, 0, j}], {j, If[i == 1, n, 0], n/i}];
a[n_] := g[n, n, 0];
Table[a[n], {n, 0, 42}] (* Jean-François Alcover, Feb 02 2025, after Alois P. Heinz *)
PROG
(Python)
n = 0
while True:
m = set()
for i in range(2**n):
t = bin(i)[2:]
t = '0' * (n - len(t)) + t + '2'
l = []
s = 0
for j in range(1, n + 1):
if t[j] != t[j - 1]:
l.append(t[s:j])
s = j
l.sort()
l = tuple(l)
m.add(l)
print(len(m), end=' ')
n += 1
(PARI) seq(n)={my(p=1/prod(k=1, n, 1-y*x^k + O(x*x^n))); Vec(sum(k=0, n\2, polcoef(p, k, y)*(2*polcoef(p, k+1, y) + polcoef(p, k, y))))} \\ Andrew Howroyd, Jan 12 2025
CROSSREFS
KEYWORD
nonn
AUTHOR
Yaroslav Deryavko, Jan 12 2025
STATUS
approved