login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..24.

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.

Wikipedia, BEST Theorem [Dmitrii Pasechnik, Dec 07 2014]

FORMULA

a(n) = A094678(n)*2^(n-1) for n > 1. [Joerg Arndt, Dec 07 2014, amended by Georg Fischer, Jun 21 2020]

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)]];

Array[a, 30] (* Jean-François Alcover, Jul 22 2018, after Joerg Arndt *)

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

Cf. A003474, A094678.

Cf. A003473, A027362.

Sequence in context: A280075 A068506 A272640 * A192384 A119036 A192382

Adjacent sequences: A192510 A192511 A192512 * A192514 A192515 A192516

KEYWORD

nonn

AUTHOR

Joerg Arndt, Jul 03 2011

EXTENSIONS

More terms from Dmitrii Pasechnik, Dec 07 2014

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 3 17:00 EST 2023. Contains 360044 sequences. (Running on oeis4.)