OFFSET

1,2

COMMENTS

From Svjetlan Feretic, Jun 01 2013: (Start)

A three-choice path is a path whose steps lie in the set {(1,1), (1,0), (1,-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.

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

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

(End)

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

LINKS

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

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

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

FORMULA

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

MATHEMATICA

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

PROG

(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

CROSSREFS

KEYWORD

easy,nonn

AUTHOR

Philippe Deléham, Jul 25 2003

EXTENSIONS

Name corrected and clarified, and offset 1 from Svjetlan Feretic, Jun 01 2013

STATUS

approved