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,2

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

G. Benkart, 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).

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

Example

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)

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

Prog

(Magma) [(3^(2*n+1)+1)/4: n in [0..20]]; // Vincenzo Librandi, Jun 16 2011
(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

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

Sequence in context: A155599 A104093 A015572 * A108448 A218473 A098659

Adjacent sequences: A066440 A066441 A066442 * A066444 A066445 A066446

Keyword

nonn,easy

Author

John W. Layman, Aug 12 2002

Extensions

Corrected by Vladeta Jovovic, Dec 22 2002

Status

approved