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
KEYWORD
nonn
AUTHOR
Clone Lester (aflms(AT)cts1.cats.alaska.edu)
STATUS
approved