

A061551


Number of paths along a corridor width 8, starting from one side.


13



1, 1, 2, 3, 6, 10, 20, 35, 69, 124, 241, 440, 846, 1560, 2977, 5525, 10490, 19551, 36994, 69142, 130532, 244419, 460737, 863788, 1626629, 3052100, 5743674, 10782928, 20283121, 38092457, 71632290, 134560491, 252989326, 475313762
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Counts all paths of length n starting at initial node on the path graph P_8.  Paul Barry, May 11 2004
The a(n) represent the number of possible chess games, ignoring the fiftymove and the triple repetition rules, after n moves by White in the following position: White Ka1, pawns a2, b6, d2, d6 and g2; Black Ka8, Bc8, pawns a3, b7, d3, d7 and g3.  Johannes W. Meijer, May 29 2010
Define the 4 X 4 tridiagonal unitprimitive matrix (see [Jeffery]) M = A_{9,1} = [0,1,0,0; 1,0,1,0; 0,1,0,1; 0,0,1,1]; then a(n)=[M^n]_(4,4).  L. Edson Jeffery, Mar 18 2011
a(n) is the length of nth word derived by certain iterated substitutions on four letters {1,2,3,4} as follows. Define the substitution rules 1 > {2}, 2 > {1,3}, 3 > {2,4}, 4 > {3,4}, in which "," denotes concatenation, so 1 > 2, 2 > 13, 3 > 24, 4 > 34. Let w(k) be the kth word formed by applying the substitution rules to each letter (digit) in word w(k1), k>0, putting w(0) = 1. Then, for n=0,1,..., {w(n)} = {1, 2, 13, 224, 131334, 2242242434, 13133413133413342434, ...} in which {length(w(n)} = {1,1,2,3,6,10,...} = A061551. The maps 1 > 2, etc., are given by the above matrix A_{9,1} by taking i > {j : [A_{9,1}]_(i,j) <> 0}, i, j in {1,2,3,4}. Moreover, the entry in row 1 and column j of [A_{9,1}]^n gives the relative frequency of the letter j in the nth word w(n). Finally, the sum of the firstrow entries of [A_{9,1}]^n again gives a(n), so obviously a(n) = sum of relative frequencies of each j in word w(n).  L. Edson Jeffery, Feb 06 2012
Range of row n of the circular Pascal array of order 9.  Shaun V. Ault, Jun 05 2014
In general, a(n,m) = (2^n/(m+1))*Sum_{r=1..m} (1(1)^r)*cos(Pi*r/(m+1))^n*(1+cos(Pi*r/(m+1))) gives the number of paths of length n starting at the initial node on the path graph P_m. Here we have m=8.  Herbert Kociemba, Sep 17 2020


LINKS



FORMULA

a(n) = sum(b(n,i)) where b(n,0) = b(n,9) = 0, b(0,1)=1, b(0, n)=0 if n!=1 and b(n,i) = b(n1,i) + b(n+1,i) if 0 < n < 9.
G.f.: (12*x^2)/((1x)*(13*x^2x^3)).
a(n) = 7*a(n2)  15*a(n4) + 10*a(n6)  a(n8). (End)
a(n) = a(n1) + 3*a(n2)  2*a(n3)  a(n4), for n > 3, with {a(k)}={1,1,2,3}, k=0,1,2,3.  L. Edson Jeffery, Mar 18 2011
G.f.: 1 / (1  x / (1  x / (1 + x / (1 + x / (1  x / (1  x / (1 + x))))))).  Michael Somos, Feb 08 2015
a(n) = 2^n/9*Sum_{r=1..8} (1(1)^r)cos(Pi*r/9)^n*(1+cos(Pi*r/9)).  Herbert Kociemba, Sep 17 2020


EXAMPLE

G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 35*x^7 + 69*x^8 + ....


MAPLE

a[0]:=1: a[1]:=1: a[2]:=2: a[3]:=3: a[4]:=6: a[5]:=10: a[6]:=20: a[7]:=35: for n from 8 to 33 do a[n]:=7*a[n2]15*a[n4]+10*a[n6]a[n8] od: seq(a[n], n=0..33); # Emeric Deutsch, Aug 14 2006
with(GraphTheory): P:=8: G:=PathGraph(P): A:= AdjacencyMatrix(G): nmax:=33; for n from 0 to nmax do B(n):=A^n; a(n):=add(B(n)[1, k], k=1..P); od: seq(a(n), n=0..nmax); # Johannes W. Meijer, May 29 2010
X := j > (1)^(j/9)  (1)^(1j/9):
a := k > add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7])/9:


MATHEMATICA

LinearRecurrence[{1, 3, 2, 1}, {1, 1, 2, 3}, 40] (* Harvey P. Dale, Dec 19 2011 *)
a[n_, m_]:=2^(n+1)/(m+1) Module[{x=(Pi r)/(m+1)}, Sum[Cos[x]^n (1+Cos[x]), {r, 1, m, 2}]]


CROSSREFS

Narrower corridors effectively produce A000007, A000012, A016116, A000045, A038754, A028495, A030436, A061551, A178381, A336675, A336678.
An infinitely wide corridor (i.e., just one wall) would produce A001405.
Equivalently, the above mentioned corridor numbers are exactly the ranges of the circular Pascal array of order d = 2, 3, 4, 5, 6, 7, 8, respectively, and this is true for any natural number d greater than or equal to 2.


KEYWORD

nonn,easy


AUTHOR



STATUS

approved



