|
| |
|
|
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).
|
|
4
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| Also the number of binary normal polynomials of degree n. [Joerg Arndt, Nov 28 2004]
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 V. 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]
|
|
|
REFERENCES
| Posting to sci.math by jmccaul(AT)iatcmail.ed.ray.com (Joe McCauley).
Lionel Levine, Sandpile groups and spanning trees of directed line graphs, J. Combin. Th. (A) 118(2011), 350-364.
Wikipedia, <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a>.
|
|
|
LINKS
| Joerg Arndt, Table of n, a(n) for n = 1..130
Joerg Arndt, fxtbook, p.904.
|
|
|
FORMULA
| a(n) = A003473(n)/n. - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 09 2003
a(2^k) = 2^(2^k-k-1) from L. Levine 2011, Thm. 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)) /* show terms */ /* 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 V. Pasechnik, Aug 14 2011
|
|
|
CROSSREFS
| Sequence in context: A098010 A088533 A091155 * A068194 A134459 A179985
Adjacent sequences: A027359 A027360 A027361 * A027363 A027364 A027365
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Clone Lester (aflms(AT)cts1.cats.alaska.edu)
|
| |
|
|
