A154626 -id:A154626 - cp's OEIS frontend

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

1, 0, 2, 1, 6, 7, 22, 36, 89, 168, 377, 756, 1630, 3353, 7110, 14783, 31130, 65016, 136513, 285648, 599041, 1254456, 2629418, 5508097, 11542854, 24183271, 50674318, 106173180, 222470009, 466131960, 976694489, 2046447180, 4287928678, 8984443769, 18825088134

Offset: 1

Clark Kimberling, Jun 26 2011

Polynomial reduction: an introduction
...
We begin with an example.  Suppose that p(x) is a polynomial, so that p(x)=(x^2)t(x)+r(x) for some polynomials t(x) and r(x), where r(x) has degree 0 or 1.  Replace x^2 by x+1 to get (x+1)t(x)+r(x), which is (x^2)u(x)+v(x) for some u(x) and v(x), where v(x) has degree 0 or 1.  Continuing in this manner results in a fixed polynomial w(x) of degree 0 or 1.  If p(x)=x^n, then w(x)=x*F(n)+F(n-1), where F=A000045, the sequence of Fibonacci numbers.
In order to generalize, write d(g) for the degree of an arbitrary polynomial g(x), and suppose that p, q, s are polynomials satisfying d(s)s in this manner until reaching w such that d(w)s.
The coefficients of (reduction of p by q->s) comprise a vector of length d(q)-1, so that a sequence p(n,x) of polynomials begets a sequence of vectors, such as (F(n), F(n-1)) in the above example.  We are interested in the component sequences (e.g., F(n-1) and F(n)) for various choices of p(n,x).
Following are examples of reduction by x^2->x+1:
n-th Fibonacci p(x) -> A192232+x*A112576
n-th cyclotomic p(x) -> A192233+x*A051258
n-th 1st-kind Chebyshev p(x) -> A192234+x*A071101
n-th 2nd-kind Chebyshev p(x) -> A192235+x*A192236
x(x+1)(x+2)...(x+n-1) -> A192238+x*A192239
(x+1)^n -> A001519+x*A001906
(x^2+x+1)^n -> A154626+x*A087635
(x+2)^n -> A020876+x*A030191
(x+3)^n -> A192240+x*A099453
...
Suppose that b=(b(0), b(1),...) is a sequence, and let p(n,x)=b(0)+b(1)x+b(2)x^2+...+b(n)x^n.  We define (reduction of sequence b by q->s) to be the vector given by (reduction of p(n,x) by q->s), with components in the order of powers, from 0 up to d(q)-1.  For k=0,1,...,d(q)-1, we then have the "k-sequence of (reduction of sequence b by q->s)".  Continuing the example, if b is the sequence given by b(k)=1 if k=n and b(k)=0 otherwise, then the 0-sequence of (reduction of b by x^2->x+1) is (F(n-1)), and the 1-sequence is (F(n)).
...
For selected sequences b, here are the 0-sequences and 1-sequences of (reduction of b by x^2->x+1):
b=A000045, Fibonacci sequence (1,1,2,3,5,8,...) yields
   0-sequence A166536 and 1-sequence A064831.
b=(1,A000045)=(1,1,1,2,3,5,8,...) yields
   0-sequence A166516 and 1-sequence A001654.
b=A000027, natural number sequence (1,2,3,4,...) yields
  0-sequence A190062 and 1-sequence A122491.
b=A000032, Lucas sequence (1,3,4,7,11,...) yields
  0-sequence A192243 and 1-sequence A192068.
b=A000217, triangular sequence (1,3,6,10,...) yields
  0-sequence A192244 and 1-sequence A192245.
b=A000290, squares sequence (1,4,9,16,...) yields
  0-sequence A192254 and 1-sequence A192255.
More examples:  A192245-A192257.
...
More comments:
(1) If s(n,x)=(reduction of x^n by q->s) and
    p(x)=p(0)x^n+p(1)x^(n-1)+...+p(n)x^0, then
    (reduction of p by q->s)=p(0)s(n,x)+p(1)s(n-1,x)
    +...+p(n-1)s(1,x)+p(n)s(0,x).  See A192744.
(2) For any polynomial p(x), let P(x)=(reduction of p(x)
    by q->s).  Then P(r)=p(r) for each zero r of
    q(x)-s(x).  In particular, if q(x)=x^2 and s(x)=x+1,
    then P(r)=p(r) if r=(1+sqrt(5))/2 (golden ratio) or
    r=(1-sqrt(5))/2.

			The first four Fibonacci polynomials and their reductions by x^2->x+1 are shown here:
