|
%I #84 Dec 19 2022 17:29:07
%S 1,1,2,3,6,10,20,35,69,124,241,440,846,1560,2977,5525,10490,19551,
%T 36994,69142,130532,244419,460737,863788,1626629,3052100,5743674,
%U 10782928,20283121,38092457,71632290,134560491,252989326,475313762
%N Number of paths along a corridor width 8, starting from one side.
%C Counts all paths of length n starting at initial node on the path graph P_8. - _Paul Barry_, May 11 2004
%C 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
%C 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
%C a(n) is the 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
%C Range of row n of the circular Pascal array of order 9. - _Shaun V. Ault_, Jun 05 2014
%C 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
%H Harvey P. Dale, <a href="/A061551/b061551.txt">Table of n, a(n) for n = 0..1000</a>
%H Shaun V. Ault and Charles Kicey, <a href="http://dx.doi.org/10.1016/j.disc.2014.05.020">Counting paths in corridors using circular Pascal arrays</a>, Discrete Mathematics (2014).
%H Shaun V. Ault and Charles Kicey, <a href="http://arxiv.org/abs/1407.2197">Counting paths in corridors using circular Pascal arrays</a>, arXiv:1407.2197 [math.CO], (8-July-2014)
%H Johann Cigler, <a href="http://arxiv.org/abs/1501.04750">Some remarks and conjectures related to lattice paths in strips along the x-axis</a>, arXiv:1501.04750 [math.CO], 2015-2016.
%H Johann Cigler, <a href="https://arxiv.org/abs/2212.02118">Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials</a>, arXiv:2212.02118 [math.NT], 2022.
%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson</a>, arXiv:2006.06516 [math.CO], 2020.
%H L. E. Jeffery, <a href="/wiki/User:L._Edson_Jeffery/Unit-Primitive_Matrices">Unit-primitive matrices</a>
%H Marc A. A. Van Leeuwen, <a href="http://arxiv.org/abs/1010.4847">Some simple bijections involving lattice walks and ballot sequences</a>, arXiv:1010.4847 [math.CO], (23-October-2010)
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-2,-1).
%F 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.
%F From _Emeric Deutsch_, Aug 14 2006: (Start)
%F G.f.: (1-2*x^2)/((1-x)*(1-3*x^2-x^3)).
%F a(n) = 7*a(n-2) - 15*a(n-4) + 10*a(n-6) - a(n-8). (End)
%F a(2*n) = A094854(n) and a(2*n+1) = A094855(n). - _Johannes W. Meijer_, May 29 2010
%F 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
%F a(n) = A187498(3*n + 2). - _L. Edson Jeffery_, Mar 18 2011
%F a(n) = A205573(3,n). - _L. Edson Jeffery_, Feb 06 2012
%F G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x / (1 - x / (1 + x))))))). - _Michael Somos_, Feb 08 2015
%F 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
%e 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 + ....
%p 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
%p 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
%p X := j -> (-1)^(j/9) - (-1)^(1-j/9):
%p a := k -> add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7])/9:
%p seq(simplify(a(n)), n=0..30); # _Peter Luschny_, Sep 17 2020
%t LinearRecurrence[{1,3,-2,-1},{1,1,2,3},40] (* _Harvey P. Dale_, Dec 19 2011 *)
%t 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}]]
%t Table[a[n,8],{n,0,40}]//Round (* _Herbert Kociemba_, Sep 17 2020 *)
%Y Narrower corridors effectively produce A000007, A000012, A016116, A000045, A038754, A028495, A030436, A061551, A178381, A336675, A336678.
%Y An infinitely wide corridor (i.e., just one wall) would produce A001405.
%Y 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.
%Y a(n) = A094718(8, n).
%Y Cf. A030436 and A178381.
%K nonn,easy
%O 0,3
%A _Henry Bottomley_, May 16 2001
|
