A027362 Number of Hamiltonian cycles in the directed graph with 2n nodes {0..2n-1} and edges from each i to 2i (mod 2n) and to 2i+1 (mod 2n).

1, 1, 1, 2, 3, 4, 7, 16, 21, 48, 93, 128, 315, 448, 675, 2048, 3825, 5376, 13797, 24576, 27783, 95232, 182183, 262144, 629145, 1290240, 1835001, 3670016, 9256395, 11059200, 28629151, 67108864, 97327197, 250675200, 352149525, 704643072, 1857283155, 3616800768

Offset

1,4

Comments

Also the number of binary normal polynomials of degree n. [Joerg Arndt, Nov 28 2004]. For a proof, see S. H. Chan et al. (2015) and S. V. Duzhin and D. V. Pasechnik (2014) below. [Dmitrii Pasechnik, Dec 05 2014]

Also the number of spanning trees (more precisely, the absolute value of a maximal minor of the Laplacian matrix) of the directed graph G_n with n nodes {0..n-1} and edges from each i to 2i (mod n) and to 2i+1 (mod n). This gives a connection to sandpile groups. The bijection between this and the original description can be obtained by noticing that the line graph of G_n is isomorphic to the graph G_2n (i.e. the graph in the original description of the sequence), thus relating the Hamiltonian cycles in G_2n and the Eulerian cycles in G_n. Finally, the latter are in bijection with directed spanning trees, rooted at a fixed vertex, in G_n by BEST Theorem (see the wikipedia article on it). [Dmitrii Pasechnik, Aug 14 and Nov 13 2011]

Also the number of invertible n x n circulant matrices over GF(2), divided by n. [Joerg Arndt, Aug 15 2011]. For a proof, see S. H. Chan et al. (2015) below. [Dmitrii Pasechnik, Dec 05 2014]

References

Joe McCauley, Posting to sci.math (by jmccaul(AT)iatcmail.ed.ray.com). [Date?]

Links

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 130 terms from Joerg Arndt)

Joerg Arndt, Matters Computational (The Fxtbook), p.904.

Swee Hong Chan, Henk D. L. Hollmann and Dmitrii V. Pasechnik, Critical groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, arXiv: 1312.2114 [math.CO], 2013.

Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, arXiv:1405.0113 [math.CO], (1-May-2014).

Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, Journal of Algebra (2015), pp. 268-295. [Dmitrii Pasechnik, Dec 05 2014]

S. V. Duzhin, D. V. Pasechnik, Groups acting on necklaces and sandpile groups, 2014. See Section 3, History. - N. J. A. Sloane, Jun 30 2014

Lionel Levine, Sandpile groups and spanning trees of directed line graphs, arXiv:0906.2809 [math.CO], 2009-2010.

Lionel Levine, Sandpile groups and spanning trees of directed line graphs, J. Combin. Th. (A) 118(2011), 350-364.

Wikipedia, BEST Theorem.

Formula

a(n) = A003473(n)/n. - Vladeta Jovovic, Sep 09 2003

a(2^k) = 2^(2^k-k-1) from L. Levine 2011, Theorem 1.3.

Example

The solutions for n=1, 2 and 3 are
0 1;
0 1 3 2;
0 1 2 5 4 3.
The 4 solutions for n=6 are
0 1 2 4 8 5 11 10 9 7 3 6;
0 1 2 5 11 10 8 4 9 7 3 6;
0 1 3 7 2 4 8 5 11 10 9 6;
0 1 3 7 2 5 11 10 8 4 9 6.

Mathematica

p = 2; numNormalp[n_] := Module[{r, i, pp}, pp = 1; Do[r = MultiplicativeOrder[p, d]; i = EulerPhi[d]/r; pp *= (1 - 1/p^r)^i, {d, Divisors[n]}]; Return[pp]];
a[n_] := Module[{t, q, pp}, t = 1;  q = n; While[0 == Mod[q, p], q /= p; t += 1]; pp = numNormalp[q]; pp *= p^n/n; Return[pp]];
Array[a, 40] (* Jean-François Alcover, Jul 21 2018, after Joerg Arndt *)

Prog

(PARI) /* from p.907 of the Fxtbook */
p=2; /* global */
num_normal_p(n)=
{
    local( r, i, pp );
    pp = 1;
    fordiv (n, d,
        r = znorder(Mod(p, d));
        i = eulerphi(d)/r;
        pp *= (1 - 1/p^r)^i;
    );
    return( pp );
}
num_normal(n)=
{
    local( t, q, pp );
    t = 1;  q = n;
    while ( 0==(q%p), q/=p; t+=1; );
    /* here: n==q*p^t */
    pp = num_normal_p(q);
    pp *= p^n/n;
    return( pp );
}
a(n) = num_normal(n);
vector(66, n, a(n)) /* Joerg Arndt, Jul 03 2011 */
(Sage) # version 4.7
def dg(n): # this gives the graph in the 3rd description
    g = DiGraph(loops=True)
    for i in range(n): g.add_vertex();
    for i in range(n):
        g.add_edge(i, mod(2*i, n));
        g.add_edge(i, mod(1+2*i, n));
    return g;
def A027362(n): # this gives the number of spanning trees
    return dg(n).laplacian_matrix().submatrix(1, 1).det();
# Dmitrii Pasechnik, Aug 14 2011

Crossrefs

Cf. A003473.

Sequence in context: A359193 A355457 A254432 * A068194 A179985 A338928

Adjacent sequences: A027359 A027360 A027361 * A027363 A027364 A027365

Keyword

nonn

Author

Clone Lester (aflms(AT)cts1.cats.alaska.edu)

Status

approved