OFFSET
0,3
FORMULA
G.f.: ((1-x)^3 * (1+x)^2 * (1+x-x^2)) / ((1-x-x^2) * (1-2*x^2)^2) (conjectured). - David Radcliffe, May 03 2015
EXAMPLE
a(2)=2: {0,1}, {0,-1}.
a(3)=4: {0,1,2}, {0,1,0}, {0,-1,0}, {0,-1,-2}.
a(4)=7: There are two choices for each successive x_k, but {0,1,0,-1} and {0,-1,0,1} are equivalent, so a(4)=7 rather than 8.
a(5)=13: Now there are 3 pairs of equivalences, namely (writing a for -1, b for -2) 01210 ~ 01012, 010a0 ~ 0a010, 0aba0 ~ 0a0ab. So a(5) = 16 - 3 = 13. - N. J. A. Sloane, May 03 2015
PROG
(Python)
def generate_paths(n):
if n == 0:
yield (), 0
else:
results = set()
for p, last in generate_paths(n-1):
q = tuple(sorted(p + (last, )))
results.add((q, last+1))
results.add((q, last-1))
for p, last in results:
yield p, last
def count_paths(n):
results = set()
for p, last in generate_paths(n):
q = tuple(sorted(p + (last, )))
if not (q in results):
results.add(q)
return len(results)
print([count_paths(n) for n in range(15)])
(Python)
from itertools import product, accumulate
def A254007(n): return 1 if n == 0 else len(set(tuple(sorted(accumulate(d))) for d in product((-1, 1), repeat=n-1))) # Chai Wah Wu, Nov 13 2021
CROSSREFS
KEYWORD
nonn,nice,more
AUTHOR
John J. Harrison, May 02 2015
EXTENSIONS
More terms from David Radcliffe, May 03 2015
a(29)-a(33) from Bert Dobbelaere, Dec 31 2018
a(0) = 1 prepended by Joerg Arndt, Jan 01 2019
STATUS
approved