login
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.
1

%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