The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085810 Number of three-choice paths along a corridor of height 5, starting from the lower side. 16
1, 2, 5, 13, 35, 96, 266, 741, 2070, 5791, 16213, 45409, 127206, 356384, 998509, 2797678, 7838801, 21963661, 61540563, 172432468, 483144522, 1353740121, 3793094450, 10628012915, 29779028189, 83438979561, 233790820762, 655067316176, 1835457822857, 5142838522138, 14409913303805 (list; graph; refs; listen; history; text; internal format)



A three-choice path is a path whose steps lie in the set {(1,1), (1,0), (1,-1)}.

Narrower corridors produce A000012, A000079, A000129, A001519, A057960. An infinitely wide corridor would produce A005773.

Diagonal sums of A114164. - Paul Barry, Nov 15 2005

C(n):= a(n)*(-1)^n appears in the following formula for the nonpositive powers of rho*sigma, where rho:=2*cos(Pi/7) and sigma:=sin(3*Pi/7)/sin(Pi/7) = rho^2-1 are the ratios of the smaller and larger diagonal length to the side length in a regular 7-gon (heptagon). See the Steinbach reference where the basis  <1,rho,sigma> is used in an extension of the rational field. (rho*sigma)^(-n) = C(n) + B(n)*rho + A(n)*sigma,n>=0, with B(n)= A181880(n-2)*(-1)^n, and A(n)= A116423(n+1)*(-1)^(n+1). For the nonnegative powers see A120757(n), |A122600(n-1)| and A181879(n), respectively. See also a comment under A052547.

a(n) is also the number of bi-wall directed polygons with n cells. (The definition of bi-wall directed polygons is given in the article on A122737.)


G. C. Greubel, Table of n, a(n) for n = 1..1000

S. Feretic, Generating functions for bi-wall directed polygons, in: Proc. of the Seventh Int. Conf. on Lattice Path Combinatorics and Applications (eds. S. Rinaldi and S. G. Mohanty), Siena, 2010, 147-151.

P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), p. 22-31 (formula 5).

Roman Witula, Damian Slota and Adam Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.

Index entries for linear recurrences with constant coefficients, signature (4,-3,-1).


a(n) = 4*a(n-1) - 3*a(n-2) - a(n-3).

From Paul Barry, Nov 15 2005: (Start)

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

a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-k} C(n-k, j)*C(j+k, 2k));

a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-k} C(n-k, k+j)*C(k, k-j)*2^(n-2k-j));

a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-2*k} C(n-j, n-2*k-j)*C(k, j)(-1)^j*2^(n-2*k-j)). (End)

a(n-1) = -B(n;-1) = (1/7)*((c(4)-c(1))*(1-c(1))^n + (c(1)-c(2))*(1-c(2))^n + (c(2)-c(4))*(1-c(4))^n), where a(-1):=0, c(j):=2*cos(2*Pi*j/7). Moreover, B(n;d), n in N, d in C, denotes the respective quasi-Fibonacci number defined in comments to A121449 or in Witula-Slota-Warzynski's paper (see also A077998, A006054, A052975, A094789, A121442). - Roman Witula, Aug 09 2012


LinearRecurrence[{4, -3, -1}, {1, 2, 5}, 50] (* Roman Witula, Aug 09 2012 *)

CoefficientList[Series[(1 - 2 x)/(1 - 4 x + 3 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)


(MAGMA) I:=[1, 2, 5]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)-Self(n-3): n in [1..35]]; // Vincenzo Librandi, Sep 18 2015

(PARI) x='x+O('x^30); Vec((1-2*x)/(1-4*x+3*x^2+x^3)) \\ G. C. Greubel, Apr 19 2018


Cf. A000012, A000079, A000129, A001519, A057960, A005773.

Sequence in context: A007075 A000107 A063028 * A235611 A005773 A307789

Adjacent sequences:  A085807 A085808 A085809 * A085811 A085812 A085813




Philippe Deléham, Jul 25 2003


Svjetlan Feretic made the following changes:

1) corrected and clarified the short description of the sequence,

2) changed offset to 1,

3) added two comments (to define a three-choice path and to say what a(n) also is),

4) added a link.

Explanation for 1): The paths under consideration "live" in a corridor like 0<=y<=5. Thus, the ordinate of a vertex of a path can take six values (0,1,2,3,4,5), but the height of the corridor is five.

Explanation for 2): a(1)=1 is the number of paths with zero steps, a(2)=2 is the number of paths with one step, a(3)=5 is the number of paths with two steps, ...



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 July 14 00:36 EDT 2020. Contains 335716 sequences. (Running on oeis4.)