A066443 Number of distinct paths of length 2n+1 along edges of a unit cube between two fixed adjacent vertices.

1, 7, 61, 547, 4921, 44287, 398581, 3587227, 32285041, 290565367, 2615088301, 23535794707, 211822152361, 1906399371247, 17157594341221, 154418349070987, 1389765141638881, 12507886274749927, 112570976472749341

Offset: 0

Author

John W. Layman, Aug 12 2002

Keywords

• nonn
• easy

Comments

All members of sequence are also hex, or central hexagonal, numbers (A003215). (If n is a hex number, 9n - 2 is always a hex number; see recurrence.) - Matthew Vandermast, Mar 30 2003

The sequence 1,1,7,61,547,... with g.f. (1-9x+6x^2)/((1-x)(1-9x)) and a(n) = A054879(n)/3 + 2*0^n/3 gives the denominators in the probability that a random walk on the cube returns to its starting corner on the 2n-th step. - Paul Barry, Mar 11 2004

Equals row sums of even row terms of triangle A158303. - Gary W. Adamson, Mar 15 2009

It appears that a(n) is the n-th record value in A120437, which gives the differences of A037314 (positive integers n such that the sum of the base 3 digits of n equals the sum of the base 9 digits of n). - John W. Layman, Dec 14 2010

Numbers in base 9 are 1, 6+1, 66+1, 666+1, 6666+1, 66666+1, etc.; that is, n 6's + 1. - Yuchun Ji, Aug 15 2019

All prime factors of a(n) are 1 mod 6. In addition, if n is not 1 mod 3 (first index being n=0), then 3 is a cubic residue modulo all prime factors of a(n). This provides a simple proof that there are infinitely many primes 1 mod 6 that have 3 as a cubic residue. - William Hu, Jul 26 2024

Examples

			From _Michael B. Porter_, Aug 22 2016: (Start)
Give coordinates (a,b,c) to the vertices of the cube, where a, b, and c are either 0 or 1. For n = 1, the a(1) = 7 paths of length 2n + 1 = 3 from (0,0,0) to (0,0,1) are:
(0,0,0) -> (0,0,1) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (0,0,1) -> (0,1,1) -> (0,0,1)
(0,0,0) -> (0,0,1) -> (1,0,1) -> (0,0,1)
(0,0,0) -> (0,1,0) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (0,1,0) -> (0,1,1) -> (0,0,1)
(0,0,0) -> (1,0,0) -> (0,0,0) -> (0,0,1)
(0,0,0) -> (1,0,0) -> (1,0,1) -> (0,0,1) (End)
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• G. Benkart and D. Moon, A Schur-Weyl Duality Approach to Walking on Cubes, arXiv preprint arXiv:1409.8154 [math.RT], 2014 and Ann. Combin. 20 (3) (2016) 397-417.
• E. Estrada and J. A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013. - _N. J. A. Sloane_, Feb 28 2013
• E. Estrada and J. A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
• M. Kac, Random walk and the theory of Brownian motion, Amer. Math. Monthly, 54:369-391, 1947.
• R. J. Mathar, Counting Walks on Finite Graphs, Nov 2020, Section 5.
• Vladimir Pletser, Congruence conditions on the number of terms in sums of consecutive squared integers equal to squared integers, arXiv:1409.7969 [math.NT], 2014.
• Eric Weisstein's World of Mathematics, Repunit
• Index entries for linear recurrences with constant coefficients, signature (10,-9).

Crossrefs

Cf. A158303, A037314, A120437, A083234 (binomial transform), A083233 (inverse binomial transform), A054879 (recurrent walks), A125857 (walks ending on face diagonal), A054880 (walks ending on space diagonal).

Programs

Magma

[(3^(2*n+1)+1)/4: n in [0..20]]; // Vincenzo Librandi, Jun 16 2011

Maple

seq((3^(2*n+1) + 1)/4, n=0..18); # Zerinvary Lajos, Jun 16 2007

Mathematica

NestList[9 # - 2 &, 1, 18] (* or *)
Table[(3^(2 n + 1) + 1)/4, {n, 0, 18}] (* or *)
CoefficientList[Series[(1 - 3 x)/((1 - x) (1 - 9 x)), {x, 0, 18}], x] (* Michael De Vlieger, Aug 22 2016 *)

PARI

a(n)=3^(2*n+1)\/4 \\ Charles R Greathouse IV, Jul 02 2013

PARI

Vec((1-3*x)/((1-x)*(1-9*x)) + O(x^50)) \\ Altug Alkan, Nov 13 2015

Formula

a(n) = (3^(2*n+1)+1)/4. - Vladeta Jovovic, Dec 22 2002

a(n) = 9*a(n-1) - 2. - Matthew Vandermast, Mar 30 2003

From Paul Barry, Apr 21 2003: (Start)

G.f.: (1-3*x)/((1-x)*(1-9*x)).

E.g.f.: (3*exp(9*x) + exp(x))/4. (End)

a(n) = (-1)^n times the (i, i)-th element of M^n (for any i), where M = ((1, 1, 1, -2), (1, 1, -2, 1), (1, -2, 1, 1), (-2, 1, 1, 1)). - Simone Severini, Nov 25 2004

a(n) = Sum_{k=0..n} binomial(2*n+1, 2*k)*4^(n-k). - Paul Barry, Jan 22 2005

a(n) = A054880(n) + 1.

a(n) = A057660(3^n). - Henry Bottomley, Nov 08 2015

a(n) = Sum_{k=0..2n} (-3)^k == 1 + Sum_{k=1..n} 2*3^(2k-1). - Bob Selcoe, Aug 21 2016

a(n) = 3^(2*n+1) * a(-1-n) for all n in Z. - Michael Somos, Jul 02 2017

a(n) = 6*A002452(n) + 1. - Yuchun Ji, Aug 15 2019

Extensions

Corrected by Vladeta Jovovic, Dec 22 2002