F1(x)=1 -> 1 + 0x
F2(x)=x -> 0 + 1x
F3(x)=x^2+1 -> 2+1x
F4(x)=x^3+2x -> 1+4x
F5(x)=x^4+3x^2+1 -> (x+1)^2+3(x+1)+1 -> 6+6x.
From these, read A192232=(1,0,1,1,6,...) and A112576=(0,1,1,4,6,...).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,3,-1,-1).

Cf. A168561, A192233 - A192240, A192744.

Cf. A206296, A265398, A265399, A265752, A265753.

q[x_] := x + 1;
reductionRules = {x^y_?EvenQ -> q[x]^(y/2),  x^y_?OddQ -> x q[x]^((y - 1)/2)};
t = Table[FixedPoint[Expand[#1 /. reductionRules] &, Fibonacci[n, x]], {n, 1, 40}];
Table[Coefficient[Part[t, n], x, 0], {n, 1, 40}]
  (* A192232 *)
Table[Coefficient[Part[t, n], x, 1], {n, 1, 40}]
(* A112576 *)
(* Peter J. C. Moses, Jun 25 2011 *)
LinearRecurrence[{1, 3, -1, -1}, {1, 0, 2, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 08 2012 *)

Vec((1-x-x^2)/(1-x-3*x^2+x^3+x^4)+O(x^99)) \\ Charles R Greathouse IV, Jan 08 2013

Empirical G.f.: -x*(x^2+x-1)/(x^4+x^3-3*x^2-x+1). - Colin Barker, Sep 11 2012
The above formula is correct. - Charles R Greathouse IV, Jan 08 2013
a(n) = A265752(A206296(n)). - Antti Karttunen, Dec 15 2015
a(n) = A112576(n) -A112576(n-1) -A112576(n-2). - R. J. Mathar, Dec 16 2015

Example corrected by Clark Kimberling, Dec 18 2017

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

Original entry on oeis.org

1, 1, 5, 21, 89, 377, 1597, 6765, 28657, 121393, 514229, 2178309, 9227465, 39088169, 165580141, 701408733, 2971215073, 12586269025, 53316291173, 225851433717, 956722026041, 4052739537881, 17167680177565, 72723460248141, 308061521170129, 1304969544928657, 5527939700884757

Offset: 0

Olivier Gérard

If one deletes the leading 0 in A084326, takes the inverse binomial transform, and adds a(0)=1 in front, one obtains this sequence here. - Al Hakanson (hawkuu(AT)gmail.com), May 02 2009
For n >= 1, row sums of triangle
  m |k=0     1     2     3     4     5     6     7
====+=============================================
  0 |  1
  1 |  1     4
  2 |  1     4    16
  3 |  1     8    16    64
  4 |  1     8    48    64   256
  5 |  1    12    48   256   256  1024
  6 |  1    12    96   256  1280  1024  4096
  7 |  1    16    96   640  1280  6144  4096 16384
which is triangle for numbers 4^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012
a(n) = a(n;-2) = 3^n*Sum_{k=0..n} binomial(n,k)*F(k+1)*(-2/3)^k, where a(n;d), n=0,1,...,d, denotes the delta-Fibonacci numbers defined in comments to A000045 (see also the papers of Witula et al.). We note that (see A033887) F(3n+1) = 3^n*a(n,2/3) = Sum_{k=0..n} binomial(n,k)*F(k-1)*(-2/3)^k, which implies F(3n+1) + 3^(-n)*a(n) = Sum_{k=0..n} binomial(n,k)*L(k)*(-2/3)^k, where L(k) denotes the k-th Lucas number. - Roman Witula, Jul 12 2012
a(n+1) is (for n >= 0) the number of length-n strings of 5 letters {0,1,2,3,4} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - Joerg Arndt, Oct 11 2012
Starting with offset 1 the sequence is the INVERT transform of (1, 4, 4*3, 4*3^2, 4*3^3, ...); i.e., of A003946: (1, 4, 12, 36, 108, ...). - Gary W. Adamson, Aug 06 2016
a(n+1) equals the number of quinary sequences of length n such that no two consecutive terms differ by 3. - David Nacin, May 31 2017

T. D. Noe, Table of n, a(n) for n = 0..200
Joerg Arndt, Matters Computational (The Fxtbook), pp. 313-315.
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38, 2012, pp. 1871-1876 (see Corollary 1 (vi)).
Gary Detlefs and Wolfdieter Lang, Improved Formula for the Multi-Section of the Linear Three-Term Recurrence Sequence, arXiv:2304.12937 [math.CO], 2023.
Amelia Gilson, Hadley Killen, Steven J. Miller, Nadia Razek, Joshua M. Siktar, and Liza Sulkin, Zeckendorf's Theorem Using Indices in an Arithmetic Progression, arXiv:2005.10396 [math.NT], 2020.
Edyta Hetmaniok, Bozena Piatek, and Roman Wituła, Binomials Transformation Formulae of Scaled Fibonacci Numbers, Open Math. 15 (2017), 477-485.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Tanya Khovanova, Recursive Sequences
Bahar Kuloğlu, Engin Özkan, and Marin Marin, Fibonacci and Lucas Polynomials in n-gon, An. Şt. Univ. Ovidius Constanţa (Romania 2023) Vol. 31, No 2, 127-140.
Roman Witula, Binomials transformation formulae of scaled Lucas numbers, Demonstratio Math. 46 (2013), 15-27.
R. Witula and Damian Slota, delta-Fibonacci numbers, Appl. Anal. Discr. Math 3 (2009) 310-329, MR2555042
Index entries for linear recurrences with constant coefficients, signature (4,1).

Cf. A001076, A147722 (INVERT transform), A109499 (INVERTi transform), A154626 (Binomial transform), A086344 (inverse binomial transform), A003946, A049310.

Cf. A000032, A000045, A014445, A014448, A033887, A046854, A055830, A055870, A084326, A167808.

[Fibonacci(3*n-1): n in [0..40]]; // Vincenzo Librandi, Jul 04 2015

with(combinat): a:=n->fibonacci(n,4)-3*fibonacci(n-1,4): seq(a(n), n=1..23); # Zerinvary Lajos, Apr 04 2008

Fibonacci/@(3*Range[0,30]-1) (* Vladimir Joseph Stephan Orlovsky, Mar 01 2010 *)
LinearRecurrence[{4,1},{1,1},30] (* Harvey P. Dale, May 15 2019 *)

a[0]:1$
a[1]:1$
a[n]:=4*a[n-1]+a[n-2]$
A015448(n):=a[n]$
makelist(A015448(n),n,0,30); /* Martin Ettl, Nov 03 2012 */

a(n) = fibonacci(3*n-1); \\ Altug Alkan, Dec 10 2015

a(n) = Fibonacci(3n-1) = ( (1+sqrt(5))*(2-sqrt(5))^n - (1-sqrt(5))*(2+sqrt(5))^n )/ (2*sqrt(5)).
O.g.f.: (1-3*x)/(1-4*x-x^2). - Len Smiley, Dec 09 2001
a(n) = Sum_{k=0..n} 3^k*A055830(n,k). - Philippe Deléham, Oct 18 2006
a(n) = upper left term in the 2 X 2 matrix [1,2; 2,3]^n. - Gary W. Adamson, Mar 02 2008
[a(n), A001076(n)] = [1,4; 1,3]^n * [1,0]. - Gary W. Adamson, Mar 21 2008
a(n) = A167808(3*n-1) for n > 0. - Reinhard Zumkeller, Nov 12 2009
a(n) = Fibonacci(3n+1) mod Fibonacci(3n), n > 0.
a(n) = (A000032(3*n)-Fibonacci(3*n))/2 = (A014448(n)-A014445(n))/2.
For n >= 2, a(n) = F_n(4) + F_(n+1)(4), where F_n(x) is a Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i)*x^(n-2*i-1). - Vladimir Shevelev, Apr 13 2012
a(n) = A001076(n+1) - 3*A001076(n). - R. J. Mathar, Jul 12 2012
From Gary Detlefs and Wolfdieter Lang, Aug 20 2012: (Start)
a(n) = (5*F(n)^3 + 5*F(n-1)^3 + 3*(-1)^n*F(n-2))/2,
a(n) = (F(n+1)^3 + 2*F(n)^3 - F(n-2)^3)/2, n >= 0, with F(-1) = 1 and F(-2) = -1. Second line from first one with 3*(-1)^n* F(n-2) = F(n-1)^3 - 4*F(n-2)^3 - F(n-3)^3 (in Koshy's book, p. 89, 32. (with a - sign) and 33. For the Koshy reference see A000045) and the F^3 recurrence (see row n=4 of A055870, or Koshy p. 87, 1.). First line from the preceding R. J. Mathar formula with F(3*n) = 5*F(n)^3 + 3*(-1)^n*F(n) (Koshy p. 89, 46.) and the above mentioned formula, Koshy's 32. and 33., with n -> n+2 in order to eliminate F(n+1)^3. (End)
For n > 0, a(n) = L(n-1)*L(n)*F(n) + F(n+1)*(-1)^n with L(n)=A000032(n). - J. M. Bergot, Dec 10 2015
For n > 1, a(n)^2 is the denominator of continued fraction [4,4,...,4, 6, 4,4,...4], which has n-1 4's before, and n-1 4's after, the middle 6. - Greg Dresden, Sep 18 2019
From Gary Detlefs and Wolfdieter Lang, Mar 06 2023: (Start)
a(n) = A001076(n) + A001076(n-1), with A001076(-1) = 1. See the R. J. Mathar formula above.
a(n+1) = i^n*(S(n-1,-4*i) - i*S(n-2,-4*i)), for n >= 0, with i = sqrt(-1), and the Chebyshev S-polynomials (see A049310) with S(n, -1) = 0. From the simplified Fibonacci trisection formula for {F(3*n+2)}_{n>=0}. (End)
a(n) = Sum_{k=0..n} A046854(n-1,k)*4^k. - R. J. Mathar, Feb 10 2024
E.g.f.: exp(2*x)*(5*cosh(sqrt(5)*x) - sqrt(5)*sinh(sqrt(5)*x))/5. - Stefano Spezia, Jun 03 2024

A006012 a(0) = 1, a(1) = 2, a(n) = 4a(n-1) - 2a(n-2), n >= 2.

Original entry on oeis.org

1, 2, 6, 20, 68, 232, 792, 2704, 9232, 31520, 107616, 367424, 1254464, 4283008, 14623104, 49926400, 170459392, 581984768, 1987020288, 6784111616, 23162405888, 79081400320, 270000789504, 921840357376, 3147359850496

Offset: 0

N. J. A. Sloane

Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 4, s(2n) = 4. - Herbert Kociemba, Jun 12 2004
a(n-1) counts permutations pi on [n] for which the pairs {i, pi(i)} with i < pi(i), considered as closed intervals [i+1,pi(i)], do not overlap; equivalently, for each i in [n] there is at most one j <= i with pi(j) > i. Counting these permutations by the position of n yields the recurrence relation. - David Callan, Sep 02 2003
a(n) is the sum of (n+1)-th row terms of triangle A140070. - Gary W. Adamson, May 04 2008
The binomial transform is in A083878, the Catalan transform in A084868. - R. J. Mathar, Nov 23 2008
Equals row sums of triangle A152252. - Gary W. Adamson, Nov 30 2008
Counts all paths of length (2*n), n >= 0, starting at the initial node on the path graph P_7, see the second Maple program. - Johannes W. Meijer, May 29 2010
From L. Edson Jeffery, Apr 04 2011: (Start)
Let U_1 and U_3 be the unit-primitive matrices (see [Jeffery])
U_1 = U_(8,1) = [(0,1,0,0); (1,0,1,0); (0,1,0,1); (0,0,2,0)] and
U_3 = U_(8,3) = [(0,0,0,1); (0,0,2,0); (0,2,0,1); (2,0,2,0)]. Then a(n) = (1/4) * Trace(U_1^(2*n)) = (1/2^(n+2)) * Trace(U_3^(2*n)). (See also A084130, A001333.) (End)
Pisano period lengths: 1, 1, 8, 1, 24, 8, 6, 1, 24, 24, 120, 8, 168, 6, 24, 1, 8, 24, 360, 24, ... - R. J. Mathar, Aug 10 2012
a(n) is the first superdiagonal of array A228405. - Richard R. Forberg, Sep 02 2013
Conjecture: With offset 1, a(n) is the number of permutations on [n] with no subsequence abcd such that (i) bc are adjacent in position and (ii) max(a,c) < min(b,d). For example, the 4 permutations of [4] not counted by a(4) are 1324, 1423, 2314, 2413. - David Callan, Aug 27 2014
The conjecture of David Callan above is correct - with offset 1, a(n) is the number of permutations on [n] with no subsequence abcd such that (i) bc are adjacent in position and (ii) max(a,c) < min(b,d). - Yonah Biers-Ariel, Jun 27 2017
From Gary W. Adamson, Jul 22 2016: (Start)
A production matrix for the sequence is M =
  1, 1, 0, 0, 0, 0, ...
  1, 0, 3, 0, 0, 0, ...
  1, 0, 0, 3, 0, 0, ...
  1, 0, 0, 0, 3, 0, ...
  1, 0, 0, 0, 0, 3, ...
  ...
Take powers of M, extracting the upper left terms; getting the sequence starting: (1, 1, 2, 6, 20, 68, ...). (End)
From Gary W. Adamson, Jul 24 2016: (Start)
The sequence is the INVERT transform of the powers of 3 prefaced with a "1": (1, 1, 3, 9, 27, ...) and is N=3 in an infinite of analogous sequences starting:
   N=1 (A000079):  1, 2, 4,  8,  16,   32, ...
   N=2 (A001519):  1, 2, 5, 13,  34,   89, ...
   N=3 (A006012):  1, 2, 6, 20,  68,  232, ...
   N=4 (A052961):  1, 2, 7, 29, 124,  533, ...
   N=5 (A154626):  1, 2, 8, 40, 208, 1088, ...
   N=6:            1, 2, 9, 53, 326, 2017, ...
   ... (End)
Number of permutations of length n > 0 avoiding the partially ordered pattern (POP) {1>2, 1>3, 4>2, 4>3} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first and fourth elements are larger than the second and third elements. - Sergey Kitaev, Dec 08 2020
a(n-1) is the number of permutations of [n] that can be obtained by placing n points on an X-shape (two crossing lines with slopes 1 and -1), labeling them 1,2,...,n by increasing y-coordinate, and then reading the labels by increasing x-coordinate. - Sergi Elizalde, Sep 27 2021
Consider a stack of pancakes of height n, where the only allowed operation is reversing the top portion of the stack. First, perform a series of reversals of decreasing sizes, followed by a series of reversals of increasing sizes. The number of distinct permutations of the initial stack that can be reached through these operations is a(n). - Thomas Baruchel, May 12 2025
Number of permutations of [n] that are correctly sorted after performing one left-to-right pass and one right-to-left pass of the cocktail sort. - Thomas Baruchel, May 16 2025

D. H. Greene and D. E. Knuth, Mathematics for the Analysis of Algorithms. Birkhäuser, Boston, 3rd edition, 1990, p. 86.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.8 Answer to Exer. 8.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Andrei Asinowski and Toufik Mansour, Separable d-Permutations and Guillotine Partitions, arXiv 0803.3414 [math.CO], 2008. Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010; Abstract
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 155
George Balla, Ghislain Fourier, and Kunda Kambaso, PBW filtration and monomial bases for Demazure modules in types A and C, arXiv:2205.01747 [math.RT], 2022.
M. Barnabei, F. Bonetti, and M. Silimbani, Two permutation classes related to the Bubble Sort operator, Electronic Journal of Combinatorics 19(3) (2012), #P25. - From _N. J. A. Sloane_, Dec 25 2012
Yonah Biers-Ariel, A New Quantity Counted by OEIS Sequence A006012, arXiv:1706.07064 [math.CO], 2017.
Yonah Biers-Ariel, The Number of Permutations Avoiding a Set of Generalized Permutation Patterns, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.3.
Rocco Chirivì, Xin Fang, and Ghislain Fourier, Degenerate Schubert varieties in type A, Transformation Groups (2020).
CombOS - Combinatorial Object Server, Generate pattern-avoiding permutations
Sergi Elizalde, The X-class and almost-increasing permutations, arXiv:0710.5168 [math:CO], 2007. Ann. Comb. 15 (2011), 51-68.
S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Luca Ferrari, Enhancing the connections between patterns in permutations and forbidden configurations in restricted elections, arXiv:1906.10553 [math.CO], 2019.
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
L. E. Jeffery, Unit-primitive matrices
Donghyun Kim and Lauren Williams, Schubert polynomials, the inhomogeneous TASEP, and evil-avoiding permutations, arXiv:2106.13378 [math.CO], 2021.
Sergey Kitaev and Artem Pyatkin, On permutations avoiding partially ordered patterns defined by bipartite graphs, arXiv:2204.08936 [math.CO], 2022.
Joshua Marsh and Nathan Williams, Nesting Nonpartitions, J. Int. Seq., Vol. 25 (2022), Article 22.8.8.
Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Joris Nieuwveld, Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.
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
J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
Markus Saers, Dekai Wu, and Chris Quirk, On the Expressivity of Linear Transductions.
Yi-dong Sun and Cang-zhi Jia, Counting Dyck paths with strictly increasing peak sequences, J. Math. Res. Expos. 27 (2) (2007) 253, Theorem 3.11.
Index entries for linear recurrences with constant coefficients, signature (4,-2).

Cf. A000079, A000129, A001333, A001519, A002203, A003480, A007052, A007070, A024175, A030436, A052961, A056236, A083978, A084130, A084868, A094803, A098158, A140070, A147703, A152252, A154626, A201730, A228405, A265185.

a006012 n = a006012_list !! n
a006012_list = 1 : 2 : zipWith (-) (tail $ map (* 4) a006012_list)
(map (* 2) a006012_list)
-- Reinhard Zumkeller, Oct 03 2011

[n le 2 select n else 4*Self(n-1)- 2*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Apr 05 2011

A006012:=-(-1+2*z)/(1-4*z+2*z**2); # Simon Plouffe in his 1992 dissertation
with(GraphTheory): G:=PathGraph(7): A:= AdjacencyMatrix(G): nmax:=24; n2:=2*nmax: for n from 0 to n2 do B(n):=A^n; a(n):=add(B(n)[1,k],k=1..7); od: seq(a(2*n),n=0..nmax); # Johannes W. Meijer, May 29 2010

LinearRecurrence[{4,-2},{1,2},50] (* or *) With[{c=Sqrt[2]}, Simplify[ Table[((2+c)^n+(3+2c)(2-c)^n)/(2(2+c)),{n,50}]]] (* Harvey P. Dale, Aug 29 2011 *)

{a(n) = real(((2 + quadgen(8))^n))}; /* Michael Somos, Feb 12 2004 */

{a(n) = if( n<0, 2^n, 1) * polsym(x^2 - 4*x + 2, abs(n))[abs(n)+1] / 2}; /* Michael Somos, Feb 12 2004 */

Vec((1-2*x)/(1-4*x+2*x^2) + O(x^100)) \\ Altug Alkan, Dec 05 2015

l = [1, 2]
for n in range(2, 101): l.append(4 * l[n - 1] - 2 * l[n - 2])
print(l)  # Indranil Ghosh, Jul 02 2017

A006012=BinaryRecurrenceSequence(4,-2,1,2)
print([A006012(n) for n in range(41)]) # G. C. Greubel, Aug 27 2025

G.f.: (1-2*x)/(1 - 4*x + 2*x^2).
a(n) = 2*A007052(n-1) = A056236(n)/2.
Limit_{n -> oo} a(n)/a(n-1) = 2 + sqrt(2). - Zak Seidov, Oct 12 2002
From Paul Barry, May 08 2003: (Start)
Binomial transform of A001333.
E.g.f.: exp(2*x)*cosh(sqrt(2)*x). (End)
a(n) = Sum_{k=0..floor(n/2)} binomial(n, 2k)*2^(n-k) = Sum_{k=0..n} binomial(n, k)*2^(n-k/2)(1+(-1)^k)/2. - Paul Barry, Nov 22 2003 (typo corrected by Manfred Scheucher, Jan 17 2023)
a(n) = ((2+sqrt(2))^n + (2-sqrt(2))^n)/2.
a(n) = [M^n]{2,2}, where M is the 3 X 3 matrix: M = [1,1,1;1,2,1;1,1,1]. - _Simone Severini, Jun 11 2006
a(n) = Sum_{k=0..n} 2^k*A098158(n,k). - Philippe Deléham, Dec 04 2006
a(n) = A007070(n) - 2*A007070(n-1). - R. J. Mathar, Nov 16 2007
a(n) = Sum_{k=0..n} A147703(n,k). - Philippe Deléham, Nov 29 2008
a(n) = Sum_{k=0..n} A201730(n,k). - Philippe Deléham, Dec 05 2011
G.f.: G(0) where G(k)= 1 + 2*x/((1-2*x) - 2*x*(1-2*x)/(2*x + (1-2*x)*2/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Dec 10 2012
G.f.: G(0)*(1-2*x)/2, where G(k) = 1 + 1/(1 - 2*x*(4*k+2-x)/( 2*x*(4*k+4-x) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 27 2014
a(-n) = a(n) / 2^n for all n in Z. - Michael Somos, Aug 24 2014
a(n) = A265185(n) / 4, connecting this sequence to the simple Lie algebra B_4. - Tom Copeland, Dec 04 2015
From G. C. Greubel, Aug 27 2025: (Start)
a(n) = 2^((n-2)/2)*( (n+1 mod 2)*A002203(n) + 2*sqrt(2)*(n mod 2)*A000129(n) ).
a(n) = 2^(n/2)*ChebyshevT(n, sqrt(2)). (End)

A180028 Eight white queens and one red queen on a 3 X 3 chessboard. G.f.: (1 + 3x)/(1 - 6x - 3*x^2).

Original entry on oeis.org

1, 9, 57, 369, 2385, 15417, 99657, 644193, 4164129, 26917353, 173996505, 1124731089, 7270376049, 46996449561, 303789825513, 1963728301761, 12693739287105, 82053620627913, 530402941628793, 3428578511656497

Offset: 0

Johannes W. Meijer, Aug 09 2010; edited Jun 21 2013

The a(n) represent the number of n-move routes of a fairy chess piece starting in the center square (m = 5) on a 3 X 3 chessboard. This fairy chess piece behaves like a white queen on the eight side and corner squares but on the central square the queen explodes with fury and turns into a red queen.
On a 3 X 3 chessboard there are 2^9 = 512 ways to explode with fury on the center square (off the center square the piece behaves like a normal queen). The red queen is represented by the A[5] vector in the fifth row of the adjacency matrix A, see the Maple program and A180140. For the center square the 512 red queens lead to 17 red queen sequences, see the overview of red queen sequences and the crossreferences.
The sequence above corresponds to just one red queen vector, i.e., A[5] = [111 111 111] vector. The other squares lead for this vector to A090018.
This sequence belongs to a family of sequences with g.f. (1+k*x)/(1 - 6*x - k*x^2). The members of this family that are red queen sequences are A180028 (k=3; this sequence), A180029 (k=2), A015451 (k=1), A000400 (k=0), A001653 (k=-1), A180034 (k=-2), A084120 (k=-3), A154626 (k=-4) and A000012 (k=-5). Other members of this family are A123362 (k=5), 6*A030192(k=-6).
Inverse binomial transform of A107903.

Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Johannes W. Meijer, The red queen sequences.
Wikipedia, Alice in Wonderland (2010 film).
Index entries for linear recurrences with constant coefficients, signature (6, 3).

Cf. A180140 (berserker sequences)
Cf. A180032 (Corner and side squares).
Cf. Red queen sequences center square [decimal value A[5]]: A180028 [511], A180029 [255], A180031 [495], A015451 [127], A152240 [239], A000400 [63], A057088 [47], A001653 [31], A122690 [15], A180034 [23], A180036 [7], A084120 [19], A180038 [3], A154626 [17], A015449 [1], A000012 [16], A000007 [0].

I:=[1,9]; [n le 2 select I[n] else 6*Self(n-1)+3*Self(n-2): n in [1..20]]; // Vincenzo Librandi, Nov 15 2011

nmax:=19; m:=5; A[1]:=[0,1,1,1,1,0,1,0,1]: A[2]:=[1,0,1,1,1,1,0,1,0]: A[3]:=[1,1,0,0,1,1,1,0,1]: A[4]:=[1,1,0,0,1,1,1,1,0]: A[5]:=[1,1,1,1,1,1,1,1,1]: A[6]:=[0,1,1,1,1,0,0,1,1]: A[7]:=[1,0,1,1,1,0,0,1,1]: A[8]:=[0,1,0,1,1,1,1,0,1]: A[9]:=[1,0,1,0,1,1,1,1,0]: A:=Matrix([A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8], A[9]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax);

LinearRecurrence[{6,3},{1,9},50] (* Vincenzo Librandi, Nov 15 2011 *)

G.f.: (1+3*x)/(1 - 6*x - 3*x^2).
a(n) = 6*a(n-1) + 3*a(n-2) with a(0) = 1 and a(1) = 9.
a(n) = ((1-A)*A^(-n-1) + (1-B)*B^(-n-1))/4 with A=(-1+2*sqrt(3)/3) and B=(-1-2*sqrt(3)/3).
Lim_{k->infinity} a(n+k)/a(k) = (-1)^(n-1)*A108411(n+1)/(A041017(n-1)*sqrt(12) - A041016(n-1)) for n >= 1.

A080877 a(n)a(n+3) - a(n+1)a(n+2) = 2^n, given a(0)=1, a(1)=1, a(2)=2.

Original entry on oeis.org

1, 1, 2, 3, 8, 14, 40, 72, 208, 376, 1088, 1968, 5696, 10304, 29824, 53952, 156160, 282496, 817664, 1479168, 4281344, 7745024, 22417408, 40553472, 117379072, 212340736, 614604800, 1111830528, 3218112512, 5821620224, 16850255872

Offset: 0

Paul D. Hanna, Feb 22 2003

nonn

Index entries for linear recurrences with constant coefficients, signature (0, 6, 0, -4).

Cf. A080876, A080878, A080879, A080880, A080881, A080882.

Cf. A154626, A098648 (bisections). [From R. J. Mathar, Oct 26 2009]

LinearRecurrence[{0,6,0,-4},{1,1,2,3},50] (* or *) CoefficientList[ Series[ (-3x^3-4x^2+x+1)/(4x^4-6x^2+1),{x,0,50}],x] (* Harvey P. Dale, May 02 2011 *)

G.f.: (-3*x^3 - 4*x^2 + x + 1)/(4*x^4 - 6*x^2 + 1)
a(n + 4) = 6*a(n + 2) - 4*a(n) [From Richard Choulet, Dec 06 2008]
a(n) = ( - 1/20*5^(1/2) + 1/16*5^(1/2)*2^(1/2) - 1/16*2^(1/2) + 1/4)*(sqrt(3 + sqrt(5)))^n + (1/20*5^(1/2) + 1/16*5^(1/2)*2^(1/2) + 1/16*2^(1/2) + 1/4)*(sqrt(3 - sqrt(5)))^n + ( - 1/20*5^(1/2) - 1/16*5^(1/2)*2^(1/2) + 1/16*2^(1/2) + 1/4)*( - (sqrt(3 + sqrt(5))))^n + (1/20*5^(1/2) - 1/16*5^(1/2)*2^(1/2) - 1/16*2^(1/2) + 1/4)*( - (sqrt(3 - sqrt(5))))^n [From Richard Choulet, Dec 07 2008]

A208343 Triangle of coefficients of polynomials v(n,x) jointly generated with A208342; see the Formula section.

Original entry on oeis.org

1, 0, 2, 0, 1, 3, 0, 1, 2, 5, 0, 1, 2, 5, 8, 0, 1, 2, 6, 10, 13, 0, 1, 2, 7, 13, 20, 21, 0, 1, 2, 8, 16, 29, 38, 34, 0, 1, 2, 9, 19, 39, 60, 71, 55, 0, 1, 2, 10, 22, 50, 86, 122, 130, 89, 0, 1, 2, 11, 25, 62, 116, 187, 241, 235, 144, 0, 1, 2, 12, 28, 75, 150, 267, 392, 468

Offset: 1

Clark Kimberling, Feb 25 2012

u(n,n) = A000045(n+1) (Fibonacci numbers).
n-th row sum:  2^(n-1)
As triangle T(n,k) with 0 <= k <= n, it is (0, 1/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (2, -1/2, -1/2, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 26 2012

			First five rows:
  1;
  0, 2;
  0, 1, 3;
  0, 1, 2, 5;
  0, 1, 2, 5, 8;
First five polynomials v(n,x):
  1
     2x
      x + 3x^2
      x + 2x^2 + 5x^3
      x + 2x^2 + 5x^3 + 8x^4.

Cf. A208343.

Cf. A084938, A000045, A000079.

u[1, x_] := 1; v[1, x_] := 1; z = 13;
u[n_, x_] := u[n - 1, x] + x*v[n - 1, x];
v[n_, x_] := x*u[n - 1, x] + x*v[n - 1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]  (* A208342 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]  (* A208343 *)

u(n,x) = u(n-1,x) + x*v(n-1,x),
v(n,x) = x*u(n-1,x) + x*v(n-1,x),
where u(1,x)=1, v(1,x)=1.
From Philippe Deléham, Feb 26 2012: (Start)
As triangle T(n,k) with 0 <= k <= n:
T(n,k) = T(n-1,k) + T(n-1,k-1) + T(n-2,k-2) - T(n-2,k-1), T(0,0) = 1, T(1,0) = 0, T(1,1) = 2, T(n,k) = 0 if k > n or if k < 0.
G.f.: (1-(1-y)*x)/(1-(1+y)*x+y*(1-y)*x^2).
Sum_{k=0..n} T(n,k)*x^k = (-1)*A091003(n+1), A152166(n), A000007(n), A000079(n), A055099(n), A152224(n) for x = -2, -1, 0, 1, 2, 3 respectively.
Sum_{k=0..n} T(n,k)*x^(n-k) = A087205(n), A140165(n+1), A016116(n+1), A000045(n+2), A000079(n), A122367(n), A006012(n), A052961(n), A154626(n) for x = -3, -2, -1, 0, 1, 2, 3, 4 respectively. (End)
T(n,k) = A208748(n,k)/2^k. - Philippe Deléham, Mar 05 2012

cp's OEIS Frontend

A192232 Constant term of the reduction of n-th Fibonacci polynomial by x^2 -> x+1. (See Comments.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

Formula

A006012 a(0) = 1, a(1) = 2, a(n) = 4*a(n-1) - 2*a(n-2), n >= 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

SageMath

Formula

A180028 Eight white queens and one red queen on a 3 X 3 chessboard. G.f.: (1 + 3*x)/(1 - 6*x - 3*x^2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A080877 a(n)*a(n+3) - a(n+1)*a(n+2) = 2^n, given a(0)=1, a(1)=1, a(2)=2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A208343 Triangle of coefficients of polynomials v(n,x) jointly generated with A208342; see the Formula section.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A202868 Array: row n shows the coefficients of the characteristic polynomial of the n-th principal submatrix of the symmetric matrix A115216; by antidiagonals.

A006012 a(0) = 1, a(1) = 2, a(n) = 4a(n-1) - 2a(n-2), n >= 2.

A180028 Eight white queens and one red queen on a 3 X 3 chessboard. G.f.: (1 + 3x)/(1 - 6x - 3*x^2).

A080877 a(n)a(n+3) - a(n+1)a(n+2) = 2^n, given a(0)=1, a(1)=1, a(2)=2.