A089022 Number of walks of length 2n on the 3-regular tree beginning and ending at some fixed vertex.

1, 3, 15, 87, 543, 3543, 23823, 163719, 1143999, 8099511, 57959535, 418441191, 3043608351, 22280372247, 164008329423, 1213166815047, 9012417249663, 67208553680247, 502920171632943, 3775020828459687, 28415858155984863, 214444848602732247, 1622146752543427983

Offset: 0

Author

Paul Boddington, Nov 11 2003

Keywords

• easy
• nonn

Comments

The generating function for the corresponding sequence for the m-regular tree is 2*(m-1)/(m-2+m*sqrt(1-4*(m-1)*x)). When m=2 this reduces to the usual generating function for the central binomial coefficients.

Hankel transform is A133460. - Philippe Deléham, Dec 01 2007

Examples

			a(2) = 15 because there are 3*3=9 walks whose second step is to return to the starting vertex and 3*2=6 walks whose second step is to move away from the starting vertex.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200
• Libor Caha and Daniel Nagaj, The pair-flip model: a very entangled translationally invariant spin chain, arXiv:1805.07168 [quant-ph], 2018.
• Pakawut Jiradilok and Supanat Kamtue, Transportation Distance between Probability Measures on the Infinite Regular Tree, arXiv:2107.09876 [math.CO], 2021.
• Ed Pegg Jr., K-Cayley Trees

Crossrefs

Column k=3 of A183135.

Programs

Maple

A000602 := x -> 2^x*binomial(2*x, x)-9^x+1/3*2^x*binomial(2*x, x) * hypergeom([1, 2*x+1], [x+1], 2/3); # Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007

Mathematica

Table[2^n*Binomial[2*n,n]-3^(n-1)*Sum[(2/3)^k*Binomial[n+k,n],{k,0,n-1}],{n,0,20}] (* or *)
CoefficientList[Series[4/(1+3*Sqrt[1-8*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

PARI

my(x='x+O('x^30)); Vec(4/(1+3*sqrt(1-8*x))) \\ Joerg Arndt, May 10 2013

Formula

G.f.: 4/(1+3*sqrt(1-8*x)).

a(n) = 2^n * binomial(2*n,n) - 3^(n-1) * Sum_{j=0..n-1} (2/3)^j*binomial(n+j,n). - Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007

a(n) = Sum_{k=0..n} A039599(n,k)*2^(n-k). - Philippe Deléham, Aug 25 2007

From Paul Barry, Sep 04 2009: (Start)

G.f.: 1/(1-3x/(1-2x/(1-2x/(1-2x/(1-2x/(1-... (continued fraction);

G.f.: (1-2*x*c(x))/(1-3*x-2*x*c(x)), where c(x) is the g.f. of A000108. (End)

a(n) = A126087(2n). - Philippe Deléham, Nov 02 2011

D-finite with recurrence n*a(n) + (12-17*n)*a(n-1) + 36*(2n-3)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011

a(n) ~ 6*8^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012

From Karol A. Penson, Sep 06 2014: (Start)

a(n) is the (2*n)-th moment of a positive function W(x) = (3/Pi)*sqrt(8-x^2)/(9-x^2), on the segment x = (0,2*sqrt(2)): a(n) = Integral_{x=0..2*sqrt(2)} x^(2*n)*W(x) dx;

a(n) is the special value of hypergeometric function 2F1, in Maple notation: a(n)=2*8^n*GAMMA(n+1/2)*hypergeom([1,n+1/2],[n+2],8/9)/(3*sqrt(Pi)*(n+1)!). (End)

a(n) = A151374(n)*hypergeom([1,n+1/2],[n+2],8/9)*(2/3). - Peter Luschny, Sep 06 2014