login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061551 Number of paths along a corridor width 8, starting from one side. 10
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 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. - Johannes W. Meijer, May 29 2010

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

Range of row n of the circular Pascal array of order 9. - Shaun V. Ault, Jun 05 2014

LINKS

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics (2014).

Shaun V. Ault, Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], (8-July-2014)

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.

L. E. Jeffery, Unit-primitive matrices

Marc A. A. Van Leeuwen, Some simple bijections involving lattice walks and ballot sequences, arXiv:1010.4847 [math.CO], (23-October-2010)

Index entries for 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.

From Emeric Deutsch, Aug 14 2006: (Start)

G.f.: (1-2*x^2)/((1-x)*(1-3*x^2-x^3)).

a(n) = 7*a(n-2) - 15*a(n-4) + 10*a(n-6) - a(n-8). (End)

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, Mar 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

G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x / (1 - x / (1 + x))))))). - Michael Somos, Feb 08 2015

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[n-2]-15*a[n-4]+10*a[n-6]-a[n-8] 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

MATHEMATICA

LinearRecurrence[{1, 3, -2, -1}, {1, 1, 2, 3}, 40] (* 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.

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.

a(n) = A094718(8, n).

Cf. A030436 and A178381.

Sequence in context: A030227 A180272 A319436 * A026034 A178381 A037031

Adjacent sequences:  A061548 A061549 A061550 * A061552 A061553 A061554

KEYWORD

nonn,easy

AUTHOR

Henry Bottomley, May 16 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 11:25 EST 2019. Contains 320372 sequences. (Running on oeis4.)