The OEIS is supported by the many generous donors to the OEIS Foundation. 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). 7
 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 [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: A091155 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

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

Last modified October 1 16:19 EDT 2022. Contains 357149 sequences. (Running on oeis4.)