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

%I #117 Aug 28 2024 11:32:44

%S 1,7,61,547,4921,44287,398581,3587227,32285041,290565367,2615088301,

%T 23535794707,211822152361,1906399371247,17157594341221,

%U 154418349070987,1389765141638881,12507886274749927,112570976472749341

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

%C 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

%C 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

%C Equals row sums of even row terms of triangle A158303. - _Gary W. Adamson_, Mar 15 2009

%C 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

%C 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

%C 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

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

%H G. Benkart and D. Moon, <a href="http://arxiv.org/abs/1409.8154">A Schur-Weyl Duality Approach to Walking on Cubes</a>, arXiv preprint arXiv:1409.8154 [math.RT], 2014 and <a href="http://dx.doi.org/10.1007/s00026-016-0311-3">Ann. Combin. 20 (3) (2016) 397-417</a>.

%H E. Estrada and J. A. de la Pena, <a href="http://arxiv.org/abs/1302.1176">From Integer Sequences to Block Designs via Counting Walks in Graphs</a>, arXiv preprint arXiv:1302.1176 [math.CO], 2013. - _N. J. A. Sloane_, Feb 28 2013

%H E. Estrada and J. A. de la Pena, <a href="http://nntdm.net/volume-19-2013/number-3/78-84/">Integer sequences from walks in graphs</a>, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.

%H M. Kac, <a href="http://www.jstor.org/stable/2304386">Random walk and the theory of Brownian motion</a>, Amer. Math. Monthly, 54:369-391, 1947.

%H R. J. Mathar, <a href="/A102518/a102518.pdf">Counting Walks on Finite Graphs</a>, Nov 2020, Section 5.

%H Vladimir Pletser, <a href="http://arxiv.org/abs/1409.7969">Congruence conditions on the number of terms in sums of consecutive squared integers equal to squared integers</a>, arXiv:1409.7969 [math.NT], 2014.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Repunit.html">Repunit</a>

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

%F a(n) = (3^(2*n+1)+1)/4. - _Vladeta Jovovic_, Dec 22 2002

%F a(n) = 9*a(n-1) - 2. - _Matthew Vandermast_, Mar 30 2003

%F From _Paul Barry_, Apr 21 2003: (Start)

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

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

%F 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

%F a(n) = Sum_{k=0..n} binomial(2*n+1, 2*k)*4^(n-k). - _Paul Barry_, Jan 22 2005

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

%F a(n) = A057660(3^n). - _Henry Bottomley_, Nov 08 2015

%F a(n) = Sum_{k=0..2n} (-3)^k == 1 + Sum_{k=1..n} 2*3^(2k-1). - _Bob Selcoe_, Aug 21 2016

%F a(n) = 3^(2*n+1) * a(-1-n) for all n in Z. - _Michael Somos_, Jul 02 2017

%F a(n) = 6*A002452(n) + 1. - _Yuchun Ji_, Aug 15 2019

%e From _Michael B. Porter_, Aug 22 2016: (Start)

%e 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:

%e (0,0,0) -> (0,0,1) -> (0,0,0) -> (0,0,1)

%e (0,0,0) -> (0,0,1) -> (0,1,1) -> (0,0,1)

%e (0,0,0) -> (0,0,1) -> (1,0,1) -> (0,0,1)

%e (0,0,0) -> (0,1,0) -> (0,0,0) -> (0,0,1)

%e (0,0,0) -> (0,1,0) -> (0,1,1) -> (0,0,1)

%e (0,0,0) -> (1,0,0) -> (0,0,0) -> (0,0,1)

%e (0,0,0) -> (1,0,0) -> (1,0,1) -> (0,0,1) (End)

%p seq((3^(2*n+1) + 1)/4, n=0..18); # _Zerinvary Lajos_, Jun 16 2007

%t NestList[9 # - 2 &, 1, 18] (* or *)

%t Table[(3^(2 n + 1) + 1)/4, {n, 0, 18}] (* or *)

%t CoefficientList[Series[(1 - 3 x)/((1 - x) (1 - 9 x)), {x, 0, 18}], x] (* _Michael De Vlieger_, Aug 22 2016 *)

%o (Magma) [(3^(2*n+1)+1)/4: n in [0..20]]; // _Vincenzo Librandi_, Jun 16 2011

%o (PARI) a(n)=3^(2*n+1)\/4 \\ _Charles R Greathouse IV_, Jul 02 2013

%o (PARI) Vec((1-3*x)/((1-x)*(1-9*x)) + O(x^50)) \\ _Altug Alkan_, Nov 13 2015

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

%K nonn,easy

%O 0,2

%A _John W. Layman_, Aug 12 2002

%E Corrected by _Vladeta Jovovic_, Dec 22 2002