A085810 - OEIS

%I #59 Sep 08 2022 08:45:11

%S 1,2,5,13,35,96,266,741,2070,5791,16213,45409,127206,356384,998509,

%T 2797678,7838801,21963661,61540563,172432468,483144522,1353740121,

%U 3793094450,10628012915,29779028189,83438979561,233790820762,655067316176,1835457822857,5142838522138,14409913303805

%N Number of three-choice paths along a corridor of height 5, starting from the lower side.

%C From _Svjetlan Feretic_, Jun 01 2013: (Start)

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

%C 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.

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

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

%C (End)

%C Diagonal sums of A114164. - _Paul Barry_, Nov 15 2005

%C 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.

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

%H G. C. Greubel, <a href="/A085810/b085810.txt">Table of n, a(n) for n = 1..1000</a>

%H Svjetlan Feretic, <a href="http://www.gradri.uniri.hr/adminmax/files/staff/bi_wall_5.pdf"> Generating functions for bi-wall directed polygons</a>, in: Proc. of the Seventh Int. Conf. on Lattice Path Combinatorics and Applications (eds. S. Rinaldi and S. G. Mohanty), Siena, 2010, 147-151.

%H Peter Steinbach, <a href="http://www.jstor.org/stable/2691048">Golden fields: a case for the heptagon</a>, Math. Mag. 70 (1997), p. 22-31 (formula 5).

%H Roman Witula, Damian Slota and Adam Warzynski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Slota/slota57.html">Quasi-Fibonacci Numbers of the Seventh Order</a>, J. Integer Seq., 9 (2006), Article 06.4.3.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-3,-1).

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

%F From _Paul Barry_, Nov 15 2005: (Start)

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

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

%F 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));

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

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

%t LinearRecurrence[{4,-3,-1}, {1,2,5}, 50] (* _Roman Witula_, Aug 09 2012 *)

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

%o (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

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

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

%K easy,nonn

%O 1,2

%A _Philippe Deléham_, Jul 25 2003

%E Name corrected and clarified, and offset 1 from _Svjetlan Feretic_, Jun 01 2013