cp's OEIS Frontend

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

%I A089022 #68 May 02 2025 05:16:36
%S A089022 1,3,15,87,543,3543,23823,163719,1143999,8099511,57959535,418441191,
%T A089022 3043608351,22280372247,164008329423,1213166815047,9012417249663,
%U A089022 67208553680247,502920171632943,3775020828459687,28415858155984863,214444848602732247,1622146752543427983
%N A089022 Number of walks of length 2n on the 3-regular tree beginning and ending at some fixed vertex.
%C A089022 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.
%C A089022 Hankel transform is A133460. - _Philippe Deléham_, Dec 01 2007
%H A089022 Vincenzo Librandi, <a href="/A089022/b089022.txt">Table of n, a(n) for n = 0..200</a>
%H A089022 Libor Caha and Daniel Nagaj, <a href="https://arxiv.org/abs/1805.07168">The pair-flip model: a very entangled translationally invariant spin chain</a>, arXiv:1805.07168 [quant-ph], 2018.
%H A089022 Pakawut Jiradilok and Supanat Kamtue, <a href="https://arxiv.org/abs/2107.09876">Transportation Distance between Probability Measures on the Infinite Regular Tree</a>, arXiv:2107.09876 [math.CO], 2021.
%H A089022 Ed Pegg Jr., <a href="http://demonstrations.wolfram.com/KCayleyTrees/">K-Cayley Trees</a>
%F A089022 G.f.: 4/(1+3*sqrt(1-8*x)).
%F A089022 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
%F A089022 a(n) = Sum_{k=0..n} A039599(n,k)*2^(n-k). - _Philippe Deléham_, Aug 25 2007
%F A089022 From _Paul Barry_, Sep 04 2009: (Start)
%F A089022 G.f.: 1/(1-3x/(1-2x/(1-2x/(1-2x/(1-2x/(1-... (continued fraction);
%F A089022 G.f.: (1-2*x*c(x))/(1-3*x-2*x*c(x)), where c(x) is the g.f. of A000108. (End)
%F A089022 a(n) = A126087(2n). - _Philippe Deléham_, Nov 02 2011
%F A089022 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
%F A089022 a(n) ~ 6*8^n/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 17 2012
%F A089022 From _Karol A. Penson_, Sep 06 2014: (Start)
%F A089022 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;
%F A089022 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)
%F A089022 a(n) = A151374(n)*hypergeom([1,n+1/2],[n+2],8/9)*(2/3). - _Peter Luschny_, Sep 06 2014
%e A089022 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.
%p A089022 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
%t A089022 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 *)
%t A089022 CoefficientList[Series[4/(1+3*Sqrt[1-8*x]), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Oct 17 2012 *)
%o A089022 (PARI) my(x='x+O('x^30)); Vec(4/(1+3*sqrt(1-8*x))) \\ _Joerg Arndt_, May 10 2013
%Y A089022 Column k=3 of A183135.
%K A089022 easy,nonn
%O A089022 0,2
%A A089022 _Paul Boddington_, Nov 11 2003