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

1, 4, 40, 544, 8320, 131584, 2099200, 33562624, 536903680, 8590065664, 137439477760, 2199025352704, 35184380477440, 562949986975744, 9007199388958720, 144115188612726784, 2305843011361177600

Offset: 0

Author

Paul Barry, Mar 11 2004

Keywords

• easy
• nonn

Comments

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]

Also, cogrowth sequence of the 16-element group C2^4. - Sean A. Irvine, Nov 10 2024

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• G. R. Franssens, On a number pyramid related to the binomial, Deleham, Eulerian, MacMahon and Stirling number triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.1.
• Katarzyna Grygiel, Pawel M. Idziak and Marek Zaionc, How big is BCI fragment of BCK logic, arXiv preprint arXiv:1112.0643 [cs.LO], 2011. [From _N. J. A. Sloane_, Feb 21 2012]
• L. Reyzin, Mathoverflow, Number of closed walks on an n-cube.
• Index entries for linear recurrences with constant coefficients, signature (20,-64).

Crossrefs

Essentially the same as A075878.

Cf. A026244, A081294, A054879, A121822.

Programs

Magma

[3*0^n/8+16^n/8+4^n/2: n in [0..30]]; // Vincenzo Librandi, May 31 2011

Mathematica

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 *)

Formula

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

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

From Peter Bala, Nov 13 2006: (Start)

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

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

(-1)^n*a(n) = Sum_{k=0..n} A086872(n,k)*(-5)^(n-k). - Philippe Deléham, Aug 17 2007

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

a(n) = 4*A026244(n-1), n > 0. - R. J. Mathar, Oct 24 2014

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

Extensions

Title improved by Sean A. Irvine at the suggestion of Peter Bala, Jun 04 2019