update to A124350: Numbers of Hamiltonian paths on the n-prism graph.

Sat Feb 9 01:45:48 CET 2008

Neil, Eric, SeqFans,

I've also got the following formula for the number of Hamiltonian
(directed) circuits in circulant graphs C_n(1,2) (in particular, in
n-antiprism graph A124353):

a(n) = 2*(n + 3*A000930(n) - 2*A000930(n-1)), for even n
a(n) = 2*(n + 3*A000930(n) - 2*A000930(n-1) + 1), for odd n

Later I found that a similar formula (but in the recurrent form) is
derived in the paper:

Mordecai J. Golin and Yiu Cho Leung.
Unhooking Circulant Graphs: A Combinatorial Method for Counting
Spanning Trees, Hamiltonian Cycles and other Parameters.
Technical report HKUST-TCSC-2004-02.
http://www.cse.ust.hk/tcsc/RR/2004-02.ps.gz

Actually, the technique from this paper can be used to compute
combinatorial parameters of other circulant graph.

There is some disagreement on how to define initial terms of these
sequences. Namely, the recurrent formula and the formula formula
suggest one option, while the natural interpretation as strings over
the alphabet {-2, -1, 1, 2} (see A137725 below) suggests another
option. Therefore, I decided to leave the offset of A124353 and give
the interpretation and other descriptions only in A137725 / A137726.

I suggest the following update to A124353 and two new related sequences:

%I A124353
%S A124353 32,58,112,220,450,938,1982,4220,9022,19332,41472,89022,191150,410506,881656,1893634,
%T A124353 4067256,8735972,18763898,40302866,86566390,185935764,399371142,857808780,1842486536,
%U A124353 3957474934,8500256470,18257692546,39215680080,84231321290,180920373632,388598695916
%N A124353 Number of (directed) Hamiltonian circuits on the n-antiprism graph.
%F A124353 a(n) = 2*(n + 3*A000930(2*n) - 2*A000930(2*n)) =
A137725(2*n) = 2*A137726(2*n)
%F A124353 a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) + a(n-5) or a(n) =
2*a(n-1) + a(n-2) - a(n-3) - a(n-4) - 12.
%H A124353 Eric Weisstein's World of Mathematics, <a
heref="http://mathworld.wolfram.com/AntiprismGraph.html">Antiprism
Graph</a> and <a
href="http://mathworld.wolfram.com/HamiltonianCircuit.html">Hamiltonian
Circuit</a>.
%H A124353 Mordecai J. Golin and Yiu Cho Leung, <a
href="http://www.cse.ust.hk/tcsc/RR/2004-02.ps.gz">Unhooking Circulant
Graphs: A Combinatorial Method for Counting Spanning Trees,
Hamiltonian Cycles and other Parameters</a>. Technical report
HKUST-TCSC-2004-02.
%Y A124353 Cf. A124352.
%Y A124353 Adjacent sequences: A124350 A124351 A124352 this_sequence
A124354 A124355 A124356
%Y A124353 Sequence in context: A033907 A033549 A117478 this_sequence
A008434 A130447 A116284
%K A124353 nonn,more
%O A124353 3,1
%A A124353 Eric Weisstein (eric(AT)weisstein.com), Oct 27, 2006
%E A124353 Formulas and further terms from Max Alekseyev
(maxal(AT)cs.ucsd.edu), Feb 8, 2008

%I A137725
%S A137725 4,4,16,18,24,32,46,58,82,112,158,220,316,450,650,938,1364,1982,2892,4220,6170,9022,13206,
%T A137725 19332,28314,41472,60760,89022,130446,191150,280120,410506,601600,881656,1292102,
%U A137725 1893634,2775226,4067256,5960822,8735972,12803156,18763898,27499794,40302866,59066684
%N A137725 Number of sequences of length n with elements
{-2,-1,+1,+2}, such that the sum of elements of the whole sequence but
of no proper subsequence equals 0 modulo n. For n>=4, the number of
Hamiltonian (directed) circuits on the circulant graph C_n(1,2).
%C A137725 Number of 1-D walks with jumps to next-nearest neighbors
with n steps, starting at 0 and ending at -2n, -n, 0, n, or 2n, such
that every point is visited at most once, and every pair of points at
the distance n contains at least one unvisited point (not counting the
ending visit). Cf. A092765.
%C A137725 For n>1, the number of circular permutations (counted up to
rotations) of {0, 1,...,n-1} such that the distance between every two
adjacent elements is -2,-1,1,or 2 modulo n. Cf. A003274.
%F A137725 For even n>=4, a(n) = 2*(n + 3*A000930(n) - 2*A000930(n));
for odd n>=3, a(n) = 2*(n + 3*A000930(n) - 2*A000930(n)+1).
%F A137725 For n>8, a(n) = 2*a(n-1) - a(n-3) - a(n-5) + a(n-6) or a(n)
= a(n-1) + a(n-2) - a(n-5) - 4.
%H A137725 Eric Weisstein's World of Mathematics, <a
href="http://mathworld.wolfram.com/CirculantGraph.html">Circulant
Graph</a> and <a
href="http://mathworld.wolfram.com/HamiltonianCircuit.html">Hamiltonian
Circuit</a>.
%H A137725 Mordecai J. Golin and Yiu Cho Leung, <a
href="http://www.cse.ust.hk/tcsc/RR/2004-02.ps.gz">Unhooking Circulant
Graphs: A Combinatorial Method for Counting Spanning Trees,
Hamiltonian Cycles and other Parameters</a>. Technical report
HKUST-TCSC-2004-02.
%Y A137725 Cf. A124353, A137726
%K A137725 nonn
%O A137725 1,1
%A A137725 Max Alekseyev (maxal(AT)cs.ucsd.edu), Feb 8, 2008

