cp's OEIS Frontend

A192513 Number of Hamiltonian cycles in the 3-ary de Bruijn graph.

%I A192513 #43 Feb 19 2025 01:04:54
%S A192513 2,4,24,64,512,1728,13312,32768,373248,1310720,10903552,35831808,
%T A192513 287965184,1240465408,10319560704,26843545600,331895275520,
%U A192513 1253826625536,10690521726976,34359738368000,347727917481984,1307761908383744,11445236333019136,30814043149172736
%N A192513 Number of Hamiltonian cycles in the 3-ary de Bruijn graph.
%C A192513 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).
%C A192513 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]
%H A192513 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 A192513 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.
%H A192513 Gabriele Fici and Estéban Gabory, <a href="https://arxiv.org/abs/2502.12844">Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform</a>, arXiv:2502.12844 [math.CO], 2025. See Table 1. p. 7.
%H A192513 Wikipedia, <a href="http://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a> [_Dmitrii Pasechnik_, Dec 07 2014]
%F A192513 a(n) = A094678(n)*2^(n-1) for n > 1. [_Joerg Arndt_, Dec 07 2014, amended by _Georg Fischer_, Jun 21 2020]
%t A192513 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]];
%t A192513 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)]];
%t A192513 Array[a, 30] (* _Jean-François Alcover_, Jul 22 2018, after _Joerg Arndt_ *)
%o A192513 (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
%Y A192513 Cf. A003474, A094678.
%Y A192513 Cf. A003473, A027362.
%K A192513 nonn
%O A192513 1,1
%A A192513 _Joerg Arndt_, Jul 03 2011
%E A192513 More terms from _Dmitrii Pasechnik_, Dec 07 2014