cp's OEIS Frontend

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

%I A027362 #103 Feb 19 2025 01:05:07
%S A027362 1,1,1,2,3,4,7,16,21,48,93,128,315,448,675,2048,3825,5376,13797,24576,
%T A027362 27783,95232,182183,262144,629145,1290240,1835001,3670016,9256395,
%U A027362 11059200,28629151,67108864,97327197,250675200,352149525,704643072,1857283155,3616800768
%N 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).
%C A027362 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]
%C A027362 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]
%C A027362 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]
%D A027362 Joe McCauley, Posting to sci.math (by jmccaul(AT)iatcmail.ed.ray.com). [Date?]
%H A027362 Joerg Arndt and Alois P. Heinz, <a href="/A027362/b027362.txt">Table of n, a(n) for n = 1..1000</a> (first 130 terms from Joerg Arndt)
%H A027362 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.904.
%H A027362 Swee Hong Chan, Henk D. L. Hollmann and Dmitrii V. Pasechnik, <a href="http://arxiv.org/abs/1312.2114">Critical groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields</a>, arXiv: 1312.2114 [math.CO], 2013.
%H A027362 Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, <a href="http://arxiv.org/abs/1405.0113">Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields</a>, arXiv:1405.0113 [math.CO], (1-May-2014).
%H A027362 Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, <a href="http://dx.doi.org/10.1016/j.jalgebra.2014.08.029">Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields</a>, Journal of Algebra (2015), pp. 268-295. [_Dmitrii Pasechnik_, Dec 05 2014]
%H A027362 S. V. Duzhin, D. V. Pasechnik, <a href="ftp://pdmi.ras.ru/pub/publicat/znsl/v421/p081.pdf">Groups acting on necklaces and sandpile groups</a>, 2014. See Section 3, History. - _N. J. A. Sloane_, Jun 30 2014
%H A027362 Gabriele Fici and Estéban Gabory, <a href="https://arxiv.org/abs/2502.12844">Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform</a>, arXiv:2502.12844 [math.CO], 2025. See Table 1. p. 7.
%H A027362 Lionel Levine, <a href="http://arxiv.org/abs/0906.2809">Sandpile groups and spanning trees of directed line graphs</a>, arXiv:0906.2809 [math.CO], 2009-2010.
%H A027362 Lionel Levine, <a href="http://dx.doi.org/10.1016/j.jcta.2010.04.001">Sandpile groups and spanning trees of directed line graphs</a>, J. Combin. Th. (A) 118(2011), 350-364.
%H A027362 Wikipedia, <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a>.
%F A027362 a(n) = A003473(n)/n. - _Vladeta Jovovic_, Sep 09 2003
%F A027362 a(2^k) = 2^(2^k-k-1) from L. Levine 2011, Theorem 1.3.
%e A027362 The solutions for n=1, 2 and 3 are
%e A027362   0 1;
%e A027362   0 1 3 2;
%e A027362   0 1 2 5 4 3.
%e A027362 The 4 solutions for n=6 are
%e A027362   0 1 2 4 8 5 11 10 9 7 3 6;
%e A027362   0 1 2 5 11 10 8 4 9 7 3 6;
%e A027362   0 1 3 7 2 4 8 5 11 10 9 6;
%e A027362   0 1 3 7 2 5 11 10 8 4 9 6.
%t A027362 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]];
%t A027362 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]];
%t A027362 Array[a, 40] (* _Jean-François Alcover_, Jul 21 2018, after _Joerg Arndt_ *)
%o A027362 (PARI) /* from p.907 of the Fxtbook */
%o A027362 p=2; /* global */
%o A027362 num_normal_p(n)=
%o A027362 {
%o A027362     local( r, i, pp );
%o A027362     pp = 1;
%o A027362     fordiv (n, d,
%o A027362         r = znorder(Mod(p,d));
%o A027362         i = eulerphi(d)/r;
%o A027362         pp *= (1 - 1/p^r)^i;
%o A027362     );
%o A027362     return( pp );
%o A027362 }
%o A027362 num_normal(n)=
%o A027362 {
%o A027362     local( t, q, pp );
%o A027362     t = 1;  q = n;
%o A027362     while ( 0==(q%p), q/=p; t+=1; );
%o A027362     /* here: n==q*p^t */
%o A027362     pp = num_normal_p(q);
%o A027362     pp *= p^n/n;
%o A027362     return( pp );
%o A027362 }
%o A027362 a(n) = num_normal(n);
%o A027362 vector(66,n,a(n)) /* _Joerg Arndt_, Jul 03 2011 */
%o A027362 (Sage) # version 4.7
%o A027362 def dg(n): # this gives the graph in the 3rd description
%o A027362     g = DiGraph(loops=True)
%o A027362     for i in range(n): g.add_vertex();
%o A027362     for i in range(n):
%o A027362         g.add_edge(i, mod(2*i, n));
%o A027362         g.add_edge(i, mod(1+2*i, n));
%o A027362     return g;
%o A027362 def A027362(n): # this gives the number of spanning trees
%o A027362     return dg(n).laplacian_matrix().submatrix(1, 1).det();
%o A027362 # _Dmitrii Pasechnik_, Aug 14 2011
%Y A027362 Cf. A003473.
%K A027362 nonn
%O A027362 1,4
%A A027362 Clone Lester (aflms(AT)cts1.cats.alaska.edu)