A035610 - OEIS

%I #88 Aug 06 2024 22:48:40

%S 1,4,28,232,2092,19864,195352,1970896,20275660,211823800,2240795848,

%T 23951289520,258255469816,2805534253552,30675477376432,

%U 337306474674592,3727578443380492,41376874025687032,461121792658583272,5157384457905440752,57869888433073055272,651266142688270063312,7349148747954997832272

%N G.f.: 3/(1 + 2*sqrt(1-12*x)).

%C Number of walks of length 2n on the 4-regular tree beginning and ending at some fixed vertex. 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. - _Paul Boddington_, Nov 11 2003

%C Main diagonal of the array A(0,j)=A(i,0)=1 for i,j>=0 and for i,j>=1 A(i,j)=min{A(i,j-1)+3*A(i-1,j); 3*A(i,j-1)+A(i-1,j)}. - _Benoit Cloitre_, Aug 05 2004

%C Hankel transform is A133461. - _Philippe Deléham_, Dec 01 2007

%C Also the number of length 2n words over an alphabet of size 4 that can be built by repeatedly inserting doublets into the initially empty word.

%C The sequence {b(n)}, where b(2n)=a(n), b(2n+1)=0, is the cogrowth function of the free group of rank 2. - _Murray Elder_, Jun 28 2016

%H Robert Israel, <a href="/A035610/b035610.txt">Table of n, a(n) for n = 0..837</a>

%H Murray Elder, <a href="/A035610/a035610.txt">Table of n, b(n) for n = 0..200</a>, where b(n) is mentioned in a comment above.

%H 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 M. Elder and A. Rechnitzer, T. Wong, <a href="http://arxiv.org/abs/1108.1596">On the cogrowth of Thompson's group F</a>, Groups, Complexity, Cryptology 4(2) (2012), 301-320.

%H 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 J. Novak, <a href="http://arxiv.org/abs/1205.2097">Three lectures on free probability</a>, arXiv preprint arXiv:1205.2097, 2012. - _N. J. A. Sloane_, Oct 15 2012

%H Gregory Quenell, <a href="http://student.plattsburgh.edu/quenelgt/pubpdf/freeprod.pdf">Combinatorics of free product graphs</a>, Contemp. Math (1994) 257-281 (Eq. 19).

%H Ian M. Wanless, <a href="https://doi.org/10.1017/S0963548309990678">Counting Matchings and Tree-Like Walks in Regular Graphs</a>, Combinatorics, Probability and Computing (2010) 19, 463-480 (Lemma 3.1).

%F a(n) = Sum_{k=0..n} A039599(n,k)*3^(n-k). - _Philippe Deléham_, Aug 25 2007

%F From _Paul Barry_, Sep 15 2009: (Start)

%F G.f.: 1/(1-4x*c(3x)), c(x) the g.f. of A000108;

%F G.f.: 1/(1-4x/(1-3x/(1-3x/(1-3x/(1-3x/(1-.... (continued fraction);

%F G.f.: 1/(1-4x-12x^2/(1-6x-9x^2/(1-6x-9x^2/(1-6x-9x^2/(1-... (continued fraction).

%F Integral representation: a(n) = (2/Pi)*Integral_{x=0..12} x^n*sqrt(x*(12-x))/(16-x). (End)

%F a(0) = 1; a(n) = (4/n) * Sum_{j=0..n-1} C(2*n,j) * (n-j) * 3^j for n > 0.

%F a(n) = upper left term in M^n, M = an infinite square production matrix as follows:

%F   4, 4, 0, 0, 0, 0, ...

%F   3, 3, 3, 0, 0, 0, ...

%F   3, 3, 3, 3, 0, 0, ...

%F   3, 3, 3, 3, 3, 0, ...

%F   3, 3, 3, 3, 3, 3, ...

%F   ...

%F - _Gary W. Adamson_, Jul 15 2011

%F D-finite with recurrence: n*a(n) + 2*(9-14*n)*a(n-1) + 96*(2*n-3)*a(n-2) = 0. - _R. J. Mathar_, Nov 14 2011

%F P-recurrence confirmed using differential equation (-96*x+10)*g(x) + (-192*x^2+28*x-1)*g'(x) - 6 = 0 satisfied by the generating function. - _Robert Israel_, Jul 06 2015

%F a(n) ~ 3*12^n/(sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Jun 29 2013

%F a(n) are special values of the hypergeometric function 2F1, in Maple notation: a(n) = 3*12^n*GAMMA(n+1/2)*hypergeom([1,n+1/2],[n+2],3/4)/(4*sqrt(Pi)*(n+1)!), n=0,1,... . - _Karol A. Penson_, Jul 06 2015

%e a(2)=28 because there are 4*4=16 walks whose second step is to return to the starting vertex and 4*3=12 walks whose second step is to move away from the starting vertex.

%p a:= n-> `if`(n=0, 1, 4/n*add(binomial(2*n, j) *(n-j)*3^j, j=0..n-1)):

%p seq(a(n), n=0..20);

%p # Alternative:

%p f:= gfun:-rectoproc({(-192*n-288)*a(n+1)+(28*n+66)*a(n+2)+(-n-3)*a(n+3)=0,a(0)=1,a(1)=4,a(2)=28},a(n),remember):

%p map(f, [$0..50]); # _Robert Israel_, Jul 06 2015

%t CoefficientList[ Series[3/(1 + 2Sqrt[1 - 12x]), {x, 0, 19}], x] (* _Robert G. Wilson v_, Nov 12 2003 *)

%o (PARI) x='x+O('x^66); Vec(3/(1+2*sqrt(1-12*x))) \\ _Joerg Arndt_, Sep 06 2014

%Y Cf. A089022.

%Y 4th column of A183135.

%K nonn

%O 0,2

%A _N. J. A. Sloane_

%E Edited by _Alois P. Heinz_, Jan 20 2011