login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A035610
G.f.: 3/(1 + 2*sqrt(1-12*x)).
7
1, 4, 28, 232, 2092, 19864, 195352, 1970896, 20275660, 211823800, 2240795848, 23951289520, 258255469816, 2805534253552, 30675477376432, 337306474674592, 3727578443380492, 41376874025687032, 461121792658583272, 5157384457905440752, 57869888433073055272, 651266142688270063312, 7349148747954997832272
OFFSET
0,2
COMMENTS
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
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
Hankel transform is A133461. - Philippe Deléham, Dec 01 2007
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.
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
LINKS
Murray Elder, Table of n, b(n) for n = 0..200, where b(n) is mentioned in a comment above.
Libor Caha and Daniel Nagaj, The pair-flip model: a very entangled translationally invariant spin chain, arXiv:1805.07168 [quant-ph], 2018.
M. Elder and A. Rechnitzer, T. Wong, On the cogrowth of Thompson's group F, Groups, Complexity, Cryptology 4(2) (2012), 301-320.
Pakawut Jiradilok and Supanat Kamtue, Transportation Distance between Probability Measures on the Infinite Regular Tree, arXiv:2107.09876 [math.CO], 2021.
J. Novak, Three lectures on free probability, arXiv preprint arXiv:1205.2097, 2012. - N. J. A. Sloane, Oct 15 2012
Gregory Quenell, Combinatorics of free product graphs, Contemp. Math (1994) 257-281 (Eq. 19).
Ian M. Wanless, Counting Matchings and Tree-Like Walks in Regular Graphs, Combinatorics, Probability and Computing (2010) 19, 463-480 (Lemma 3.1).
FORMULA
a(n) = Sum_{k=0..n} A039599(n,k)*3^(n-k). - Philippe Deléham, Aug 25 2007
From Paul Barry, Sep 15 2009: (Start)
G.f.: 1/(1-4x*c(3x)), c(x) the g.f. of A000108;
G.f.: 1/(1-4x/(1-3x/(1-3x/(1-3x/(1-3x/(1-.... (continued fraction);
G.f.: 1/(1-4x-12x^2/(1-6x-9x^2/(1-6x-9x^2/(1-6x-9x^2/(1-... (continued fraction).
Integral representation: a(n) = (2/Pi)*Integral_{x=0..12} x^n*sqrt(x*(12-x))/(16-x). (End)
a(0) = 1; a(n) = (4/n) * Sum_{j=0..n-1} C(2*n,j) * (n-j) * 3^j for n > 0.
a(n) = upper left term in M^n, M = an infinite square production matrix as follows:
4, 4, 0, 0, 0, 0, ...
3, 3, 3, 0, 0, 0, ...
3, 3, 3, 3, 0, 0, ...
3, 3, 3, 3, 3, 0, ...
3, 3, 3, 3, 3, 3, ...
...
- Gary W. Adamson, Jul 15 2011
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
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
a(n) ~ 3*12^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 29 2013
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
EXAMPLE
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.
MAPLE
a:= n-> `if`(n=0, 1, 4/n*add(binomial(2*n, j) *(n-j)*3^j, j=0..n-1)):
seq(a(n), n=0..20);
# Alternative:
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):
map(f, [$0..50]); # Robert Israel, Jul 06 2015
MATHEMATICA
CoefficientList[ Series[3/(1 + 2Sqrt[1 - 12x]), {x, 0, 19}], x] (* Robert G. Wilson v, Nov 12 2003 *)
PROG
(PARI) x='x+O('x^66); Vec(3/(1+2*sqrt(1-12*x))) \\ Joerg Arndt, Sep 06 2014
CROSSREFS
Cf. A089022.
4th column of A183135.
Sequence in context: A152599 A199579 A089023 * A229652 A229651 A229650
KEYWORD
nonn
EXTENSIONS
Edited by Alois P. Heinz, Jan 20 2011
STATUS
approved