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

Author

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

Keywords

• nonn

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]

Examples

			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.
		

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
• Gabriele Fici and Estéban Gabory, Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform, arXiv:2502.12844 [math.CO], 2025. See Table 1. p. 7.
• 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.

Crossrefs

Cf. A003473.

Programs

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 *)

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

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.