|
%I #97 Jul 21 2018 11:22:23
%S 1,1,1,2,3,4,7,16,21,48,93,128,315,448,675,2048,3825,5376,13797,24576,
%T 27783,95232,182183,262144,629145,1290240,1835001,3670016,9256395,
%U 11059200,28629151,67108864,97327197,250675200,352149525,704643072,1857283155,3616800768
%N 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 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 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 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 Joe McCauley, Posting to sci.math (by jmccaul(AT)iatcmail.ed.ray.com). [Date?]
%H 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 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.904.
%H 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 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 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 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 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 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 Wikipedia, <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a>.
%F a(n) = A003473(n)/n. - _Vladeta Jovovic_, Sep 09 2003
%F a(2^k) = 2^(2^k-k-1) from L. Levine 2011, Theorem 1.3.
%e The solutions for n=1, 2 and 3 are
%e 0 1;
%e 0 1 3 2;
%e 0 1 2 5 4 3.
%e The 4 solutions for n=6 are
%e 0 1 2 4 8 5 11 10 9 7 3 6;
%e 0 1 2 5 11 10 8 4 9 7 3 6;
%e 0 1 3 7 2 4 8 5 11 10 9 6;
%e 0 1 3 7 2 5 11 10 8 4 9 6.
%t 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 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 Array[a, 40] (* _Jean-François Alcover_, Jul 21 2018, after _Joerg Arndt_ *)
%o (PARI) /* from p.907 of the Fxtbook */
%o p=2; /* global */
%o num_normal_p(n)=
%o {
%o local( r, i, pp );
%o pp = 1;
%o fordiv (n, d,
%o r = znorder(Mod(p,d));
%o i = eulerphi(d)/r;
%o pp *= (1 - 1/p^r)^i;
%o );
%o return( pp );
%o }
%o num_normal(n)=
%o {
%o local( t, q, pp );
%o t = 1; q = n;
%o while ( 0==(q%p), q/=p; t+=1; );
%o /* here: n==q*p^t */
%o pp = num_normal_p(q);
%o pp *= p^n/n;
%o return( pp );
%o }
%o a(n) = num_normal(n);
%o vector(66,n,a(n)) /* _Joerg Arndt_, Jul 03 2011 */
%o (Sage) # version 4.7
%o def dg(n): # this gives the graph in the 3rd description
%o g = DiGraph(loops=True)
%o for i in range(n): g.add_vertex();
%o for i in range(n):
%o g.add_edge(i, mod(2*i, n));
%o g.add_edge(i, mod(1+2*i, n));
%o return g;
%o def A027362(n): # this gives the number of spanning trees
%o return dg(n).laplacian_matrix().submatrix(1, 1).det();
%o # _Dmitrii Pasechnik_, Aug 14 2011
%Y Cf. A003473.
%K nonn
%O 1,4
%A Clone Lester (aflms(AT)cts1.cats.alaska.edu)
|
