|
|
A192513
|
|
Number of Hamiltonian cycles in the 3-ary de Bruijn graph.
|
|
2
|
|
|
2, 4, 24, 64, 512, 1728, 13312, 32768, 373248, 1310720, 10903552, 35831808, 287965184, 1240465408, 10319560704, 26843545600, 331895275520, 1253826625536, 10690521726976, 34359738368000, 347727917481984, 1307761908383744, 11445236333019136, 30814043149172736
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
The 3-ary de Bruijn graph is the graph with 3*n nodes {0..3*n-1} and edges from each i to 3*i (mod 3*n), 3*i+1 (mod 3*n), and 3*i+2 (mod 3*n).
Correctness of a(n) = A094678(n)*2^(n-1) for all n>1 follows from S. H. Chan et al. below, together with the BEST theorem. [Dmitrii Pasechnik, Dec 07 2014]
|
|
LINKS
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
p = 3; numNormalp[n_] := Module[{r, i, 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 = 1, q = n, pp}, While[0 == Mod[q, p], q /= p; t += 1]; pp = numNormalp[q]; pp *= p^n/n; Return[pp*2^(n - 1)]];
|
|
PROG
|
(PARI) a(n)=if(n==1, return(2)); my(r, i, t=3^n/n<<(n-1)); fordiv(n/3^valuation(n, 3), d, r=znorder(Mod(3, d)); i=eulerphi(d)/r; t*=(1-1/3^r)^i); t \\ See comments. Charles R Greathouse IV, Jan 03 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|