%I A137726
%S A137726 2,2,8,9,12,16,23,29,41,56,79,110,158,225,325,469,682,991,1446,2110,3085,4511,6603,9666,
%T A137726 14157,20736,30380,44511,65223,95575,140060,205253,300800,440828,646051,946817,
%U A137726 1387613,2033628,2980411,4367986,6401578,9381949,13749897,20151433,29533342,
%N A137726 Number of sequences of length n with elements
{-2,-1,+1,+2}, counted up to simultaneous reversal and negation, such
that the sum of elements of the whole sequence but of no proper
subsequence equals 0 modulo n. For n>=4, the number of Hamiltonian
(undirected) cycles on the circulant graph C_n(1,2).
%C A137726 For n>1, the number of circular permutations (counted up to
rotations and reversals) of {0, 1,...,n-1} such that the distance
between every two adjacent elements is -2,-1,1,or 2 modulo n.
%F A137726 For even n>=4, a(n) = n + 3*A000930(n) - 2*A000930(n); for
odd n>=3, a(n) = n + 3*A000930(n) - 2*A000930(n)+1.
%F A137726 For n>8, a(n) = 2*a(n-1) - a(n-3) - a(n-5) + a(n-6) or a(n)
= a(n-1) + a(n-2) - a(n-5) - 2.
%F A137726 a(n) = A137725(n) / 2.
%H A137726 Eric Weisstein's World of Mathematics, <a
href="http://mathworld.wolfram.com/CirculantGraph.html">Circulant
Graph</a>
%H A137726 Mordecai J. Golin and Yiu Cho Leung, <a
href="http://www.cse.ust.hk/tcsc/RR/2004-02.ps.gz">Unhooking Circulant
Graphs: A Combinatorial Method for Counting Spanning Trees,
Hamiltonian Cycles and other Parameters</a>. Technical report
HKUST-TCSC-2004-02.
%Y A137726 Cf. A069241, A124353, A137725
%K A137726 nonn
%O A137726 1,1
%A A137726 Max Alekseyev (maxal(AT)cs.ucsd.edu), Feb 8, 2008

Regards,
Max

On Feb 7, 2008 12:01 PM, Max Alekseyev <maxale at gmail.com> wrote:
> Neil, Eric, SeqFans,
>
> I've got the following formula for the number of directed Hamiltonian
> paths in the n-prism graph:
>
> 4*n*([n^2/2]+1)
>
> Based on this formula I suggest to update A124350 as listed below.
> Eric, please update MathWorld entries referring to A124350 accordingly.
>
> P.S. I've also prepended three initial terms, computed from the
> formula above, despite that the n-prism graph is not defined for n<3.
>
> Regards,
> Max
>
> %I A124350
> %S A124350 0,4,24,60,144,260,456,700,1056,1476,2040,2684,3504,4420,5544,6780,8256,9860,11736,13756,
> %T A124350 16080,18564,21384,24380,27744,31300,35256,39420,44016,48836,54120,59644,65664,71940,
> %U A124350 78744,85820,93456,101380,109896,118716,128160,137924,148344,159100,170544,182340
> %N A124350 4*n*([n^2/2]+1). For n>=3, the number of directed
> Hamiltonian paths on the n-prism graph.
> %F A124350 a(n) = 4*n*([n^2/2]+1)
> %H A124350 Eric Weisstein's World of Mathematics, <a
> href="http://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian
> Path</a>
> %Y A124350 Cf. A124349.
> %Y A124350 Adjacent sequences: A124347 A124348 A124349 this_sequence
> A124351 A124352 A124353
> %Y A124350 Sequence in context: A043478 A044311 A044692 this_sequence
> A039497 A135199 A112065
> %K A124350 nonn
> %O A124350 0,2
> %A A124350 Eric Weisstein (eric(AT)weisstein.com), Oct 26, 2006
> %E A124350 Formula and further terms from Max Alekseyev
> (maxal(AT)cs.ucsd.edu), Feb 7, 2008
>

Dear Seqfans,

Max A. told me about this sequence when I was visiting San Diego.
He says he has no time right now to work on such problems himself,
and invites others to do so.
In particular:
- is there a formula for this sequence?
- what if we start with 4 letters: abcd? Or k letters?
- what if we start with k different letters and fix the number, d say, of duplications?

Neil

%I A135473
%S A135473 1,3,8,21,54,138,355,924,2432,6461,17301,46657,126656,345972,950611,
%T A135473 2626253
%N A135473 a(n) = number of strings of length n that can be obtained by starting with abc and doubling any substring in place.
%O A135473 3,2
%K A135473 nonn,more
%e A135473 n=3: abc
%e A135473 n=4: aabc, abbc, abcc
%e A135473 n=5: aaabc, abbbc, abccc, aabbc, aabcc, abbcc, ababc, abcbc
%A A135473 Max Alekseyev (maxal(AT)cs.ucsd.edu), Jan 07 2008