A085810 -id:A085810 - cp's OEIS frontend

A005021 Random walks (binomial transform of A006054).

1, 5, 19, 66, 221, 728, 2380, 7753, 25213, 81927, 266110, 864201, 2806272, 9112264, 29587889, 96072133, 311945595, 1012883066, 3288813893, 10678716664, 34673583028, 112584429049, 365559363741, 1186963827439, 3854047383798, 12514013318097, 40632746115136

Offset: 0

N. J. A. Sloane

Number of walks of length 2n+5 in the path graph P_6 from one end to the other one. Example: a(1)=5 because in the path ABCDEF we have ABABCDEF, ABCBCDEF, ABCDCDEF, ABCDEDEF and ABCDEFEF. - Emeric Deutsch, Apr 02 2004
Since a(n) is the binomial transform of A006054 from formula (3.63) in the Witula-Slota-Warzynski paper, it follows that a(n)=A(n;1)*(B(n;-1)-C(n;-1))-B(n;1)*B(n;-1)+C(n;1)*(A(n;-1)-B(n;-1)+C(n;-1)), where A(n;1)=A077998(n), B(n;1)=A006054(n+1), C(n;1)=A006054(n), A(n;-1)=A121449(n), B(n+1;-1)=-A085810(n+1), C(n;-1)=A215404(n) and A(n;d), B(n;d), C(n;d), n in N, d in C, denote the quasi-Fibonacci numbers defined and discussed in comments in A121449 and in the cited paper. - Roman Witula, Aug 09 2012
From Wolfdieter Lang, Mar 30 2020: (Start)
With offset -4 this sequence 6, 1, 0, 0, 1, 5, ... appears in the formula for the n-th power of the 3 X 3 tridiagonal Matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: (M_3)^n = a(n-2)*(M_3)^2 - (6*a(n-3) - a(n-4))*M_3 + a(n-3)*1_3, with the 3 X 3 unit matrix 1_3, for n >= 0. Proof from Cayley-Hamilton: (M_3)^n = 5*(M_3)^3 - 6*M_3 + 1_3 (see A332602 for the characteristic polynomial Phi(3, x)), and the recurrence (M_3)^n = M_3*(M_3)^(n-1). For (M_3)^n[1,1] = 2*a(n-2) - 5*a(n-3) + a(n-4), for n >= 0, see A080937(n).
The formula for a(n) in terms of r = rho(7) = A160389 given below shows that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796... for n -> infinity. This is because r - 2/r = 0.692..., and r - 1 - 1/r = 0.137... .
(End)

W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025. See p. 26.
Jean-Luc Baril and Helmut Prodinger, Enumeration of partial Lukasiewicz paths, arXiv:2205.01383 [math.CO], 2022.
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
C. J. Everett and P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45.
C. J. Everett and P. R. Stein, The combinatorics of random walk with absorbing barriers, Discrete Math. 17 (1977), no. 1, 27-45. [Annotated scanned copy]
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
S. Morier-Genoud, V. Ovsienko and S. Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987; arXiv:1008.3359 [math.AG], 2010-2011. - From _N. J. A. Sloane_, Dec 26 2012
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
N. J. A. Sloane, Transforms
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
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 (5,-6,1).

Double partial sums of A060557. Bisection of A052547.

Cf. A094789, A094790, A080937, A160389, A116425, A322602.

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

