A192513 Number of Hamiltonian cycles in the 3-ary de Bruijn graph.
2, 4, 24, 64, 512, 1728, 13312, 32768, 373248, 1310720, 10903552, 35831808, 287965184, 1240465408, 10319560704, 26843545600, 331895275520, 1253826625536, 10690521726976, 34359738368000, 347727917481984, 1307761908383744, 11445236333019136, 30814043149172736
Offset: 1
Keywords
Links
- 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.
- Gabriele Fici and Estéban Gabory, Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform, arXiv:2502.12844 [math.CO], 2025. See Table 1. p. 7.
- Wikipedia, BEST Theorem [_Dmitrii Pasechnik_, Dec 07 2014]
Programs
-
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 *) -
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
Formula
a(n) = A094678(n)*2^(n-1) for n > 1. [Joerg Arndt, Dec 07 2014, amended by Georg Fischer, Jun 21 2020]
Extensions
More terms from Dmitrii Pasechnik, Dec 07 2014
Comments