%I #73 Nov 14 2021 00:44:06
%S 1,1,2,4,7,13,22,40,66,118,192,338,546,948,1526,2618,4208,7146,11482,
%T 19332,31070,51938,83520,138786,223330,369284,594662,979306,1578064,
%U 2590138,4176394,6836164,11028942,18012562
%N Cardinality of the set of equivalence classes of the set X_n of finite integer sequences {x_1 = 0, x_2, ..., x_n} satisfying |x_k - x_{k+1}| = 1, where two such sequences are deemed equivalent if they are permutations of each other.
%F 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
%e a(2)=2: {0,1}, {0,-1}.
%e a(3)=4: {0,1,2}, {0,1,0}, {0,-1,0}, {0,-1,-2}.
%e 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.
%e 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
%o (Python)
%o def generate_paths(n):
%o if n == 0:
%o yield (), 0
%o else:
%o results = set()
%o for p, last in generate_paths(n-1):
%o q = tuple(sorted(p + (last,)))
%o results.add((q, last+1))
%o results.add((q, last-1))
%o for p, last in results:
%o yield p, last
%o def count_paths(n):
%o results = set()
%o for p, last in generate_paths(n):
%o q = tuple(sorted(p + (last,)))
%o if not (q in results):
%o results.add(q)
%o return len(results)
%o print([count_paths(n) for n in range(15)])
%o (Python)
%o from itertools import product, accumulate
%o 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
%K nonn,nice,more
%O 0,3
%A _John J. Harrison_, May 02 2015
%E More terms from _David Radcliffe_, May 03 2015
%E a(29)-a(33) from _Bert Dobbelaere_, Dec 31 2018
%E a(0) = 1 prepended by _Joerg Arndt_, Jan 01 2019