|
| |
|
|
A061551
|
|
Number of paths along a corridor width 8, starting from one side.
|
|
9
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Counts all paths of length n starting at initial node on the path graph P_8. - Paul Barry (pbarry(AT)wit.ie), May 11 2004
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), May 29 2010: (Start)
The a(n) represent the number of possible chess games, ignoring the fifty-move 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.
(End)
Define the 4 X 4 tridiagonal unit-primitive 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) = length of n-th 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 k-th word formed by applying the substitution rules to each letter (digit) in word w(k-1), 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 n-th word w(n). Finally, the sum of the first-row 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
|
|
|
LINKS
| L. E. Jeffery, Unit-primitive matrices
Index to sequences with linear recurrences with constant coefficients, signature (1,3,-2,-1).
|
|
|
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(n-1, i)+b(n+1, i) if 0<n<9.
G.f.=(1-2x^2)/[(1-x)(1-3x^2-x^3)]. a(n)=7a(n-2)-15a(n-4)+10a(n-6)-a(n-8). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 14 2006
a(2*n) = A094854(n) and a(2*n+1) = A094855(n). [Johannes W. Meijer, May 29 2010]
a(n)=a(n-1)+3*a(n-2)-2*a(n-3)-a(n-4), for n>3, with {a(k)}={1,1,2,3}, k=0,1,2,3. - L. Edson Jeffery, March 18, 2011.
a(n)=A187498(3*n+2). - L. Edson Jeffery, Mar 18 2011
a(n)=A205573(3,n). - L. Edson Jeffery, Feb 06 2012
|
|
|
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[n-2]-15*a[n-4]+10*a[n-6]-a[n-8] od: seq(a[n], n=0..33); - Emeric Deutsch (deutsch(AT)duke.poly.edu), Aug 14 2006
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), May 29 2010: (Start)
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);
(End)
|
|
|
MATHEMATICA
| LinearRecurrence[{1, 3, -2, -1}, {1, 1, 2, 3}, 40] (* From Harvey P. Dale, Dec 19 2011 *)
|
|
|
CROSSREFS
| Narrower corridors effectively produce A000007, A000012, A016116, A000045, A038754, A028495, A030436. An infinitely wide corridor (i.e. just one wall) would produce A001405.
a(n) = A094718(8, n).
Cf. A030436 and A178381.
Sequence in context: A030436 A030227 A180272 * A026034 A178381 A037031
Adjacent sequences: A061548 A061549 A061550 * A061552 A061553 A061554
|
|
|
KEYWORD
| nonn,easy,changed
|
|
|
AUTHOR
| Henry Bottomley (se16(AT)btinternet.com), May 16 2001
|
| |
|
|
