A205573 -id:A205573 - cp's OEIS frontend

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

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

Offset: 0

Henry Bottomley, May 16 2001

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

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

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 and 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.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Nachum Dershowitz, Between Broadway and the Hudson, arXiv:2006.06516 [math.CO], 2020.
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).

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.
a(n) = A094718(8, n).
Cf. A030436 and A178381.

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
X := j -> (-1)^(j/9) - (-1)^(1-j/9):
a := k -> add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7])/9:
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 17 2020

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}]]
Table[a[n,8],{n,0,40}]//Round (* Herbert Kociemba, Sep 17 2020 *)

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

A191314 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths (i.e., Motzkin paths with no (1,0) steps at positive heights) of length n and height k.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 7, 2, 1, 12, 6, 1, 1, 20, 12, 2, 1, 33, 27, 8, 1, 1, 54, 53, 16, 2, 1, 88, 108, 44, 10, 1, 1, 143, 208, 88, 20, 2, 1, 232, 405, 208, 65, 12, 1, 1, 376, 768, 415, 130, 24, 2, 1, 609, 1459, 908, 350, 90, 14, 1, 1, 986, 2734, 1804, 700, 180, 28, 2, 1, 1596, 5117, 3776, 1700, 544, 119, 16, 1

Offset: 0

Emeric Deutsch, May 31 2011

Row n has 1 + floor(n/2) entries.
Sum of entries in row n is binomial(n, floor(n/2)) = A001405(n).
T(n,1) = A000071(n+1) (Fibonacci numbers minus 1).
Sum_{k>=0} k * T(n,k) = A191315(n).
Extracting the even numbered rows, we obtain triangle A205946 with row sums A000984. The odd numbered rows yield triangle A205945 with row sums A001700. - Gary W. Adamson, Feb 01 2012

			T(5,2) = 2 because we have HUUDD and UUDDH, where U=(1,1), D=(1,-1), H=(1,0).
Triangle starts:
1;
1;
1,  1;
1,  2;
1,  4,  1;
1,  7,  2;
1, 12,  6, 1;
1, 20, 12, 2;
1, 33, 27, 8, 1;

Alois P. Heinz, Rows n = 0..200, flattened

Cf. A001405, A000071, A191315.

Cf. A205573, A205945, A001700, A205946, A000984.

F[0] := 1: F[1] := 1-z: for k from 2 to 12 do F[k] := sort(expand(F[k-1]-z^2*F[k-2])) end do: for k from 0 to 11 do h[k] := z^(2*k)/(F[k]*F[k+1]) end do: T := proc (n, k) options operator, arrow: coeff(series(h[k], z = 0, 20), z, n) end proc: for n from 0 to 16 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1,
      (p->add(coeff(p, z, i)*z^max(i, y), i=0..degree(p,z)))
      (b(x-1, y-1))+ b(x-1, y+1)+`if`(y=0, b(x-1, y), 0)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Mar 12 2014

b[x_, y_] := b[x, y] = If[y>x || y<0, 0, If[x==0, 1, Function [{p}, Sum[ Coefficient[p, z, i]*z^Max[i, y], {i, 0, Exponent[p, z]}]][b[x-1, y-1]] + b[x-1, y+1] + If[y==0, b[x-1, y], 0]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[n, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Mar 31 2015, after Alois P. Heinz *)

G.f.: The g.f. of column k is z^{2k}/(F[k]*F[k+1]), where F[k] are polynomials in z defined by F[0]=1, F[1]=1-z, F[k]=F[k-1]-z^2*F[k-2] for k>=2. The coefficients of these polynomials form the triangle A108299.

Rows may be obtained by taking finite differences of A205573 columns from the top -> down. - Gary W. Adamson, Feb 01 2012

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A191314 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths (i.e., Motzkin paths with no (1,0) steps at positive heights) of length n and height k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A205945 Triangle read by rows related to A001700.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A205946 Triangle read by rows related to A000984, central binomial coefficients.

Views

Author

Keywords

Examples

Crossrefs

Formula