A348595 -id:A348595 - cp's OEIS frontend

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

1, 4, 28, 212, 1676, 13604, 112380, 940020, 7936620, 67494980, 577309148, 4961187092, 42801458764, 370478720356, 3215827927228, 27982214082612, 244004165618220, 2131710838837380, 18654504783815580, 163488269572628820

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Jun 25 2003

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
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
From G. C. Greubel, May 22 2020: (Start)
This sequence is part of a class of sequences, for m >= 0, with the properties:
a(n) = 2*m*(4*m+1)^(n-1) - (1/2)*Sum_{k=1..n-1} a(k)*a(n-k).
a(n) = Sum_{k=0..n} m^k * binomial(n-1, n-k) * binomial(2*k, k).
a(n) = (2*m) * Hypergeometric2F1(-n+1, 3/2; 2; -4*m), for n > 0.
n*a(n) = 2*((2*m+1)*n - (m+1))*a(n-1) - (4*m+1)*(n-2)*a(n-2).
(4*m + 1)^n = Sum_{k=0..n} Sum_{j=0..k} a(j)*a(k-j).
G.f.: sqrt( (1 - t)/(1 - (4*m+1)*t) ).
This sequence is the case of m=2. (End)
The number of elements in the free group on two generators of length 2n that are zero exponent sum. - Tey Berendschot, Aug 09 2021

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Kees A.S. Immink and Kui Cai, Properties and constructions of constrained codes for DNA-based data storage, IEEE Access, vol. 8, no. 1, pp. 49523-49531, 2020, page 49529.
John Machacek, Lattice walks ending on a coordinate hyperplane avoiding backtracking and repeats, preprint arXiv:2105.02417 [math.CO], 2021.

Cf. A001019 (9^n), A084771, A085362, A085364, diagonal of A348595.

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( Sqrt((1-x)/(1-9*x)) )); // G. C. Greubel, May 23 2020

seq(coeff(series(sqrt((1-x)/(1-9*x)), x, n+1), x, n), n = 0..30); # G. C. Greubel, May 23 2020

CoefficientList[Series[Sqrt[(1-x)/(1-9x)], {x, 0, 25}], x]

my(x='x+O('x^66)); Vec(sqrt((1-x)/(1-9*x)) ) \\ Joerg Arndt, May 10 2013

def A085363_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( sqrt((1-x)/(1-9*x)) ).list()
A085363_list(30) # G. C. Greubel, May 23 2020

G.f.: sqrt((1-x)/(1-9*x)).
Sum_{i=0..n} Sum_{j=0..i} a(j)*a(i-j) = 9^n.
From Vladeta Jovovic, Oct 10 2003: (Start)
First differences of A084771.
a(n) = Sum_{k=1..n} 2^k * binomial(n-1, k-1) * binomial(2*k, k). (End)
D-finite with recurrence n*a(n) = (10*n-6)*a(n-1) - (9*n-18)*a(n-2). - Vladeta Jovovic, Jul 16 2004
a(n) ~ 2*sqrt(2)*3^(2*n-1)/sqrt(Pi*n). - Vaclav Kotesovec, Oct 14 2012
a(0) = 1; a(n) = (4/n) * Sum_{k=0..n-1} (n+k) * a(k). - Seiichi Manyama, Mar 28 2023
From Seiichi Manyama, Aug 22 2025: (Start)
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)).
a(n) = Sum_{k=0..n} (-2)^k * 9^(n-k) * binomial(2*k,k)/(1-2*k) * binomial(n-1,n-k). (End)

A307584 Triangle read by rows: T(n,k) is the number of non-backtracking walks on Z^2 of length n that are active for k steps, where the walk is initially active and turns in the walk toggle the activity.

Original entry on oeis.org

1, 2, 1, 2, 6, 1, 2, 14, 10, 1, 2, 22, 42, 14, 1, 2, 30, 106, 86, 18, 1, 2, 38, 202, 318, 146, 22, 1, 2, 46, 330, 838, 722, 222, 26, 1, 2, 54, 490, 1774, 2514, 1382, 314, 30, 1, 2, 62, 682, 3254, 6802, 6062, 2362, 422, 34, 1, 2, 70, 906, 5406, 15378, 20406, 12570, 20406, 12570, 3726, 546, 38, 1

Offset: 1

Matthew Fahrbach, Apr 15 2019

			Triangle begins:
1;
2,  1;
2,  6,   1;
2, 14,  10,    1;
2, 22,  42,   14,     1;
2, 30, 106,   86,    18,     1;
2, 38, 202,  318,   146,    22,     1;
2, 46, 330,  838,   722,   222,    26,    1;
2, 54, 490, 1774,  2514,  1382,   314,   30,   1;
2, 62, 682, 3254,  6802,  6062,  2362,  422,  34,  1;
2, 70, 906, 5406, 15378, 20406, 12570, 3726, 546, 38, 1;
...

M. Fahrbach and D. Randall, Slow mixing of Glauber dynamics for the six-vertex model in the ferroelectric and antiferroelectric phases, arXiv:1904.01495 [cs.DS], 2019
R. J. Mathar, Walks of up and right steps in the square lattice with blocked squares (2022) Table 2.

Row sums give A000244. Cf. A051708 (subdiagonal T(2n,n)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A307584 Triangle read by rows: T(n,k) is the number of non-backtracking walks on Z^2 of length n that are active for k steps, where the walk is initially active and turns in the walk toggle the activity.

Views

Author

Keywords

Examples

Links

Crossrefs

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).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A307584 Triangle read by rows: T(n,k) is the number of non-backtracking walks on Z^2 of length n that are active for k steps, where the walk is initially active and turns in the walk toggle the activity.

Views

Author

Keywords

Examples

Links

Crossrefs

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