login
Number of closed walks of length 2*n on the 4-cube.
8

%I #52 Nov 10 2024 21:45:29

%S 1,4,40,544,8320,131584,2099200,33562624,536903680,8590065664,

%T 137439477760,2199025352704,35184380477440,562949986975744,

%U 9007199388958720,144115188612726784,2305843011361177600

%N Number of closed walks of length 2*n on the 4-cube.

%C With interpolated zeros this has a(n) = (6*0^n + 4^n + (-4)^n + 4*2^n + 4*(-2)^n)/16 and counts closed walks of length n at a vertex of the 4-cube. [Typo corrected by _Alexander R. Povolotsky_, May 26 2008]

%C Also, cogrowth sequence of the 16-element group C2^4. - _Sean A. Irvine_, Nov 10 2024

%H Vincenzo Librandi, <a href="/A092812/b092812.txt">Table of n, a(n) for n = 0..200</a>

%H G. R. Franssens, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Franssens/franssens13.html">On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.

%H Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, <a href="http://arxiv.org/abs/1112.0643">How big is BCI fragment of BCK logic</a>, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]

%H L. Reyzin, Mathoverflow, <a href="https://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube">Number of closed walks on an n-cube</a>.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (20,-64).

%F G.f.: (1-16*x+24*x^2)/((1-4*x)*(1-16*x)).

%F a(n) = 3*0^n/8 + 16^n/8 + 4^n/2.

%F From _Peter Bala_, Nov 13 2006: (Start)

%F E.g.f.: cosh^4(x).

%F O.g.f.: 1/(1-4*1*x/(1-3*2*x/(1-2*3*x/(1-1*4*x)))) (continued fraction). (End)

%F (-1)^n*a(n) = Sum_{k=0..n} A086872(n,k)*(-5)^(n-k). - _Philippe Deléham_, Aug 17 2007

%F a(n) = 20*a(n-1) - 64*a(n-2); a(0) = 1, a(1) = 4, a(2) = 40. - _Harvey P. Dale_, Aug 23 2011

%F a(n) = 4*A026244(n-1), n > 0. - _R. J. Mathar_, Oct 24 2014

%F a(n) = (1/2^4)*Sum_{j = 0..4} binomial(4, j)*(4 - 2*j)^(2*n). See Reyzin link. - _Peter Bala_, Jun 03 2019

%t CoefficientList[Series[(1-16x+24x^2)/((1-4x)(1-16x)),{x,0,30}],x] (* or *) Join[{1},LinearRecurrence[{20,-64},{4,40},30]] (* _Harvey P. Dale_, Aug 23 2011 *)

%o (Magma) [3*0^n/8+16^n/8+4^n/2: n in [0..30]]; // _Vincenzo Librandi_, May 31 2011

%Y Essentially the same as A075878.

%Y Cf. A026244, A081294, A054879, A121822.

%K easy,nonn,changed

%O 0,2

%A _Paul Barry_, Mar 11 2004

%E Title improved by _Sean A. Irvine_ at the suggestion of _Peter Bala_, Jun 04 2019