a:=k->sum(binomial(5+2*k,7*j+k-2),j=ceil((2-k)/7)..floor((7+k)/7))-sum(binomial(5+2*k,7*j+k-1),j=ceil((1-k)/7)..floor((6+k)/7)): seq(a(k),k=0..25);
A005021:=-(z-1)*(z-5)/(-1+5*z-6*z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence apart from the initial 1

LinearRecurrence[{5,-6,1}, {1,5,19}, 50] (* Roman Witula, Aug 09 2012 *)
CoefficientList[Series[1/(1 - 5 x + 6 x^2 - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

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

G.f.: 1/(1-5x+6x^2-x^3). - Emeric Deutsch, Apr 02 2004
a(n) = 5*a(n-1) -6*a(n-2) +a(n-3). - Emeric Deutsch, Apr 02 2004
a(n) = Sum_{j=-infinity..infinity} (binomial(5+2*k, 7*j+k-2) - binomial(5+2*k, 7*j+k-1)) (a finite sum).
a(n-2) = 2^n*C(n;1/2)=(1/7)*((c(2)-c(4))*(c(4))^(2n) + (c(4)-c(1))*(c(1))^(2n) + (c(1)-c(2))*(c(2))^(2n)), where a(-2)=a(-1):=0, c(j):=2*cos(2Pi*j/7). This formula follows from the Binet formula for C(n;d)--one of the quasi-Fibonacci numbers (see comments in A121449 and the formula (3.17) in the Witula-Slota-Warzynski paper). - Roman Witula, Aug 09 2012
In terms of the algebraic number r = rho(7) = 2*cos(Pi/7) = A160389 of degree 3 the preceding formula gives a(n) = r^(2*(n+2))*(A1(r) + A2(r)*(r - 2/r)^(2*(n+1)) = A3(r)*(r - 1 - 1/r)^(2*(n+1)))/7, for n >= -4 (see a comment above for this offset), with A1(r) = -r^2 + 2*r + 1, A2(r) = -r^2 - r + 2, and A3(r) = 2*r^2 - r - 3. - Wolfdieter Lang, Mar 30 2020

a(25)-a(26) from Vincenzo Librandi, Sep 18 2015

A094789 Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 4.

Original entry on oeis.org

1, 4, 14, 47, 155, 507, 1652, 5373, 17460, 56714, 184183, 598091, 1942071, 6305992, 20475625, 66484244, 215873462, 700937471, 2275930827, 7389902771, 23994866364, 77910846021, 252974934692, 821404463698, 2667083556359

Offset: 1

Herbert Kociemba, Jun 11 2004

In general, a(n) = (2/m)*Sum_{r=1..m-1} sin(r*j*Pi/m)*sin(r*k*Pi/m)*(2*cos(r*Pi/m))^(2n+1) counts (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < m and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = j, s(2n+1) = k.
With interpolated zeros (0,0,0,1,0,4,0,14,...) counts walks of length n between the start and fourth nodes on P_6. - Paul Barry, Jan 26 2005
The Hankel transforms of this sequence or of this sequence with the first term omitted give 1, -2, 1, 1, -2, 1, ... . - Wathek Chammam, Nov 16 2011
Diagonal of the square array A216201. - Philippe Deléham, Mar 28 2013

G. C. Greubel, Table of n, a(n) for n = 1..1000
W. Chammam, F. Marcellán and R. Sfaxi, Orthogonal polynomials, Catalan numbers, and a general Hankel determinant evaluation, Linear Algebra Appl. (2011), in press.
S. Morier-Genoud, V. Ovsienko and S. Tabachnikov, 2-frieze patterns and the cluster structure of the space of polygons, Annales de l'institut Fourier, 62 no. 3 (2012), 937-987; arXiv:1008.3359 [math.AG], 2010-2011. - _N. J. A. Sloane_, Dec 26 2012
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
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 (5,-6,1).

Cf. A094790, A080937, A005021.

I:=[1,4,14]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..45]]; // Vincenzo Librandi, Nov 10 2014

f[n_] := FullSimplify[ TrigToExp[(2/7)Sum[ Sin[Pi*k/7]Sin[4Pi*k/7](2Cos[Pi*k/7])^(2n + 1), {k, 1, 6}]]]; Table[ f[n], {n, 25}] (* Robert G. Wilson v, Jun 18 2004 *)
LinearRecurrence[{5,-6,1}, {1,4,14}, 50] (* Roman Witula, Aug 09 2012 *)
CoefficientList[Series[(x - 1) / (- 1 + 5 x - 6 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 10 2014 *)

Vec(x*(x-1)/(-1 + 5*x - 6*x^2 + x^3) + O(x^40)) \\ Michel Marcus, Nov 10 2014

a(n) = (2/7)*Sum_{k = 1..6} sin(Pi*k/7)*sin(4*Pi*k/7)*(2*cos(Pi*k/7))^(2n + 1).
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3).
G.f.: x*(x-1)/(-1 + 5*x - 6*x^2 + x^3). - Corrected by Vincenzo Librandi, Nov 10 2014
a(n) = 2^n*B(n; 1/2) = (1/7)*((c(1) - c(4))*(c(4))^(2n) + (c(2) - c(1))*(c(1))^(2n) + (c(4) - c(2))*(c(2))^(2n)), where c(j) := 2*cos(2*Pi*j/7). Here B(n; d), n in N, d in C denotes the respective quasi-Fibonacci number - see A121449 and Witula-Slota-Warzynski paper for details (see also A052975, A085810, A077998, A006054, A121442). - Roman Witula, Aug 09 2012
a(n+1) = A216201(n,n+2) = A216201(n,n+3). - Philippe Deléham, Mar 28 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.

A052975 Expansion of (1-2x)(1-x)/(1-5x+6x^2-x^3).

Original entry on oeis.org

1, 2, 6, 19, 61, 197, 638, 2069, 6714, 21794, 70755, 229725, 745889, 2421850, 7863641, 25532994, 82904974, 269190547, 874055885, 2838041117, 9215060822, 29921113293, 97153242650, 315454594314, 1024274628963, 3325798821581, 10798800928441, 35063486341682

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 3, s(2n) = 3. - Herbert Kociemba, Jun 11 2004

Counts all paths of length (2*n), n>=0, starting at the initial node and ending on the nodes 1, 2, 3, 4 and 5 on the path graph P_6, see the second Maple program. - Johannes W. Meijer, May 29 2010

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1047
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
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 (5,-6,1).

Cf. A060557.

Cf. A028495, A078038 and A094790.

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

spec := [S,{S=Sequence(Prod(Union(Sequence(Prod(Sequence(Z),Z)),Sequence(Z)),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
with(GraphTheory):G:=PathGraph(6): A:= AdjacencyMatrix(G): nmax:=25; n2:=2*nmax+1: for n from 0 to n2 do B(n):=A^n; a(n):=add(B(n)[k,1],k=1..5); od: seq(a(2*n),n=0..nmax); # Johannes W. Meijer, May 29 2010

LinearRecurrence[{5,-6,1}, {1,2,6}, 50] (* Roman Witula, Aug 09 2012 *)
CoefficientList[Series[(1 - 2 x) (1 - x)/(1 - 5 x + 6 x^2 - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

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

G.f.: (1-2*x)*(1-x)/(1-5*x+6*x^2-x^3).
a(n) = A028495(2*n). - Floor van Lamoen, Nov 02 2005
a(n) = Sum (1/7*(2-3*_alpha+_alpha^2)*_alpha^(-1-n), _alpha=RootOf(-1+5*_Z-6*_Z^2+_Z^3))
From Herbert Kociemba, Jun 11 2004: (Start)
a(n) = (2/7)*Sum_{r=1..6} sin(r*3*Pi/7)^2*(2*cos(r*Pi/7))^(2*n).
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). (End)
a(n) = 2^n*A(n;1/2) = (1/7)*(s(2)^2*c(4)^(2n) + s(4)^2*c(1)^(2n) + s(1)^2*c(2)^(2n)), where c(j):=2*cos(2Pi*j/7) and s(j):=2*sin(2*Pi*j/7). Here A(n;d), n in N, d in C denotes the respective quasi-Fibonacci number - see A121449 and Witula-Slota-Warzynski paper for details (see also A094789, A085810, A077998, A006054, A121442). I note that my and the respective Herbert Kociemba's formulas are "compatible". - Roman Witula, Aug 09 2012
a(n) = A005021(n)-3*A005021(n-1)+2*A005021(n-2). - R. J. Mathar, Feb 27 2019

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

Original entry on oeis.org

1, 1, 3, 8, 22, 61, 170, 475, 1329, 3721, 10422, 29196, 81797, 229178, 642125, 1799169, 5041123, 14124860, 39576902, 110891905, 310712054, 870595599, 2439354329, 6834918465, 19151015274, 53659951372, 150351841201, 421276495414, 1180390506681, 3307380699281

Offset: 0

Philippe Deléham, Sep 06 2006

From Roman Witula, Aug 07 2012: (Start)
In the cited Witula-Slota-Warzynski paper three so-called quasi-Fibonacci numbers A(n;d), B(n;d) and C(n;d), where n = 0,1,...,d \in C are discussed. These numbers are created by each of the following relations:
(1+d*c(j))^n = A(n;d) + B(n;d)*c(j) + C(n;d)*c(2*j), for every j=1,2,4, where c(j):=2*cos(2*Pi*j/7).
In fact all these "numbers" are integer polynomials of the argument d.
In the sequel for d=-1 we obtain A(n;-1)=a(n), B(n+1;-1)=-A085810(n).
Moreover, we have A(n;1)=A077998(n), B(n;1)=A006054(n+1), C(n;1)=A006054(n), and A(n;2)=A121442(n).
We note that the elements of the sequences A(n;-1), B(n;-1), and C(n;-1) satisfy the following system of recurrence equations:
A(0;-1)=1, B(0;-1)=C(0;-1)=0,
A(n+1;-1)=A(n;-1)-2*B(n;-1)+C(n;-1),
B(n+1;-1)=-A(n;-1)+B(n;-1), C(n+1;-1)=-B(n;-1)+2*C(n;-1).
It is proved that binomial transforms of the sequences: A(n;1), B(n;1), and C(n;1) are equal to the following sequences:
A(n;1)*(A(n;-1)-C(n;-1))-B(n;1)*(B(n;-1)+C(n;-1))+C(n;1)*B(n;-1), -A(n;1)*C(n;-1)+B(n;1)*(A(n;-1)-C(n;-1))-C(n;1)*(B(n;-1)-C(n;-1)), and
A(n;1)*(B(n;-1)-C(n;-1))-B(n;1)*B(n;-1)+C(n;1)*(A(n;-1)-B(n;-1)+C(n;-1)), respectively, whereas we have
A(n;-1) = Sum_{k=0..n} binomial(n,k)*(A(k;1)*A(n-k;1)-A(k;1)*B(n-k;1)-B(k;1)*C(n-k;1)-A(n-k;1)*C(k;1)+2*B(n-k;1)*C(k;1)-C(k;1)*C(n-k;1)),
B(n;-1) = Sum_{k=0..n} binomial(n,k)*(-A(k;1)*B(n-k;1)+A(k;1)*C(n-k;1)+B(k;1)*B(n-k;1)-A(n-k;1)*C(k;1)+B(n-k;1)*C(k;1)-C(k;1)*C(n-k;1)), and
C(n;-1) = Sum_{k=0..n} binomial(n,k)*(-A(k;1)*B(n-k;1)+A(n-k;1)*B(k;1)+B(k;1)*B(n-k;1)-B(k;1)*C(n-k;1)-A(n-k;1)*C(k;1)) (see identities (3.50-52) and (3.61-63) in the Witula-Slota-Warzynski paper).
(End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
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. A085810, A077998, A006054.

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

CoefficientList[Series[(1 - 3*x + 2*x^2)/(1-4*x + 3*x^2 + x^3), {x, 0, 200}], x] (* Stefan Steinerberger, Sep 11 2006 *)
LinearRecurrence[{4,-3,-1},{1,1,3},50] (* Roman Witula, Aug 07 2012 *)

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

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

7*a(n) = (2-c(4))*(1-c(1))^n + (2-c(1))*(1-c(2))^n + (2-c(2))*(1-c(4))^n = (s(2))^2*(1-c(1))^n + (s(4))^2*(1-c(2))^n + (s(1))^2*(1-c(4))^n, where c(j):=2*cos(2*Pi*j/7) and s(j):=2*sin(2*Pi*j/7) -- it is the special case, for d=-1, of the Binet's formula for the respective quasi-Fibonacci number A(n;d) discussed in the Witula-Slota-Warzynski paper. - Roman Witula, Aug 07 2012

More terms from Stefan Steinerberger, Sep 11 2006

a(27)-a(29) from Vincenzo Librandi, Sep 18 2015

A121442 Expansion of (1-x^2)/(1-x-9*x^2+x^3).

Original entry on oeis.org

1, 1, 9, 17, 97, 241, 1097, 3169, 12801, 40225, 152265, 501489, 1831649, 6192785, 22176137, 76079553, 269472001, 932011841, 3281180297, 11399814865, 39998425697, 139315579185, 487901595593, 1701743382561, 5953542163713, 20781331011169, 72661467102025

Offset: 0

Philippe Deléham, Sep 06 2006

From Roman Witula, Aug 08 2012: (Start)
We have a(n)=A(n;2), where A(n;2), B(n;2) and C(n;2) are the special cases of so-called quasi-Fibonacci numbers A(n;d), B(n;d), and C(n;d) for the value of argument d=2 - for details see Witula's comments to A121449 or the paper of Witula-Slota-Warzynski's. The sequences A(n;2), B(n;2) and C(n;2) are defined by the following system of recurrence equations:
A(0;2)=1, B(0;2)=C(0;2)=0,
A(n+1;2)=A(n;2)+4*B(n;2)-2*C(n;2), B(n+1;2)=2*A(n;2)+B(n;2), and C(n+1;2)=2*B(n;2)-C(n;2).
We note that A(n;1)=A077998(n), B(n;1)=A006054(n+1), and C(n;1)=A006054(n). We know (see formulas (3.61-63) in Witula et al.'s paper) that the sequences: (-2)^(-n)*(A(n;1)*(A(n;2)-C(n;2))-B(n;1)*(B(n;2)+C(n;2))+C(n;1)*B(n;2)), (-2)^(-n)*(-A(n;1)*C(n;2)+B(n;1)*(A(n;2)-C(n;2))-C(n;1)*(B(n;2)-C(n;2))), and (-2)^(-n)*(A(n;1)*(B(n;2)-C(n;2))-B(n;1)*B(n;2)+C(n;1)*(A(n;2)-B(n;2)+C(n;2))) are the binomial transforms of the sequences (-2)^(-n)*A(n;1), (-2)^(-n)*B(n;1), and (-2)^(-n)*C(n;1) respectively. Moreover the elements of the sequences A(n;1/2)=2^(-n)*A052975, B(n;1/2)=2^(-n)*A094789, and C(n;1/2) could be described by certain convolutions type identities for the elements of A(n;2), B(n;2), and C(n;2) (see identities (3.58-60) in Witula et al.'s paper). (End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
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 (1, 9, -1).

Cf. A077998, A006054, A121449, A085810.

I:=[1,1,9]; [n le 3 select I[n] else Self(n-1)+9*Self(n-2)-Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015

LinearRecurrence[{1,9,-1},{1,1,9},50] (* Roman Witula, Aug 08 2012 *)
CoefficientList[Series[(1 - x^2)/(1 - x - 9 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

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

a(0)=a(1)=1, a(2)=9, a(n+1) = a(n)+9*a(n-1)-a(n-2) for n>=2.

7*a(n) = (2-c(4))*(1-2*c(1))^n + (2-c(1))*(1-2*c(2))^n + (2-c(2))*(1-2*c(4))^n = (s(2))^2*(1-2*c(1))^n + (s(4))^2*(1-2*c(2))^n + (s(1))^2*(1-2*c(4))^n, where c(j):=2*Cos(2Pi*j/7) and s(j):=2*Sin(2Pi*j/7) - it is the special case, for d=2, of the Binet's formula for the respective quasi-Fibonacci number A(n;d) discussed in Witula-Slota-Warzynski's paper (see also A121449). - Roman Witula, Aug 08 2012

Corrected by T. D. Noe, Oct 25 2006

More terms from Vincenzo Librandi, Sep 18 2015

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

A116423 Binomial transform of A006053.

Original entry on oeis.org

0, 1, 3, 9, 26, 74, 209, 588, 1651, 4631, 12983, 36388, 101972, 285741, 800660, 2243445, 6286059, 17613241, 49351342, 138279586, 387451077, 1085614208, 3041824015, 8523002359, 23880923183, 66912861640, 187485674652, 525323190505, 1471922876424, 4124236259529

Offset: 1

Gary W. Adamson, Feb 14 2006

nonn

a(n)/a(n-1) tends to 2.801... = 1 + 2*cos(Pi/7).
A(n) := a(n+1)*(-1)^(n+1) 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 B(n)= A181880(n-2)*(-1)^n. For the nonnegative powers see A120757(n), |A122600(n-1)| and A181879(n), respectively. See also a comment under A052547.
This sequence is constructible as a spiral tiling of similar trapezoids, as follows: start with an isosceles trapezoid with side lengths 3,1,4,1. Each new trapezoid is rotated and scaled so one leg fills all unoccupied space on the short base of the previous trapezoid. a(n) is given by the length of the n-th trapezoid's legs. This process is identical to the recursion relation added by R. J. Mathar in the Formula section. See the Links section for an illustration. - Andrew B. Hudson, Jun 19 2019

			a(5) = 26 = 1*0 + 1*4 + 4*1 + 4*3 + 6*1 = 4 + 4 + 12 + 6 = 26.

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Andrew B. Hudson, Illustration of the first 7 terms as a spiral tiling of similar trapezoids.
Peter Steinbach, Golden Fields: A Case for the Heptagon, Mathematics Magazine, Vol. 70, No. 1, Feb. 1997.
Index entries for linear recurrences with constant coefficients, signature (4,-3,-1)

Cf. A006053.

I:=[0,1,3]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)-Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jul 11 2019

LinearRecurrence[{4, -3, -1}, {0, 1, 3}, 40] (* Vincenzo Librandi, Jul 11 2019 *)

concat(0, Vec(x^2*(1-x)/(1-4*x+3*x^2+x^3) + O(x^50))) \\ Michel Marcus, Sep 13 2014

Binomial transform of A006053 starting with A006053(1): (0, 1, 1, 3, 4, 9, 14, ...).
From R. J. Mathar, Apr 02 2008: (Start)
O.g.f.: x^2(1-x)/(1 - 4x + 3x^2 + x^3).
a(n) = 4*a(n-1) - 3*a(n-2) - a(n-3). (End)

More terms from R. J. Mathar, Apr 02 2008

More terms from Michel Marcus, Sep 13 2014

A215404 a(n) = 4a(n-1) - 3a(n-2) - a(n-3), with a(0)=0, a(1)=0 and a(2)=1.

Original entry on oeis.org

0, 0, 1, 4, 13, 39, 113, 322, 910, 2561, 7192, 20175, 56563, 158535, 444276, 1244936, 3488381, 9774440, 27387681, 76739023, 215018609, 602469686, 1688083894, 4729907909, 13252910268, 37133833451, 104046695091, 291532369743, 816855560248, 2288778436672, 6413014696201

Offset: 0

Roman Witula, Aug 09 2012

We have a(n)=C(n;-1), A121449(n)=A(n;-1), A085810(n+1)=-B(n+1;-1), where A(n;d), B(n;d), and C(n;d), n in N, d in C, are so-called quasi-Fibonacci numbers defined and discussed in the comments to A121449 and in Witula-Slota-Warzynski's paper. It follows from formulas (3.47-49) in this paper that the value of A(n;1/3), B(n;1/3) and C(n;1/3) could be obtained from special convolution type identities for sequences a(n), A121449, and A085810.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Ilya Amburg, Krishna Dasaratha, Laure Flapan, Thomas Garrity, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse, and Matthew Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239 [math.CO], 2015.
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
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. A077998, A006054, A121449, A085810, A052975, A094789, A005021, A121442.

I:=[0,0,1]; [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}, {0,0,1}, 50]
CoefficientList[Series[x^2/(1 - 4 x + 3 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)

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

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

a(n) = (1/7)*((c(2)-c(4))*(1-c(1))^n + (c(4)-c(1))*(1-c(2))^n + (c(1)-c(2))*(1-c(4))^n), where c(j):=2*cos(2*Pi*j/7) - this formula is the Binet formula for a(n) (see the Binet formula (3.17) for the respective quasi-Fibonacci number C(n;d) for value d=-1 in the Witula-Slota-Warzynski paper).

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.

cp's OEIS Frontend

A005021 Random walks (binomial transform of A006054).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A094789 Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

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

A052975 Expansion of (1-2*x)*(1-x)/(1-5*x+6*x^2-x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A121442 Expansion of (1-x^2)/(1-x-9*x^2+x^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

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

A052975 Expansion of (1-2x)(1-x)/(1-5x+6x^2-x^3).

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

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

A215404 a(n) = 4a(n-1) - 3a(n-2) - a(n-3), with a(0)=0, a(1)=0 and a(2)=1.

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