login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 6
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 (list; graph; refs; listen; history; text; internal format)
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, 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]

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.

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: A088533 A091155 A254432 * A068194 A134459 A217289

Adjacent sequences:  A027359 A027360 A027361 * A027363 A027364 A027365

KEYWORD

nonn,changed

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 23 22:30 EDT 2017. Contains 283985 sequences.