cp's OEIS Frontend

A085363 a(0)=1, for n>0: a(n) = 4*9^(n-1) - (1/2)*Sum_{i=1..n-1} a(i)*a(n-i).

%I A085363 #79 Aug 22 2025 11:02:06
%S A085363 1,4,28,212,1676,13604,112380,940020,7936620,67494980,577309148,
%T A085363 4961187092,42801458764,370478720356,3215827927228,27982214082612,
%U A085363 244004165618220,2131710838837380,18654504783815580,163488269572628820
%N A085363 a(0)=1, for n>0: a(n) = 4*9^(n-1) - (1/2)*Sum_{i=1..n-1} a(i)*a(n-i).
%C A085363 Apparently, the number of 2-D directed walks of semilength n starting at (0,0) and ending on the X-axis using steps NE, SE, NW and SW avoiding adjacent NW/SE and adjacent NE/SW. - _David Scambler_, Jun 20 2013
%C A085363 Form an array with m(0,n) = m(n,0) = 2^n; m(i,j) equals the sum of the terms to the left of m(i,j) and the sum of the terms above m(i,j), which is m(i,j) = Sum_{k-0..j-1} m(i,k) + Sum_{k=0..i-1} m(k,j).  m(n,n) = a(n). - _J. M. Bergot_, Jul 10 2013
%C A085363 From _G. C. Greubel_, May 22 2020: (Start)
%C A085363 This sequence is part of a class of sequences, for m >= 0, with the properties:
%C A085363 a(n) = 2*m*(4*m+1)^(n-1) - (1/2)*Sum_{k=1..n-1} a(k)*a(n-k).
%C A085363 a(n) = Sum_{k=0..n} m^k * binomial(n-1, n-k) * binomial(2*k, k).
%C A085363 a(n) = (2*m) * Hypergeometric2F1(-n+1, 3/2; 2; -4*m), for n > 0.
%C A085363 n*a(n) = 2*((2*m+1)*n - (m+1))*a(n-1) - (4*m+1)*(n-2)*a(n-2).
%C A085363 (4*m + 1)^n = Sum_{k=0..n} Sum_{j=0..k} a(j)*a(k-j).
%C A085363 G.f.: sqrt( (1 - t)/(1 - (4*m+1)*t) ).
%C A085363 This sequence is the case of m=2. (End)
%C A085363 The number of elements in the free group on two generators of length 2n that are zero exponent sum. - _Tey Berendschot_, Aug 09 2021
%H A085363 Vincenzo Librandi, <a href="/A085363/b085363.txt">Table of n, a(n) for n = 0..200</a>
%H A085363 Kees A.S. Immink and Kui Cai, <a href="https://doi.org/10.1109/ACCESS.2020.2980036">Properties and constructions of constrained codes for DNA-based data storage</a>, IEEE Access, vol. 8, no. 1, pp. 49523-49531, 2020, page 49529.
%H A085363 John Machacek, <a href="https://arxiv.org/abs/2105.02417">Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats</a>, preprint arXiv:2105.02417 [math.CO], 2021.
%F A085363 G.f.: sqrt((1-x)/(1-9*x)).
%F A085363 Sum_{i=0..n} Sum_{j=0..i} a(j)*a(i-j) = 9^n.
%F A085363 From _Vladeta Jovovic_, Oct 10 2003: (Start)
%F A085363 First differences of A084771.
%F A085363 a(n) = Sum_{k=1..n} 2^k * binomial(n-1, k-1) * binomial(2*k, k). (End)
%F A085363 D-finite with recurrence n*a(n) = (10*n-6)*a(n-1) - (9*n-18)*a(n-2). - _Vladeta Jovovic_, Jul 16 2004
%F A085363 a(n) ~ 2*sqrt(2)*3^(2*n-1)/sqrt(Pi*n). - _Vaclav Kotesovec_, Oct 14 2012
%F A085363 a(0) = 1; a(n) = (4/n) * Sum_{k=0..n-1} (n+k) * a(k). - _Seiichi Manyama_, Mar 28 2023
%F A085363 From _Seiichi Manyama_, Aug 22 2025: (Start)
%F A085363 a(n) = (1/4)^n * Sum_{k=0..n} 9^k * binomial(2*k,k) * binomial(2*(n-k),n-k)/(1-2*(n-k)).
%F A085363 a(n) = Sum_{k=0..n} (-2)^k * 9^(n-k) * binomial(2*k,k)/(1-2*k) * binomial(n-1,n-k). (End)
%p A085363 seq(coeff(series(sqrt((1-x)/(1-9*x)), x, n+1), x, n), n = 0..30); # _G. C. Greubel_, May 23 2020
%t A085363 CoefficientList[Series[Sqrt[(1-x)/(1-9x)], {x, 0, 25}], x]
%o A085363 (PARI) my(x='x+O('x^66)); Vec(sqrt((1-x)/(1-9*x)) ) \\ _Joerg Arndt_, May 10 2013
%o A085363 (Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( Sqrt((1-x)/(1-9*x)) )); // _G. C. Greubel_, May 23 2020
%o A085363 (Sage)
%o A085363 def A085363_list(prec):
%o A085363     P.<x> = PowerSeriesRing(ZZ, prec)
%o A085363     return P( sqrt((1-x)/(1-9*x)) ).list()
%o A085363 A085363_list(30) # _G. C. Greubel_, May 23 2020
%Y A085363 Cf. A001019 (9^n), A084771, A085362, A085364, diagonal of A348595.
%K A085363 easy,nonn,changed
%O A085363 0,2
%A A085363 Mario Catalani (mario.catalani(AT)unito.it), Jun 25 2003