A116423 -id:A116423 - cp's OEIS frontend

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

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

Offset: 1

Philippe Deléham, Jul 25 2003

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

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

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

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

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

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

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

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

A120757 Expansion of x^2(2+x)/(1-3x-4*x^2-x^3).

Original entry on oeis.org

0, 2, 7, 29, 117, 474, 1919, 7770, 31460, 127379, 515747, 2088217, 8455018, 34233669, 138609296, 561217582, 2272323599, 9200450421, 37251863241, 150829715006, 610697048403, 2472661868474, 10011603514040, 40536155064419

Offset: 1

Gary W. Adamson & Roger L. Bagula, Jul 01 2006

The (1,1)-entry of the matrix M^n, where M is the 3 X 3 matrix [0,1,1; 1,1,2; 1,2,2].
a(n)/a(n-1) tends to 4.0489173...an eigenvalue of M and a root to the characteristic polynomial x^3 - 3x^2 - 4x - 1.
C(n):=a(n), with a(0):=1 (hence the o.g.f. for C(n) is (1-3*x-2*x^2)/(1-3*x-4*x^2-x^3)), appears in the following formula for the nonnegative 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)= |A122600(n-1)|, B(0)=0, and A(n)= A181879(n). For the nonpositive powers see A085810(n)*(-1)^n, A181880(n-2)*(-1)^n and A116423(n+1)*(-1)^(n+1), respectively. See also a comment under A052547.
We have a(n)=cs(3n+1), where the sequence cs(n) and its two conjugate sequences as(n) and bs(n) are defined in the comments to the sequence A214683 (see also A215076, A215100, A006053). We call the sequence a(n) the Ramanujan-type sequence number 5 for the argument 2Pi/7. Since as(3n+1)=bs(3n+1)=0, we obtain the following relation: 49^(1/3)*a(n) = (c(1)/c(4))^(n + 1/3) + (c(4)/c(2))^(n + 1/3) + (c(2)/c(1))^(n + 1/3), where c(j) := Cos(2Pi/7) (for more details and proofs see Witula et al.'s papers). - Roman Witula, Aug 02 2012

			a(7)=1919 because M^7= [1919,3458,4312;3458,6231,7770;4312,7770,9689].

R. Witula, E. Hetmaniok and D. Slota, Sums of the powers of any order roots taken from the roots of a given polynomial, Proceedings of the Fifteenth International Conference on Fibonacci Numbers and Their Applications, Eger, Hungary, 2012.

G. C. Greubel, Table of n, a(n) for n = 1..1000
P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31, MR 1439165
Roman Witula, Ramanujan Type Trigonometric Formulas: The General Form for the Argument 2*Pi/7, Journal of Integer Sequences, Vol. 12 (2009), Article 09.8.5.
Roman Witula, Full Description of Ramanujan Cubic Polynomials, Journal of Integer Sequences, Vol. 13 (2010), Article 10.5.7.
Roman Witula, Ramanujan Cubic Polynomials of the Second Kind, Journal of Integer Sequences, Vol. 13 (2010), Article 10.7.5.
Roman Witula, Ramanujan Type Trigonometric Formulae, Demonstratio Math. 45 (2012) 779-796.
Index entries for linear recurrences with constant coefficients, signature (3,4,1).

Cf. A006053, A214683, A215076, A215100.

a:=[0,2,7]; [ n le 3 select a[n] else 3*Self(n-1) + 4*Self(n-2) + Self(n-3): n in [1..25]]; // Marius A. Burtea, Oct 03 2019

with(linalg): M[1]:=matrix(3,3,[0,1,1,1,1,2,1,2,2]): for n from 2 to 25 do M[n]:=multiply(M[1],M[n-1]) od: seq(M[n][1,1],n=1..25);

LinearRecurrence[{3,4,1},{0,2,7},40] (* Roman Witula, Aug 02 2012 *)

a(n)=([0,1,0; 0,0,1; 1,4,3]^(n-1)*[0;2;7])[1,1] \\ Charles R Greathouse IV, Jun 22 2016

@CachedFunction
def a(n): # a = A120757
    if (n<3): return (0,2,7)[n]
    else: return 3*a(n-1) + 4*a(n-2) + a(n-3)
[a(n) for n in range(40)] # G. C. Greubel, Nov 25 2022

a(n) = 3*a(n-1) + 4*a(n-2) + a(n-3) (follows from the minimal polynomial of the matrix M). See also the o.g.f. given in the name.

Edited by N. J. A. Sloane, Dec 03 2006

New name, old name as comment; o.g.f.; reference.

A122600 Expansion of 1/(1 + 3x - 4x^2 + x^3).

Original entry on oeis.org

1, -3, 13, -52, 211, -854, 3458, -14001, 56689, -229529, 929344, -3762837, 15235416, -61686940, 249765321, -1011279139, 4094585641, -16578638800, 67125538103, -271785755150, 1100438056662, -4455582728689, 18040286167865, -73043627475013, 295747609825188, -1197457625543481

Offset: 0

Roger L. Bagula and Gary W. Adamson, Sep 20 2006

Suggested by the Steinbach heptagon polynomial p^3 - 2*p^2*(1 - p) - p(1 - p)^2 + (1 - p)^3 = (1 - 4 p + 3 p^2 + p^3).

B(n):=|a(n-1)| = a(n-1)*(-1)^(n-1) with B(0):=0 (hence the o.g.f. for B(n) is x/(1 + 3*x - 4*x^2 + x^3)) appears in the following formula for the nonnegative 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 C(n)= A120757(n) with C(0):=1, and A(n)= A181879(n). For the nonpositive powers see A085810*(-1)^n, A181880(n) and A116423(n)*(-1)^n, respectively. See also a comment under A052547.

Toufik Mansour and Mark Shattuck, Avoidance of vincular patterns by flattened derangements, arXiv:2504.14713 [math.CO], 2025. See p. 6.
Peter Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
Index entries for linear recurrences with constant coefficients, signature (-3,4,-1).

Cf. A065941.

p[x_] := 1 - 4 x + 3x^2 + x^3; q[x_] := ExpandAll[x^3*p[1/x]]; Table[ SeriesCoefficient[ Series[x/q[x], {x, 0, 30}], n], {n, 0, 30}]
CoefficientList[Series[1/(1 + 3*x - 4*x^2 + x^3), {x, 0, 50}], x] (* or *) LinearRecurrence[{-3, 4, -1}, {1, -3, 13}, 40] (* Vladimir Joseph Stephan Orlovsky, Jan 31 2012 *)

a(n)= -3*a(n-1) + 4*a(n-2) - a(n-3), n>=2, a(-1):=0, a(1)=0, a(1)=-3 (from the o.g.f. given in the name).
a(n) = (-1)^n*Sum_{k=0..n} binomial(n+k+2,3*k+2)*7^k. - Emanuele Munarini, Aug 27 2017
From Kai Wang, Jul 05 2020: (Start)
a(n) =  Sum_{i+2j+3k=n} (-1)^(i+k)*3^i*4^j*((i+j+k)!)/(i!*j!*k!).
a(n) = (-1)^n*(6*A215076(n+4) - 21*A215076(n+3) - 13*A215076(n+2))/7. (End)

Edited by N. J. A. Sloane, Feb 01 2007

A181879 Expansion of x(1+x)/(1-3x-4*x^2-x^3).

Original entry on oeis.org

0, 1, 4, 16, 65, 263, 1065, 4312, 17459, 70690, 286218, 1158873, 4692181, 18998253, 76922356, 311452261, 1261044460, 5105864780, 20673224441, 83704176903, 338911293253, 1372223811812, 5556020785351, 22495868896554, 91083913642878, 368791237300201, 1493205235368669, 6045864568949689, 24479205885623944, 99114281168039257, 401305531615563236

Offset: 0

Wolfdieter Lang, Nov 26 2010

a(n) appears in the following formula for the nonnegative 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, called there Q(rho). (rho*sigma)^n = C(n) + B(n)*rho + a(n)*sigma,n>=0, with C(n)= A120757(n) with C(0):=1, and B(n)= |A122600(n-1)| with B(0)=1. For the nonpositive powers see A085810(n)*(-1)^n, A181880(n-2)*(-1)^n and A116423(n+1)*(-1)^(n+1), respectively. See also a comment under A052547.

P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
Index entries for linear recurrences with constant coefficients, signature (3,4,1).

CoefficientList[Series[x (1+x)/(1-3x-4x^2-x^3),{x,0,40}],x] (* or *) LinearRecurrence[{3,4,1},{0,1,4},40] (* Harvey P. Dale, Feb 04 2024 *)

Vec((1+x)/(1-3*x-4*x^2-x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 24 2012

a(n) = 3*a(n-1) + 4*a(n-2) + a(n-3), n>=2, a(-1):=1, a(0)=0, a(1)=1.

A181880 Expansion of 1/(1-4x-3x^2-x^3).

Original entry on oeis.org

1, 4, 19, 89, 417, 1954, 9156, 42903, 201034, 942001, 4414009, 20683073, 96916320, 454128508, 2127946065, 9971086104, 46722311119, 218930448853, 1025859814873, 4806952917170, 22524321562152, 105544004814991, 494555936863590, 2317380083461485, 10858732149251701, 50881624784254849, 238420075668235984, 1117183909174960184, 5234877488488803537, 24529481757148330684

Offset: 0

Wolfdieter Lang, Nov 27 2010

B(n):=a(n-2)*(-1)^n, B(0):=0, B(1):=0, (o.g.f. x^2/(1 + 4*x + 3*x^2 -x^3))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 C(n)= A085810(n)*(-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.

P. Steinbach, Golden fields: a case for the heptagon, Math. Mag. 70 (1997), no. 1, 22-31.
Index entries for linear recurrences with constant coefficients, signature (4, 3, 1).

CoefficientList[Series[1/(1-4*x-3*x^2-x^3),{x,0,40}],x] (* or *) LinearRecurrence[{4,3,1},{1,4,19},40] (* Vladimir Joseph Stephan Orlovsky, Feb 01 2012 *)

O.g.f.: 1/(1-4*x-3*x^2-x^3).

a(n) = 4*a(n) + 3*a(n-2) +a(n-3), n>=2, a(-1):=0, a(0)=1, a(1)=4.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A120757 Expansion of x^2*(2+x)/(1-3*x-4*x^2-x^3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A122600 Expansion of 1/(1 + 3*x - 4*x^2 + x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A181879 Expansion of x*(1+x)/(1-3*x-4*x^2-x^3).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

A181880 Expansion of 1/(1-4*x-3*x^2-x^3).

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A120757 Expansion of x^2(2+x)/(1-3x-4*x^2-x^3).

A122600 Expansion of 1/(1 + 3x - 4x^2 + x^3).

A181879 Expansion of x(1+x)/(1-3x-4*x^2-x^3).

A181880 Expansion of 1/(1-4x-3x^2-x^3).