cp's OEIS Frontend

G.f. for row polynomials S(n,x) (signed triangle): 1/(1-x*z+z^2). Unsigned triangle |a(n,m)| has Fibonacci polynomials F(n+1,x) as row polynomials with g.f. 1/(1-x*z-z^2). |a(n,m)| triangle has rows of Pascal's triangle A007318 in the even-numbered diagonals (odd-numbered ones have only 0's).

Row sums (unsigned triangle) A000045(n+1) (Fibonacci). Row sums (signed triangle) S(n,1) sequence = periodic(1,1,0,-1,-1,0) = A010892.

Alternating row sums A049347(n) = S(n,-1) = periodic(1,-1,0). - Wolfdieter Lang, Nov 04 2011

S(n,x) is the characteristic polynomial of the adjacency matrix of the n-path. - Michael Somos, Jun 24 2002

S(n,x) is also the matching polynomial of the n-path. - Eric W. Weisstein, Apr 10 2017

|T(n,k)| = number of compositions of n+1 into k+1 odd parts. Example: |T(7,3)| = 10 because we have (1,1,3,3), (1,3,1,3), (1,3,3,1), (3,1,1,3), (3,1,3,1), (3,3,1,1), (1,1,1,5), (1,1,5,1), (1,5,1,1) and (5,1,1,1). - Emeric Deutsch, Apr 09 2005

S(n,x)= R(n,x) + S(n-2,x), n >= 2, S(-1,x)=0, S(0,x)=1, R(n,x):=2*T(n,x/2) = Sum_{m=0..n} A127672(n,m)*x^m (monic integer Chebyshev T-Polynomials). This is the rewritten so-called trace of the transfer matrix formula for the T-polynomials. - Wolfdieter Lang, Dec 02 2010

In a regular N-gon inscribed in a unit circle, the side length is d(N,1) = 2*sin(Pi/N). The length ratio R(N,k):=d(N,k)/d(N,1) for the (k-1)-th diagonal, with k from {2,3,...,floor(N/2)}, N >= 4, equals S(k-1,x) = sin(k*Pi/N)/sin(Pi/N) with x=rho(N):=R(N,2) = 2*cos(Pi/N). Example: N=7 (heptagon), rho=R(7,2), sigma:=R(N,3) = S(2,rho) = rho^2 - 1. Motivated by the quoted paper by P. Steinbach. - Wolfdieter Lang, Dec 02 2010

From Wolfdieter Lang, Jul 12 2011: (Start)

In q- or basic analysis, q-numbers are [n]_q := S(n-1,q+1/q) = (q^n-(1/q)^n)/(q-1/q), with the row polynomials S(n,x), n >= 0.

The zeros of the row polynomials S(n-1,x) are (from those of Chebyshev U-polynomials):

x(n-1;k) = +- t(k,rho(n)), k = 1..ceiling((n-1)/2), n >= 2, with t(n,x) the row polynomials of A127672 and rho(n):= 2*cos(Pi/n). The simple vanishing zero for even n appears here as +0 and -0.

Factorization of the row polynomials S(n-1,x), x >= 1, in terms of the minimal polynomials of cos(2 Pi/2), called Psi(n,x), with coefficients given by A181875/A181876:

S(n-1,x) = (2^(n-1))*Product_{n>=1}(Psi(d,x/2), 2 < d | 2n).

(From the rewritten eq. (3) of the Watkins and Zeitlin reference, given under A181872.) [See the W. Lang ArXiv link, Proposition 9, eq. (62). - Wolfdieter Lang, Apr 14 2018]

(End)

The discriminants of the S(n,x) polynomials are found in A127670. - Wolfdieter Lang, Aug 03 2011

This is an example for a subclass of Riordan convolution arrays (lower triangular matrices) called Bell arrays. See the L. W. Shapiro et al. reference under A007318. If a Riordan array is named (G(z),F(z)) with F(z)=z*Fhat(z), the o.g.f. for the row polynomials is G(z)/(1-x*z*Fhat(z)), and it becomes a Bell array if G(z)=Fhat(z). For the present Bell type triangle G(z)=1/(1+z^2) (see the o.g.f. comment above). This leads to the o.g.f. for the column no. k, k >= 0, x^k/(1+x^2)^(k+1) (see the formula section), the one for the row sums and for the alternating row sums (see comments above). The Riordan (Bell) A- and Z-sequences (defined in a W. Lang link under A006232, with references) have o.g.f.s 1-x*c(x^2) and -x*c(x^2), with the o.g.f. of the Catalan numbers A000108. Together they lead to a recurrence given in the formula section. - Wolfdieter Lang, Nov 04 2011

The determinant of the N x N matrix S(N,[x[1], ..., x[N]]) with elements S(m-1,x[n]), for n, m = 1, 2, ..., N, and for any x[n], is identical with the determinant of V(N,[x[1], ..., x[N]]) with elements x[n]^(m-1) (a Vandermondian, which equals Product_{1 <= i < j<= N} (x[j] - x[i])). This is a special instance of a theorem valid for any N >= 1 and any monic polynomial system p(m,x), m>=0, with p(0,x) = 1. For this theorem see the Vein-Dale reference, p. 59. Thanks to L. Edson Jeffery for an email asking for a proof of the non-singularity of the matrix S(N,[x[1], ...., x[N]]) if and only if the x[j], j = 1..N, are pairwise distinct. - Wolfdieter Lang, Aug 26 2013

These S polynomials also appear in the context of modular forms. The rescaled Hecke operator T*n = n^((1-k)/2)*T_n acting on modular forms of weight k satisfies T*(p^n) = S(n, T*p), for each prime p and positive integer n. See the Koecher-Krieg reference, p. 223. - _Wolfdieter Lang, Jan 22 2016

For a shifted o.g.f. (mod signs), its compositional inverse, and connections to Motzkin and Fibonacci polynomials, non-crossing partitions and other combinatorial structures, see A097610. - Tom Copeland, Jan 23 2016

From M. Sinan Kul, Jan 30 2016; edited by Wolfdieter Lang, Jan 31 2016 and Feb 01 2016: (Start)

Solutions of the Diophantine equation u^2 + v^2 - k*u*v = 1 for integer k given by (u(k,n), v(k,n)) = (S(n,k), S(n-1,k)) because of the Cassini-Simson identity: S(n,x)^2 - S(n+1,x)*S(n-1, x) = 1, after use of the S-recurrence. Note that S(-n, x) = -S(-n-2, x), n >= 1, and the periodicity of some S(n, k) sequences.

Hence another way to obtain the row polynomials would be to take powers of the matrix [x, -1; 1,0]: S(n, x) = (([x, -1; 1, 0])^n)[1,1], n >= 0.

See also a Feb 01 2016 comment on A115139 for a well-known S(n, x) sum formula.

Then we have with the present T triangle

A039834(n) = -i^(n+1)*T(n-1, k) where i is the imaginary unit and n >= 0.

A051286(n) = Sum_{i=0..n} T(n,i)^2 (see the Philippe Deléham, Nov 21 2005 formula),

A181545(n) = Sum_{i=0..n+1} abs(T(n,i)^3),

A181546(n) = Sum_{i=0..n+1} T(n,i)^4,

A181547(n) = Sum_{i=0..n+1} abs(T(n,i)^5).

S(n, 0) = A056594(n), and for k = 1..10 the sequences S(n-1, k) with offset n = 0 are A128834, A001477, A001906, A001353, A004254, A001109, A004187, A001090, A018913, A004189.

(End)

For more on the Diophantine equation presented by Kul, see the Ismail paper. - Tom Copeland, Jan 31 2016

The o.g.f. for the Legendre polynomials L(n,x) is 1 / sqrt(1- 2x*z + z^2), and squaring it gives the o.g.f. of U(n,x), A053117, so Sum_{k=0..n} L(k,x/2) L(n-k,x/2) = S(n,x). This gives S(n,x) = L(n/2,x/2)^2 + 2*Sum_{k=0..n/2-1} L(k,x/2) L(n-k,x/2) for n even and S(n,x) = 2*Sum_{k=0..(n-1)/2} L(k,x/2) L(n-k,x/2) for odd n. For a connection to elliptic curves and modular forms, see A053117. For the normalized Legendre polynomials, see A100258. For other properties and relations to other polynomials, see Allouche et al. - Tom Copeland, Feb 04 2016

LG(x,h1,h2) = -log(1 - h1*x + h2*x^2) = Sum_{n>0} F(n,-h1,h2,0,..,0) x^n/n is a log series generator of the bivariate row polynomials of A127672 with A127672(0,0) = 0 and where F(n,b1,b2,..,bn) are the Faber polynomials of A263916. Exp(LG(x,h1,h2)) = 1 / (1 - h1*x + h2*x^2 ) is the o.g.f. of the bivariate row polynomials of this entry. - Tom Copeland, Feb 15 2016 (Instances of the bivariate o.g.f. for this entry are on pp. 5 and 18 of Sunada. - Tom Copeland, Jan 18 2021)

For distinct odd primes p and q the Legendre symbol can be written as Legendre(q,p) = Product_{k=1..P} S(q-1, 2*cos(2*Pi*k/p)), with P = (p-1)/2. See the Lemmermeyer reference, eq. (8.1) on p. 236. Using the zeros of S(q-1, x) (see above) one has S(q-1, x) = Product_{l=1..Q} (x^2 - (2*cos(Pi*l/q))^2), with Q = (q-1)/2. Thus S(q-1, 2*cos(2*Pi*k/p)) = ((-4)^Q)*Product_{l=1..Q} (sin^2(2*Pi*k/p) - sin^2(Pi*l/q)) = ((-4)^Q)*Product_{m=1..Q} (sin^2(2*Pi*k/p) - sin^2(2*Pi*m/q)). For the proof of the last equality see a W. Lang comment on the triangle A057059 for n = Q and an obvious function f. This leads to Eisenstein's proof of the quadratic reciprocity law Legendre(q,p) = ((-1)^(P*Q)) * Legendre(p,q), See the Lemmermeyer reference, pp. 236-237. - Wolfdieter Lang, Aug 28 2016

For connections to generalized Fibonacci polynomials, compare their generating function on p. 5 of the Amdeberhan et al. link with the o.g.f. given above for the bivariate row polynomials of this entry. - Tom Copeland, Jan 08 2017

The formula for Ramanujan's tau function (see A000594) for prime powers is tau(p^k) = p^(11*k/2)*S(k, p^(-11/2)*tau(p)) for k >= 1, and p = A000040(n), n >= 1. See the Hardy reference, p. 164, eqs. (10.3.4) and (10.3.6) rewritten in terms of S. - Wolfdieter Lang, Jan 27 2017

From Wolfdieter Lang, May 08 2017: (Start)

The number of zeros Z(n) of the S(n, x) polynomials in the open interval (-1,+1) is 2*b(n) for even n >= 0 and 1 + 2*b(n) for odd n >= 1, where b(n) = floor(n/2) - floor((n+1)/3). This b(n) is the number of integers k in the interval (n+1)/3 < k <= floor(n/2). See a comment on the zeros of S(n, x) above, and b(n) = A008615(n-2), n >= 0. The numbers Z(n) have been proposed (with a conjecture related to A008611) by Michel Lagneau, as the number of zeros of Fibonacci polynomials on the imaginary axis (-I,+I), with I=sqrt(-1). They are Z(n) = A008611(n-1), n >= 0, with A008611(-1) = 0. Also Z(n) = A194960(n-4), n >= 0. Proof using the A008611 version. A194960 follows from this.

In general the number of zeros Z(a;n) of S(n, x) for n >= 0 in the open interval (-a,+a) for a from the interval (0,2) (x >= 2 never has zeros, and a=0 is trivial: Z(0;n) = 0) is with b(a;n) = floor(n//2) - floor((n+1)*arccos(a/2)/Pi), as above Z(a;n) = 2*b(a;n) for even n >= 0 and 1 + 2*b(a;n) for odd n >= 1. For the closed interval [-a,+a] Z(0;n) = 1 and for a from (0,1) one uses for Z(a;n) the values b(a;n) = floor(n/2) - ceiling((n+1)*arccos(a/2)/Pi) + 1. (End)

The Riordan row polynomials S(n, x) (Chebyshev S) belong to the Boas-Buck class (see a comment and references in A046521), hence they satisfy the Boas-Buck identity: (E_x - n*1)*S(n, x) = (E_x + 1)*Sum_{p=0..n-1} (1 - (-1)^p)*(-1)^((p+1)/2)*S(n-1-p, x), for n >= 0, where E_x = x*d/dx (Euler operator). For the triangle T(n, k) this entails a recurrence for the sequence of column k, given in the formula section. - Wolfdieter Lang, Aug 11 2017

The e.g.f. E(x,t) := Sum_{n>=0} (t^n/n!)*S(n,x) for the row polynomials is obtained via inverse Laplace transformation from the above given o.g.f. as E(x,t) = ((1/xm)*exp(t/xm) - (1/xp)*exp(t/xp) )/(xp - xm) with xp = (x + sqrt(x^2-4))/2 and xm = (x - sqrt(x^2-4))/2. - Wolfdieter Lang, Nov 08 2017

From Wolfdieter Lang, Apr 12 2018: (Start)

Factorization of row polynomials S(n, x), for n >= 1, in terms of C polynomials (not Chebyshev C) with coefficients given in A187360. This is obtained from the factorization into Psi polynomials (see the Jul 12 2011 comment above) but written in terms of minimal polynomials of 2*cos(2*Pi/n) with coefficients in A232624:

S(2*k, x) = Product_{2 <= d | (2*k+1)} C(d, x)*(-1)^deg(d)*C(d, -x), with deg(d) = A055034(d) the degree of C(d, x).

S(2*k+1, x) = Product_{2 <= d | 2*(k+1)} C(d, x) * Product_{3 <= 2*d + 1 | (k+1)} (-1)^(deg(2*d+1))*C(2*d+1, -x).

Note that (-1)^(deg(2*d+1))*C(2*d+1, -x)*C(2*d+1, x) pairs always appear.

The number of C factors of S(2*k, x), for k >= 0, is 2*(tau(2*k+1) - 1) = 2*(A099774(k+1) - 1) = 2*A095374(k), and for S(2*k+1, x), for k >= 0, it is tau(2*(k+1)) + tau_{odd}(k+1) - 2 = A302707(k), with tau(2*k+1) = A099774(k+1), tau(n) = A000005 and tau(2*(k+1)) = A099777(k+1).

For the reverse problem, the factorization of C polynomials into S polynomials, see A255237. (End)

The S polynomials with general initial conditions S(a,b;n,x) = x*S(a,b;n-1,x) - S(a,b;n-2,x), for n >= 1, with S(a,b;-1,x) = a and S(a,b;0,x) = b are S(a,b;n,x) = b*S(n, x) - a*S(n-1, x), for n >= -1. Recall that S(-2, x) = -1 and S(-1, x) = 0. The o.g.f. is G(a,b;z,x) = (b - a*z)/(1 - x*z + z^2). - Wolfdieter Lang, Oct 18 2019

Also the convolution triangle of A101455. - Peter Luschny, Oct 06 2022

From Wolfdieter Lang, Apr 26 2023: (Start)

Multi-section of S-polynomials: S(m*n+k, x) = S(m+k, x)*S(n-1, R(m, x)) - S(k, x)*S(n-2, R(m, x)), with R(n, x) = S(n, x) - S(n-2, x) (see A127672), S(-2, x) = -1, and S(-1, x) = 0, for n >= 0, m >= 1, and k = 0, 1, ..., m-1.

O.g.f. of {S(m*n+k, y)}_{n>=0}: G(m,k,y,x) = (S(k, y) - (S(k, y)*R(m, y) - S(m+k, y))*x)/(1 - R(m,y)*x + x^2).

See eqs. (40) and (49), with r = x or y and s =-1, of the G. Detlefs and W. Lang link at A034807. (End)

S(n, x) for complex n and complex x: S(n, x) = ((-i/2)/sqrt(1 - (x/2)^2))*(q(x/2)*exp(+n*log(q(x/2))) - (1/q(x/2))*exp(-n*log(q(x/2)))), with q(x) = x + sqrt(1 - x^2)*i. Here log(z) = |z| + Arg(z)*i, with Arg(z) from [-Pi,+Pi) (principal branch). This satisfies the recurrence relation for S because it is derived from the Binet - de Moivre formula for S. Examples: S(n/m, 0) = cos((n/m)*Pi/4), for n >= 0 and m >= 1. S(n*i, 0) = (1/2)*(1 + exp(n*Pi))*exp(-(n/2)*Pi), for n >= 0. S(1+i, 2+i) = 0.6397424847... + 1.0355669490...*i. Thanks to Roberto Alfano for asking a question leading to this formula. - Wolfdieter Lang, Jun 05 2023

Lim_{n->oo} S(n, x)/S(n-1, x) = r(x) = (x - sqrt(x^2 -4))/2, for |x| >= 2. For x = +-2, this limit is +-1. - Wolfdieter Lang, Nov 15 2023

Number of n-step non-selfintersecting paths starting at (0,0) with steps of types (1,0), (-1,0) or (0,1) [Stanley].

Number of n steps one-sided prudent walks with east, west and north steps. - Shanzhen Gao, Apr 26 2011

Number of ternary strings of length n-1 with subwords (0,2) and (2,0) not allowed. - Olivier Gérard, Aug 28 2012

Number of symmetric 2n X 2 or (2n-1) X 2 crossword puzzle grids: all white squares are edge connected; at least 1 white square on every edge of grid; 180-degree rotational symmetry. - Erich Friedman

a(n+1) is the number of ways to put molecules on a 2 X n ladder lattice so that the molecules do not touch each other.

In other words, a(n+1) is the number of independent vertex sets and vertex covers in the n-ladder graph P_2 X P_n. - Eric W. Weisstein, Apr 04 2017

Number of (n-1) X 2 binary arrays with a path of adjacent 1's from top row to bottom row, see A359576. - R. H. Hardin, Mar 16 2002

a(2*n+1) with b(2*n+1) := A000129(2*n+1), n >= 0, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = -1.

a(2*n) with b(2*n) := A000129(2*n), n >= 1, give all (positive integer) solutions to Pell equation a^2 - 2*b^2 = +1 (see Emerson reference).

Bisection: a(2*n) = T(n,3) = A001541(n), n >= 0 and a(2*n+1) = S(2*n,2*sqrt(2)) = A002315(n), n >= 0, with T(n,x), resp. S(n,x), Chebyshev's polynomials of the first, resp. second kind. See A053120, resp. A049310.

Binomial transform of A077957. - Paul Barry, Feb 25 2003

For n > 0, the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 4 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 2, s(n) = 2. - Herbert Kociemba, Jun 02 2004

For n > 1, a(n) corresponds to the longer side of a near right-angled isosceles triangle, one of the equal sides being A000129(n). - Lekraj Beedassy, Aug 06 2004

Exponents of terms in the series F(x,1), where F is determined by the equation F(x,y) = xy + F(x^2*y,x). - Jonathan Sondow, Dec 18 2004

Number of n-words from the alphabet A={0,1,2} which two neighbors differ by at most 1. - Fung Cheok Yin (cheokyin_restart(AT)yahoo.com.hk), Aug 30 2006

Consider the mapping f(a/b) = (a + 2b)/(a + b). Taking a = b = 1 to start with and carrying out this mapping repeatedly on each new (reduced) rational number gives the following sequence 1/1, 3/2, 7/5, 17/12, 41/29, ... converging to 2^(1/2). Sequence contains the numerators. - Amarnath Murthy, Mar 22 2003 [Amended by Paul E. Black (paul.black(AT)nist.gov), Dec 18 2006]

Odd-indexed prime numerators are prime RMS numbers (A140480) and also NSW primes (A088165). - Ctibor O. Zizka, Aug 13 2008

The intermediate convergents to 2^(1/2) begin with 4/3, 10/7, 24/17, 58/41; essentially, numerators=A052542 and denominators here. - Clark Kimberling, Aug 26 2008

Equals right border of triangle A143966. Starting (1, 3, 7, ...) equals INVERT transform of (1, 2, 2, 2, ...) and row sums of triangle A143966. - Gary W. Adamson, Sep 06 2008

Inverse binomial transform of A006012; Hankel transform is := [1, 2, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008

From Charlie Marion, Jan 07 2009: (Start)

In general, denominators, a(k,n) and numerators, b(k,n), of continued fraction convergents to sqrt((k+1)/k) may be found as follows:

let a(k,0) = 1, a(k,1) = 2k; for n>0, a(k,2n) = 2*a(k,2n-1) + a(k,2n-2) and a(k,2n+1) = (2k)*a(k,2n) + a(k,2n-1);

let b(k,0) = 1, b(k,1) = 2k+1; for n>0, b(k,2n) = 2*b(k,2n-1) + b(k,2n-2) and b(k,2n+1) = (2k)*b(k,2n) + b(k,2n-1).

For example, the convergents to sqrt(2/1) start 1/1, 3/2, 7/5, 17/12, 41/29.

In general, if a(k,n) and b(k,n) are the denominators and numerators, respectively, of continued fraction convergents to sqrt((k+1)/k) as defined above, then

k*a(k,2n)^2 - a(k,2n-1)*a(k,2n+1) = k = k*a(k,2n-2)*a(k,2n) - a(k,2n-1)^2 and

b(k,2n-1)*b(k,2n+1) - k*b(k,2n)^2 = k+1 = b(k,2n-1)^2 - k*b(k,2n-2)*b(k,2n);

for example, if k=1 and n=3, then b(1,n)=a(n+1) and

1*a(1,6)^2 - a(1,5)*a(1,7) = 1*169^2 - 70*408 = 1;

1*a(1,4)*a(1,6) - a(1,5)^2 = 1*29*169 - 70^2 = 1;

b(1,5)*b(1,7) - 1*b(1,6)^2 = 99*577 - 1*239^2 = 2;

b(1,5)^2 - 1*b(1,4)*b(1,6) = 99^2 - 1*41*239 = 2.

Cf. A000129, A142238-A142239, A153313-A153318.

(End)

This sequence occurs in the lower bound of the order of the set of equivalent resistances of n equal resistors combined in series and in parallel (A048211). - Sameen Ahmed Khan, Jun 28 2010

Let M = a triangle with the Fibonacci series in each column, but the leftmost column is shifted upwards one row. A001333 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 27 2010

a(n) is the number of compositions of n when there are 1 type of 1 and 2 types of other natural numbers. - Milan Janjic, Aug 13 2010

Equals the INVERTi transform of A055099. - Gary W. Adamson, Aug 14 2010

From L. Edson Jeffery, Apr 04 2011: (Start)

Let U be the unit-primitive matrix (see [Jeffery])

U = U_(8,2) = (0 0 1 0)

(0 1 0 1)

(1 0 2 0)

(0 2 0 1).

Then a(n) = (1/4)*Trace(U^n). (See also A084130, A006012.)

(End)

For n >= 1, row sums of triangle

m/k.|..0.....1.....2.....3.....4.....5.....6.....7

==================================================

.0..|..1

.1..|..1.....2

.2..|..1.....2.....4

.3..|..1.....4.....4.....8

.4..|..1.....4....12.....8....16

.5..|..1.....6....12....32....16....32

.6..|..1.....6....24....32....80....32....64

.7..|..1.....8....24....80....80...192....64...128

which is the triangle for numbers 2^k*C(m,k) with duplicated diagonals. - Vladimir Shevelev, Apr 12 2012

a(n) is also the number of ways to place k non-attacking wazirs on a 2 X n board, summed over all k >= 0 (a wazir is a leaper [0,1]). - Vaclav Kotesovec, May 08 2012

The sequences a(n) and b(n) := A000129(n) are entries of powers of the special case of the Brahmagupta Matrix - for details see Suryanarayan's paper. Further, as Suryanarayan remark, if we set A = 2*(a(n) + b(n))*b(n), B = a(n)*(a(n) + 2*b(n)), C = a(n)^2 + 2*a(n)*b(n) + 2*b(n)^2 we obtain integral solutions of the Pythagorean relation A^2 + B^2 = C^2, where A and B are consecutive integers. - Roman Witula, Jul 28 2012

Pisano period lengths: 1, 1, 8, 4, 12, 8, 6, 4, 24, 12, 24, 8, 28, 6, 24, 8, 16, 24, 40, 12, .... - R. J. Mathar, Aug 10 2012

This sequence and A000129 give the diagonal numbers described by Theon of Smyrna. - Sture Sjöstedt, Oct 20 2012

a(n) is the top left entry of the n-th power of any of the following six 3 X 3 binary matrices: [1, 1, 1; 1, 1, 1; 1, 0, 0] or [1, 1, 1; 1, 1, 0; 1, 1, 0] or [1, 1, 1; 1, 0, 1; 1, 1, 0] or [1, 1, 1; 1, 1, 0; 1, 0, 1] or [1, 1, 1; 1, 0, 1; 1, 0, 1] or [1, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

If p is prime, a(p) == 1 (mod p) (compare with similar comment for A000032). - Creighton Dement, Oct 11 2005, modified by Davide Colazingari, Jun 26 2016

a(n) = A000129(n) + A000129(n-1), where A000129(n) is the n-th Pell Number; e.g., a(6) = 99 = A000129(6) + A000129(5) = 70 + 29. Hence the sequence of fractions has the form 1 + A000129(n-1)/A000129(n), and the ratio A000129(n-1)/A000129(n)converges to sqrt(2) - 1. - Gregory L. Simay, Nov 30 2018

For n > 0, a(n+1) is the length of tau^n(1) where tau is the morphism: 1 -> 101, 0 -> 1. See Song and Wu. - Michel Marcus, Jul 21 2020

For n > 0, a(n) is the number of nonisomorphic quasitrivial semigroups with n elements, see Devillet, Marichal, Teheux. A292932 is the number of labeled quasitrivial semigroups. - Peter Jipsen, Mar 28 2021

a(n) is the permanent of the n X n tridiagonal matrix defined in A332602. - Stefano Spezia, Apr 12 2022

From Greg Dresden, May 08 2023: (Start)

For n >= 2, 4*a(n) is the number of ways to tile this T-shaped figure of length n-1 with two colors of squares and one color of domino; shown here is the figure of length 5 (corresponding to n=6), and it has 4*a(6) = 396 different tilings.

_

|| _

|||_|||

|_|

(End)

12*a(n) = number of walks of length n in the cyclic Kautz digraph CK(3,4). - Miquel A. Fiol, Feb 15 2024

This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n) and F(-1) = 1.

Number of ordered trees with n+1 edges and height at most 3 (height=number of edges on a maximal path starting at the root). Number of directed column-convex polyominoes of area n+1. Number of nondecreasing Dyck paths of length 2n+2. - Emeric Deutsch, Jul 11 2001

Terms are the solutions x to: 5x^2-4 is a square, with 5x^2-4 in A081071 and sqrt(5x^2-4) in A002878. - Benoit Cloitre, Apr 07 2002

a(0) = a(1) = 1, a(n+1) is the smallest Fibonacci number greater than the n-th partial sum. - Amarnath Murthy, Oct 21 2002

The fractional part of tau*a(n) decreases monotonically to zero. - Benoit Cloitre, Feb 01 2003

Numbers k such that floor(phi^2*k^2) - floor(phi*k)^2 = 1 where phi=(1+sqrt(5))/2. - Benoit Cloitre, Mar 16 2003

Number of leftist horizontally convex polyominoes with area n+1.

Number of 31-avoiding words of length n on alphabet {1,2,3} which do not end in 3. (E.g., at n=3, we have 111, 112, 121, 122, 132, 211, 212, 221, 222, 232, 321, 322 and 332.) See A028859. - Jon Perry, Aug 04 2003

Appears to give all solutions > 1 to the equation: x^2 = ceiling(x*r*floor(x/r)) where r=phi=(1+sqrt(5))/2. - Benoit Cloitre, Feb 24 2004

a(1) = 1, a(2) = 2, then the least number such that the square of any term is just less than the geometric mean of its neighbors. a(n+1)*a(n-1) > a(n)^2. - Amarnath Murthy, Apr 06 2004

All positive integer solutions of Pell equation b(n)^2 - 5*a(n+1)^2 = -4 together with b(n)=A002878(n), n >= 0. - Wolfdieter Lang, Aug 31 2004

Essentially same as Pisot sequence E(2,5).

Number of permutations of [n+1] avoiding 321 and 3412. E.g., a(3) = 13 because the permutations of [4] avoiding 321 and 3412 are 1234, 2134, 1324, 1243, 3124, 2314, 2143, 1423, 1342, 4123, 3142, 2413, 2341. - Bridget Tenner, Aug 15 2005

Number of 1324-avoiding circular permutations on [n+1].

A subset of the Markoff numbers (A002559). - Robert G. Wilson v, Oct 05 2005

(x,y) = (a(n), a(n+1)) are the solutions of x/(yz) + y/(xz) + z/(xy) = 3 with z=1. - Floor van Lamoen, Nov 29 2001

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

With interpolated zeros, counts closed walks of length n at the start or end node of P_4. a(n) counts closed walks of length 2n at the start or end node of P_4. The sequence 0,1,0,2,0,5,... counts walks of length n between the start and second node of P_4. - Paul Barry, Jan 26 2005

a(n) is the number of ordered trees on n edges containing exactly one non-leaf vertex all of whose children are leaves (every ordered tree must contain at least one such vertex). For example, a(0) = 1 because the root of the tree with no edges is not considered to be a leaf and the condition "all children are leaves" is vacuously satisfied by the root and a(4) = 13 counts all 14 ordered trees on 4 edges (A000108) except (ignore dots)

|..|

.\/.

which has two such vertices. - David Callan, Mar 02 2005

Number of directed column-convex polyominoes of area n. Example: a(2)=2 because we have the 1 X 2 and the 2 X 1 rectangles. - Emeric Deutsch, Jul 31 2006

Same as the number of Kekulé structures in polyphenanthrene in terms of the number of hexagons in extended (1,1)-nanotubes. See Table 1 on page 411 of I. Lukovits and D. Janezic. - Parthasarathy Nambi, Aug 22 2006

Number of free generators of degree n of symmetric polynomials in 3-noncommuting variables. - Mike Zabrocki, Oct 24 2006

Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5)*a(n) + sqrt(5*a(n)^2 - 4))/2) = n for n >= 1. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

Consider a teacher who teaches one student, then he finds he can teach two students while the original student learns to teach a student. And so on with every generation an individual can teach one more student then he could before. a(n) starting at a(2) gives the total number of new students/teachers (see program). - Ben Paul Thurston, Apr 11 2007

The Diophantine equation a(n)=m has a solution (for m >= 1) iff ceiling(arcsinh(sqrt(5)*m/2)/log(phi)) != ceiling(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130255(m)=A130256(m). - Hieronymus Fischer, May 24 2007

a(n+1) = B^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 2=`0`, 5=`00`, 13=`000`, ..., in Wythoff code.

Bisection of the Fibonacci sequence into odd-indexed nonzero terms (1, 2, 5, 13, ...) and even-indexed terms (1, 3, 8, 21, ...) may be represented as row sums of companion triangles A140068 and A140069. - Gary W. Adamson, May 04 2008

a(n) is the number of partitions pi of [n] (in standard increasing form) such that Flatten[pi] is a (2-1-3)-avoiding permutation. Example: a(4)=13 counts all 15 partitions of [4] except 13/24 and 13/2/4. Here "standard increasing form" means the entries are increasing in each block and the blocks are arranged in increasing order of their first entries. Also number that avoid 3-1-2. - David Callan, Jul 22 2008

Let P be the partial sum operator, A000012: (1; 1,1; 1,1,1; ...) and A153463 = M, the partial sum & shift operator. It appears that beginning with any randomly taken sequence S(n), iterates of the operations M * S(n), -> M * ANS, -> P * ANS, etc. (or starting with P) will rapidly converge upon a two-sequence limit cycle of (1, 2, 5, 13, 34, ...) and (1, 1, 3, 8, 21, ...). - Gary W. Adamson, Dec 27 2008

Number of musical compositions of Rhythm-music over a time period of n-1 units. Example: a(4)=13; indeed, denoting by R a rest over a time period of 1 unit and by N[j] a note over a period of j units, we have (writing N for N[1]): NNN, NNR, NRN, RNN, NRR, RNR, RRN, RRR, N[2]R, RN[2], NN[2], N[2]N, N[3] (see the J. Groh reference, pp. 43-48). - Juergen K. Groh (juergen.groh(AT)lhsystems.com), Jan 17 2010

Given an infinite lower triangular matrix M with (1, 2, 3, ...) in every column but the leftmost column shifted upwards one row. Then (1, 2, 5, ...) = lim_{n->infinity} M^n. (Cf. A144257.) - Gary W. Adamson, Feb 18 2010

As a fraction: 8/71 = 0.112676 or 98/9701 = 0.010102051334... (fraction 9/71 or 99/9701 for sequence without initial term). 19/71 or 199/9701 for sequence in reverse. - Mark Dols, May 18 2010

For n >= 1, a(n) is the number of compositions (ordered integer partitions) of 2n-1 into an odd number of odd parts. O.g.f.: (x-x^3)/(1-3x^2+x^4) = A(A(x)) where A(x) = 1/(1-x)-1/(1-x^2).

For n > 0, determinant of the n X n tridiagonal matrix with 1's in the super and subdiagonals, (1,3,3,3,...) in the main diagonal, and the rest zeros. - Gary W. Adamson, Jun 27 2011

The Gi3 sums, see A180662, of the triangles A108299 and A065941 equal the terms of this sequence without a(0). - Johannes W. Meijer, Aug 14 2011

The number of permutations for which length equals reflection length. - Bridget Tenner, Feb 22 2012

Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n+1, with exactly 2 elements of each rank between 0 and 1. (Uniform used in the sense of Retakh, Serconek and Wilson. Graded used in R. Stanley's sense that all maximal chains have the same length.)

HANKEL transform of sequence and the sequence omitting a(0) is the sequence A019590(n). This is the unique sequence with that property. - Michael Somos, May 03 2012

The number of Dyck paths of length 2n and height at most 3. - Ira M. Gessel, Aug 06 2012

Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - R. J. Mathar, Aug 10 2012

Primes in the sequence are 2, 5, 13, 89, 233, 1597, 28657, ... (apparently A005478 without the 3). - R. J. Mathar, May 09 2013

a(n+1) is the sum of rising diagonal of the Pascal triangle written as a square - cf. comments in A085812. E.g., 13 = 1+5+6+1. - John Molokach, Sep 26 2013

a(n) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 1, 1, 1; 0, 1, 1] or [1, 1, 1; 0, 1, 1; 1, 1, 1] or [1, 1, 0; 1, 1, 1; 1, 1, 1] or [1, 0, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014

Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker, Feb 04 2014

Except for the initial term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 64 = 0. - Colin Barker, Feb 16 2014

Positive values of x such that there is a y satisfying x^2 - xy - y^2 - 1 = 0. - Ralf Stephan, Jun 30 2014

a(n) is also the number of permutations simultaneously avoiding 231, 312 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl, Aug 07 2014

(1, a(n), a(n+1)), n >= 0, are Markoff triples (see A002559 and Robert G. Wilson v's Oct 05 2005 comment). In the Markoff tree they give one of the outer branches. Proof: a(n)*a(n+1) - 1 = A001906(2*n)^2 = (a(n+1) - a(n))^2 = a(n)^2 + a(n+1)^2 - 2*a(n)*a(n+1), thus 1^2 + a(n)^2 + a(n+1)^2 = 3*a(n)*a(n+1). - Wolfdieter Lang, Jan 30 2015

For n > 0, a(n) is the smallest positive integer not already in the sequence such that a(1) + a(2) + ... + a(n) is a Fibonacci number. - Derek Orr, Jun 01 2015

Number of vertices of degree n-2 (n >= 3) in all Fibonacci cubes, see Klavzar, Mollard, & Petkovsek. - Emeric Deutsch, Jun 22 2015

Except for the first term, this sequence can be generated by Corollary 1 (ii) of Azarian's paper in the references for this sequence. - Mohammad K. Azarian, Jul 02 2015

Precisely the numbers F(n)^k + F(n+1)^k that are also Fibonacci numbers with k > 1, see Luca & Oyono. - Charles R Greathouse IV, Aug 06 2015

a(n) = MA(n) - 2*(-1)^n where MA(n) is exactly the maximum area of a quadrilateral with lengths of sides in order L(n-2), L(n-2), F(n+1), F(n+1) for n > 1 and L(n)=A000032(n). - J. M. Bergot, Jan 28 2016

a(n) is the number of bargraphs of semiperimeter n+1 having no valleys (i.e., convex bargraphs). Equivalently, number of bargraphs of semiperimeter n+1 having exactly 1 peak. Example: a(5) = 34 because among the 35 (=A082582(6)) bargraphs of semiperimeter 6 only the one corresponding to the composition [2,1,2] has a valley. - Emeric Deutsch, Aug 12 2016

Integers k such that the fractional part of k*phi is less than 1/k. See Byszewski link p. 2. - Michel Marcus, Dec 10 2016

Number of words of length n-1 over {0,1,2,3} in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017

With a(0) = 0 this is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Fibonacci sequence A000045. See a Feb 17 2017 comment on A097805. - Wolfdieter Lang, Feb 17 2017

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) < e(k). [Martinez and Savage, 2.12] - Eric M. Schmidt, Jul 17 2017

Number of permutations of [n] that avoid the patterns 321 and 2341. - Colin Defant, May 11 2018

The sequence solves the following problem: find all the pairs (i,j) such that i divides 1+j^2 and j divides 1+i^2. In fact, the pairs (a(n), a(n+1)), n > 0, are all the solutions. - Tomohiro Yamada, Dec 23 2018

Number of permutations in S_n whose principal order ideals in the Bruhat order are lattices (equivalently, modular, distributive, Boolean lattices). - Bridget Tenner, Jan 16 2020

From Wolfdieter Lang, Mar 30 2020: (Start)

a(n) is the upper left entry of the n-th power of the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602: a(n) = ((M_2)^n)[1,1].

Proof: (M_2)^2 = 3*M + 1_2 (with the 2 X 2 unit matrix 1_2) from the characteristic polynomial of M_2 (see a comment in A322602) and the Cayley-Hamilton theorem. The recurrence M^n = M*M^(n-1) leads to (M_n)^n = S(n, 3)*1_2 + S(n-a, 3)*(M - 3*1_2), for n >= 0, with S(n, 3) = F(2(n+1)) = A001906(n+1). Hence ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3) = a(n) = F(2*n-1) = (1/(2*r+1))*r^(2*n-1)*(1 + (1/r^2)^(2*n-1)), with r = rho(5) = A001622 (golden ratio) (see the first Aug 31 2004 formula, using the recurrence of S(n, 3), and the Michael Somos Oct 28 2002 formula). This proves a conjecture of Gary W. Adamson in A322602.

The ratio a(n)/a(n-1) converges to r^2 = rho(5)^2 = A104457 for n -> infinity (see the a(n) formula in terms of r), which is one of the statements by Gary W. Adamson in A322602. (End)

a(n) is the number of ways to stack coins with a bottom row of n coins such that any coin not on the bottom row touches exactly two coins in the row below, and all the coins on any row are contiguous [Wilf, 2.12]. - Greg Dresden, Jun 29 2020

a(n) is the upper left entry of the (2*n)-th power of the 4 X 4 Jacobi matrix L with L(i,j)=1 if |i-j| = 1 and L(i,j)=0 otherwise. - Michael Shmoish, Aug 29 2020

All positive solutions of the indefinite binary quadratic F(1, -3, 1) := x^2 - 3*x*y + y^2, of discriminant 5, representing -1 (special Markov triples (1, y=x, z=y) if y <= z) are [x(n), y(n)] = [abs(F(2*n+1)), abs(F(2*n-1))], for n = -infinity..+infinity. (F(-n) = (-1)^(n+1)*F(n)). There is only this single family of proper solutions, and there are no improper solutions. [See also the Floor van Lamoen Nov 29 2001 comment, which uses this negative n, and my Jan 30 2015 comment.] - Wolfdieter Lang, Sep 23 2020

These are the denominators of the lower convergents to the golden ratio, tau; they are also the numerators of the upper convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022

a(n+1) is the number of subgraphs of the path graph on n vertices. - Leen Droogendijk, Jun 17 2023

For n > 4, a(n+2) is the number of ways to tile this 3 x n "double-box" shape with squares and dominos (reflections or rotations are counted as distinct tilings). The double-box shape is made up of two horizontal strips of length n, connected by three vertical columns of length 3, and the center column can be located anywhere not touching the two outside columns.

_ _ _ _

|||_|||_|||_|||_|||

|| _ |_| _ _ ||

|||_|||_|||_|||_|||. - Greg Dresden and Ruishan Wu, Aug 25 2024

a(n+1) is the number of integer sequences a_1, ..., a_n such that for any number 1 <= k <= n, (a_1 + ... + a_k)^2 = a_1^3 + ... + a_k^3. - Yifan Xie, Dec 07 2024

a(n) is also the Vandermonde determinant of the numbers 1,2,...,(n+1), i.e., the determinant of the (n+1) X (n+1) matrix A with A[i,j] = i^j, 1 <= i <= n+1, 0 <= j <= n. - Ahmed Fares (ahmedfares(AT)my-deja.com), May 06 2001

a(n) = (1/n!) * D(n) where D(n) is the determinant of order n in which the (i,j)-th element is i^j. - Amarnath Murthy, Jan 02 2002

Determinant of S_n where S_n is the n X n matrix S_n(i,j) = Sum_{d|i} d^j. - Benoit Cloitre, May 19 2002

Appears to be det(M_n) where M_n is the n X n matrix with m(i,j) = J_j(i) where J_k(n) denote the Jordan function of row k, column n (cf. A059380(m)). - Benoit Cloitre, May 19 2002

a(2n+1) = 1, 12, 34560, 125411328000, ... is the Hankel transform of A000182 (tangent numbers) = 1, 2, 16, 272, 7936, ...; example: det([1, 2, 16, 272; 2, 16, 272, 7936; 16, 272, 7936, 353792; 272, 7936, 353792, 22368256]) = 125411328000. - Philippe Deléham, Mar 07 2004

Determinant of the (n+1) X (n+1) matrix whose i-th row consists of terms 1 to n+1 of the Lucas sequence U(i,Q), for any Q. When Q=0, the Vandermonde matrix is obtained. - T. D. Noe, Aug 21 2004

Determinant of the (n+1) X (n+1) matrix A whose elements are A(i,j) = B(i+j) for 0 <= i,j <= n, where B(k) is the k-th Bell number, A000110(k) [I. Mezo, JIS 14 (2011) # 11.1.1]. - T. D. Noe, Dec 04 2004

The Hankel transform of the sequence A090365 is A000178(n+1); example: det([1,1,3; 1,3,11; 3,11,47]) = 12. - Philippe Deléham, Mar 02 2005

Theorem 1.3, page 2, of Polynomial points, Journal of Integer Sequences, Vol. 10 (2007), Article 07.3.6, provides an example of an Abelian quotient group of order (n-1) superfactorial, for each positive integer n. The quotient is obtained from sequences of polynomial values. - E. F. Cornelius, Jr. (efcornelius(AT)comcast.net), Apr 09 2007

Starting with offset 1 this is a 'Matryoshka doll' sequence with alpha=1, the multiplicative counterpart to the additive A000292. seq(mul(mul(i,i=alpha..k), k=alpha..n),n=alpha..12). - Peter Luschny, Jul 14 2009

For n>0, a(n) is also the determinant of S_n where S_n is the n X n matrix, indexed from 1, S_n(i,j)=sigma_i(j), where sigma_k(n) is the generalized divisor sigma function: A000203 is sigma_1(n). - Enrique Pérez Herrero, Jun 21 2010

a(n) is the multiplicative Wiener index of the (n+1)-vertex path. Example: a(4)=288 because in the path on 5 vertices there are 3 distances equal to 2, 2 distances equal to 3, and 1 distance equal to 4 (2*2*2*3*3*4=288). See p. 115 of the Gutman et al. reference. - Emeric Deutsch, Sep 21 2011

a(n-1) = Product_{j=1..n-1} j! = V(n) = Product_{1 <= i < j <= n} (j - i) (a Vandermondian V(n), see the Ahmed Fares May 06 2001 comment above), n >= 1, is in fact the determinant of any n X n matrix M(n) with entries M(n;i,j) = p(j-1,x = i), 1 <= i, j <= n, where p(m,x), m >= 0, are monic polynomials of exact degree m with p(0,x) = 1. This is a special x[i] = i choice in a general theorem given in Vein-Dale, p. 59 (written for the transposed matrix M(n;j,x_i) = p(i-1,x_j) = P_i(x_j) in Vein-Dale, and there a_{k,k} = 1, for k=1..n). See the Aug 26 2013 comment under A049310, where p(n,x) = S(n,x) (Chebyshev S). - Wolfdieter Lang, Aug 27 2013

a(n) is the number of monotonic magmas on n elements labeled 1..n with a symmetric multiplication table. I.e., Product(i,j) >= max(i,j); Product(i,j) = Product(j,i). - Chad Brewbaker, Nov 03 2013

The product of the pairwise differences of n+1 integers is a multiple of a(n) [and this does not hold for any k > a(n)]. - Charles R Greathouse IV, Aug 15 2014

a(n) is the determinant of the (n+1) X (n+1) matrix M with M(i,j) = (n+j-1)!/(n+j-i)!, 1 <= i <= n+1, 1 <= j <= n+1. - Stoyan Apostolov, Aug 26 2014

All terms are in A064807 and all terms after a(2) are in A005101. - Ivan N. Ianakiev, Sep 02 2016

Empirical: a(n-1) is the determinant of order n in which the (i,j)-th entry is the (j-1)-th derivative of x^(x+i-1) evaluated at x=1. - John M. Campbell, Dec 13 2016

Empirical: If f(x) is a smooth, real-valued function on an open neighborhood of 0 such that f(0)=1, then a(n) is the determinant of order n+1 in which the (i,j)-th entry is the (j-1)-th derivative of f(x)/((1-x)^(i-1)) evaluated at x=0. - John M. Campbell, Dec 27 2016

Also the automorphism group order of the n-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017

Is the zigzag Hankel transform of A000182. That is, a(2*n+1) is the Hankel transform of A000182 and a(2*n+2) is the Hankel transform of A000182(n+1). - Michael Somos, Mar 11 2020

Except for n = 0, 1, superfactorial a(n) is never a square (proof in link Mabry and Cormick, FFF 4 p. 349); however, when k belongs to A349079 (see for further information), there exists m, 1 <= m <= k such that a(k) / m! is a square. - Bernard Schott, Nov 29 2021

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.

Number of paths from (0,0) to (n,n) in an n X n grid using only steps north, northeast and east (i.e., steps (1,0), (1,1), and (0,1)).

Also the number of ways of aligning two sequences (e.g., of nucleotides or amino acids) of length n, with at most 2*n gaps (-) inserted, so that while unnecessary gappings: - -a a- - are forbidden, both b- and -b are allowed. (If only other of the latter is allowed, then the sequence A000984 gives the number of alignments.) There is an easy bijection from grid walks given by Dickau to such set of alignments (e.g., the straight diagonal corresponds to the perfect alignment with no gaps). - Antti Karttunen, Oct 10 2001

Also main diagonal of array A008288 defined by m(i,1) = m(1,j) = 1, m(i,j) = m(i-1,j-1) + m(i-1,j) + m(i,j-1). - Benoit Cloitre, May 03 2002

So, as a special case of Dmitry Zaitsev's Dec 10 2015 comment on A008288, a(n) is the number of points in Z^n that are L1 (Manhattan) distance <= n from any given point. These terms occur in the crystal ball sequences: a(n) here is the n-th term in the sequence for the n-dimensional cubic lattice. See A008288 for a list of crystal ball sequences (rows or columns of A008288). - Shel Kaphan, Dec 26 2022

a(n) is the number of n-matchings of a comb-like graph with 2*n teeth. Example: a(2) = 13 because the graph consisting of a horizontal path ABCD and the teeth Aa, Bb, Cc, Dd has 13 2-matchings: any of the six possible pairs of teeth and {Aa, BC}, {Aa, CD}, {Bb, CD}, {Cc, AB}, {Dd, AB}, {Dd, BC}, {AB, CD}. - Emeric Deutsch, Jul 02 2002

Number of ordered trees with 2*n+1 edges, having root of odd degree, nonroot nodes of outdegree at most 2 and branches of odd length. - Emeric Deutsch, Aug 02 2002

The sum of the first n coefficients of ((1 - x) / (1 - 2*x))^n is a(n-1). - Michael Somos, Sep 28 2003

Row sums of A063007 and A105870. - Paul Barry, Apr 23 2005

The Hankel transform (see A001906 for definition) of this sequence is A036442: 1, 4, 32, 512, 16384, ... . - Philippe Deléham, Jul 03 2005

Also number of paths from (0,0) to (n,0) using only steps U = (1,1), H = (1,0) and D =(1,-1), U can have 2 colors and H can have 3 colors. - N-E. Fahssi, Jan 27 2008

Equals row sums of triangle A152250 and INVERT transform of A109980: (1, 2, 8, 36, 172, 852, ...). - Gary W. Adamson, Nov 30 2008

Number of overpartitions in the n X n box (treat a walk of the type in the first comment as an overpartition, by interpreting a NE step as N, E with the part thus created being overlined). - William J. Keith, May 19 2017

Diagonal of rational functions 1/(1 - x - y - x*y), 1/(1 - x - y*z - x*y*z). - Gheorghe Coserea, Jul 03 2018

Dimensions of endomorphism algebras End(R^{(n)}) in the Delannoy category attached to the oligomorphic group of order preserving self-bijections of the real line. - Noah Snyder, Mar 22 2023

a(n) is the number of ways to tile a strip of length n with white squares, black squares, and red dominos, where we must have an equal number of white and black squares. - Greg Dresden and Leo Zhang, Jul 11 2025

Also called Motzkin summands or ring numbers.

The old name was "Motzkin sums", used in certain publications. The sequence has the property that Motzkin(n) = A001006(n) = a(n) + a(n+1), e.g., A001006(4) = 9 = 3 + 6 = a(4) + a(5).

Number of 'Catalan partitions', that is partitions of a set 1,2,3,...,n into parts that are not singletons and whose convex hulls are disjoint when the points are arranged on a circle (so when the parts are all pairs we get Catalan numbers). - Aart Blokhuis (aartb(AT)win.tue.nl), Jul 04 2000

Number of ordered trees with n edges and no vertices of outdegree 1. For n > 1, number of dissections of a convex polygon by nonintersecting diagonals with a total number of n+1 edges. - Emeric Deutsch, Mar 06 2002

Number of Motzkin paths of length n with no horizontal steps at level 0. - Emeric Deutsch, Nov 09 2003

Number of Dyck paths of semilength n with no peaks at odd level. Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUDUDD, where U=(1,1), D=(1,-1). Number of Dyck paths of semilength n with no ascents of length 1 (an ascent in a Dyck path is a maximal string of up steps). Example: a(4)=3 because we have UUUUDDDD, UUDDUUDD and UUDUUDDD. - Emeric Deutsch, Dec 05 2003

Arises in Schubert calculus as follows. Let P = complex projective space of dimension n+1. Take n projective subspaces of codimension 3 in P in general position. Then a(n) is the number of lines of P intersecting all these subspaces. - F. Hirzebruch, Feb 09 2004

Difference between central trinomial coefficient and its predecessor. Example: a(6) = 15 = 141 - 126 and (1 + x + x^2)^6 = ... + 126*x^5 + 141*x^6 + ... (Catalan number A000108(n) is the difference between central binomial coefficient and its predecessor.) - David Callan, Feb 07 2004

a(n) = number of 321-avoiding permutations on [n] in which each left-to-right maximum is a descent (i.e., is followed by a smaller number). For example, a(4) counts 4123, 3142, 2143. - David Callan, Jul 20 2005

The Hankel transform of this sequence give A000012 = [1, 1, 1, 1, 1, 1, 1, ...]; example: Det([1, 0, 1, 1; 0, 1, 1, 3; 1, 1, 3, 6; 1, 3, 6, 15]) = 1. - Philippe Deléham, May 28 2005

The number of projective invariants of degree 2 for n labeled points on the projective line. - Benjamin J. Howard (bhoward(AT)ima.umn.edu), Nov 24 2006

Define a random variable X=trA^2, where A is a 2 X 2 unitary symplectic matrix chosen from USp(2) with Haar measure. The n-th central moment of X is E[(X+1)^n] = a(n). - Andrew V. Sutherland, Dec 02 2007

Let V be the adjoint representation of the complex Lie algebra sl(2). The dimension of the invariant subspace of the n-th tensor power of V is a(n). - Samson Black (sblack1(AT)uoregon.edu), Aug 27 2008

Starting with offset 3 = iterates of M * [1,1,1,...], where M = a tridiagonal matrix with [0,1,1,1,...] in the main diagonal and [1,1,1,...] in the super and subdiagonals. - Gary W. Adamson, Jan 08 2009

a(n) has the following standard-Young-tableaux (SYT) interpretation: binomial(n+1,k)*binomial(n-k-1,k-1)/(n+1)=f^(k,k,1^{n-2k}) where f^lambda equals the number of SYT of shape lambda. - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 02 2010

a(n) is also the sum of the numbers of standard Young tableaux of shapes (k,k,1^{n-2k}) for all 1 <= k <= floor(n/2). - Amitai Regev (amotai.regev(AT)weizmann.ac.il), Mar 10 2010

a(n) is the number of derangements of {1,2,...,n} having genus 0. The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q. Example: a(3)=1 because p=231=(123) is the only derangement of {1,2,3} with genus 0. Indeed, cp'=231*312=123=(1)(2)(3) and so g(p) = (1/2)(3+1-1-3)=0. - Emeric Deutsch, May 29 2010

Apparently: Number of Dyck 2n-paths with all ascents length 2 and no descent length 2. - David Scambler, Apr 17 2012

This is true. Proof: The mapping "insert a peak (UD) after each upstep (U)" is a bijection from all Dyck n-paths to those Dyck (2n)-paths in which each ascent is of length 2. It sends descents of length 1 in the n-path to descents of length 2 in the (2n)-path. But Dyck n-paths with no descents of length 1 are equinumerous with Riordan n-paths (Motzkin n-paths with no flatsteps at ground level) as follows. Given a Dyck n-path with no descents of length 1, split it into consecutive step pairs, then replace UU with U, DD with D, UD with a blue flatstep (F), DU with a red flatstep, and concatenate the new steps to get a colored Motzkin path. Each red F will be (immediately) preceded by a blue F or a D. In the latter case, transfer the red F so that it precedes the matching U of the D. Finally, erase colors to get the required Riordan path. For example, with lowercase f denoting a red flatstep, U^5 D^2 U D^4 U^4 D^3 U D^2 -> (U^2, U^2, UD, DU, D^2, D^2, U^2, U^2 D^2, DU, D^2) -> UUFfDDUUDfD -> UUFFDDUFUDD. - David Callan, Apr 25 2012

From Nolan Wallach, Aug 20 2014: (Start)

Let ch[part1, part2] be the value of the character of the symmetric group on n letters corresponding to the partition part1 of n on the conjucgacy class given by part2. Let A[n] be the set of (n+1) partitions of 2n with parts 1 or 2. Then deleting the first term of the sequence one has a(n) = Sum_{k=1..n+1} binomial(n,k-1)*ch[[n,n], A[n][[k]]])/2^n. This via the Frobenius Character Formula can be interpreted as the dimension of the SL(n,C) invariants in tensor^n (wedge^2 C^n).

Explanation: Let p_j denote sum (x_i)^j the sum in k variables. Then the Frobenius formula says then (p_1)^j_1 (p_2)^j_2 ... (p_r)^j_r is equal to sum(lambda, ch[lambda, 1^j_12^j_2 ... r^j_r] S_lambda) with S_lambda the Schur function corresponding to lambda. This formula implies that the coefficient of S([n,n]) in (((p_1)^1+p_2)/2)^n in its expansion in terms of Schur functions is the right hand side of our formula. If we specialize the number of variables to 2 then S[n,n](x,y)=(xy)^n. Which when restricted to y=x^(-1) is 1. That is it is 1 on SL(2).

On the other hand ((p_1)^2+p_2)/2 is the complete homogeneous symmetric function of degree 2 that is tr(S^2(X)). Thus our formula for a(n) is the same as that of Samson Black above since his V is the same as S^2(C^2) as a representation of SL(2). On the other hand, if we multiply ch(lambda) by sgn you get ch(Transpose(lambda)). So ch([n,n]) becomes ch([2,...,2]) (here there are n 2's). The formula for a(n) is now (1/2^n)*Sum_{j=0..n} ch([2,..,2], 1^(2n-2j) 2^j])*(-1)^j)*binomial(n,j), which calculates the coefficient of S_(2,...,2) in (((p_1)^2-p_2)/2)^n. But ((p_1)^2-p_2)/2 in n variables is the second elementary symmetric function which is the character of wedge^2 C^n and S_(2,...,2) is 1 on SL(n).

(End)

a(n) = number of noncrossing partitions (A000108) of [n] that contain no singletons, also number of nonnesting partitions (A000108) of [n] that contain no singletons. - David Callan, Aug 27 2014

From Tom Copeland, Nov 02 2014: (Start)

Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x)= [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).

Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)].

Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).

BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].

Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).

Various relations among the o.g.f.s may be easily constructed, such as Fib[-Mot(-x)] = -P[P(-x)] = x/(1-2*x) a generating fct for 2^n.

Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1]. (End)

Consistent with David Callan's comment above, A249548, provides a refinement of the Motzkin sums into the individual numbers for the non-crossing partitions he describes. - Tom Copeland, Nov 09 2014

The number of lattice paths from (0,0) to (n,0) that do not cross below the x-axis and use up-step=(1,1) and down-steps=(1,-k) where k is a positive integer. For example, a(4) = 3: [(1,1)(1,1)(1,-1)(1,-1)], [(1,1)(1,-1)(1,1)(1,-1)] and [(1,1)(1,1)(1,1)(1,-3)]. - Nicholas Ham, Aug 19 2015

A series created using 2*(a(n) + a(n+1)) + (a(n+1) + a(n+2)) has Hankel transform of F(2n), offset 3, F being a Fibonacci number, A001906 (Empirical observation). - Tony Foster III, Jul 30 2016

The series a(n) + A001006(n) has Hankel transform F(2n+1), offset n=1, F being the Fibonacci bisection A001519 (empirical observation). - Tony Foster III, Sep 05 2016

The Rubey and Stump reference proves a refinement of a conjecture of René Marczinzik, which they state as: "The number of 2-Gorenstein algebras which are Nakayama algebras with n simple modules and have an oriented line as associated quiver equals the number of Motzkin paths of length n. Moreover, the number of such algebras having the double centraliser property with respect to a minimal faithful projective-injective module equals the number of Riordan paths, that is, Motzkin paths without level-steps at height zero, of length n." - Eric M. Schmidt, Dec 16 2017

A connection to the Thue-Morse sequence: (-1)^a(n) = (-1)^A010060(n) * (-1)^A010060(n+1) = A106400(n) * A106400(n+1). - Vladimir Reshetnikov, Jul 21 2019

Named by Bernhart (1999) after the American mathematician John Riordan (1903-1988). - Amiram Eldar, Apr 15 2021

Drop initial 2; then iterates of A050411 do not diverge for these starting values. - David W. Wilson

All nonnegative integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = +4 together with b(n)=A001906(n), n>=0. - Wolfdieter Lang, Aug 31 2004

a(n+1) = B^(n)AB(1), n>=0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 3=`10`, 7=`010`, 18=`0010`, 47=`00010`, ..., in Wythoff code. a(0) = 2 = B(1) in Wythoff code.

Output of Tesler's formula (as well as that of Lu and Wu) for the number of perfect matchings of an m X n Möbius band where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009

Numbers having two 1's in their base-phi representation. - Robert G. Wilson v, Sep 13 2010

Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... - R. J. Mathar, Aug 10 2012

From Wolfdieter Lang, Feb 18 2013: (Start)

a(n) is also one half of the total number of round trips, each of length 2*n, on the graph P_4 (o-o-o-o) (the simple path with 4 points (vertices) and 3 lines (or edges)). See the array and triangle A198632 for the general case of the graph P_N (there N is n and the length is l=2*k).

O.g.f. for w(4,l) (with zeros for odd l): y*(d/dy)S(4,y)/S(4,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form. One half of this o.g.f. for x -> sqrt(x) produces the g.f. (2-3x)/(1-3x+x^2) given below. (End)

Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy - 5. - Michel Lagneau, Feb 01 2014

Except for the first term, positive values of x (or y) satisfying x^2 - 7xy + y^2 + 45 = 0. - Colin Barker, Feb 16 2014

Except for the first term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 320 = 0. - Colin Barker, Feb 16 2014

a(n) are the numbers such that a(n)^2-2 are Lucas numbers. - Michel Lagneau, Jul 22 2014

All sequences of this form, b(n+1) = 3*b(n) - b(n-1), regardless of initial values, which includes this sequence, yield this sequence as follows: a(n) = (b(j+n) + b(j-n))/b(j), for any j, except where b(j) = 0. Also note formula below relating this a(n) to all sequences of the form G(n+1) = G(n) + G(n-1). - Richard R. Forberg, Nov 18 2014

A non-simple continued fraction expansion for F(2n*(k+1))/F(2nk) k>=1 is a(n) + (-1)/(a(n) + (-1)/(a(n) + ... + (-1)/a(n))) where a(n) appears exactly k times (F(n) denotes the n-th Fibonacci number). E.g., F(16)/F(12) equals 7 + (-1)/(7 + (-1)/7). Furthermore, these a(n) are exactly the positive integers k such that the non-simple infinite continued fraction k + (-1)/(k + (-1)/(k + (-1)/(k + ...))) belongs to Q(sqrt(5)). Compare to Benoit Cloitre and Thomas Baruchel's comments at A002878. - Greg Dresden, Aug 13 2019

For n >= 1, a(n) is the number of cyclic up-down words of length 2*n over an alphabet of size 3. - Sela Fried, Apr 08 2025

Number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1), H=(2,0) and never going below the x-axis) from (0,0) to (2n,0) with no peaks at odd level. Example: a(2)=3 because we have UUDD, UHD and HH. - Emeric Deutsch, Dec 06 2003

Number of 3-Motzkin paths of length n-1 (i.e., lattice paths from (0,0) to (n-1,0) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0)). Example: a(4)=36 because we have 27 HHH paths, 3 HUD paths, 3 UHD paths and 3 UDH paths. - Emeric Deutsch, Jan 22 2004

Number of rooted, planar trees having edges weighted by strictly positive integers (multi-trees) with weight-sum n. - Roland Bacher, Feb 28 2005

Number of skew Dyck paths of semilength n. A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of the path is defined to be the number of its steps. - Emeric Deutsch, May 10 2007

Equivalently, number of self-avoiding paths of semilength n in the first quadrant beginning at the origin, staying weakly above the diagonal, ending on the diagonal, and consisting of steps r=(+1,0) (right), U=(0,+1) (up), and D=(0,-1) (down). Self-avoidance implies that factors UD and DU and steps D reaching the diagonal before the end are forbidden. The a(3) = 10 such paths are UrUrUr, UrUUrD, UrUUrr, UUrrUr, UUrUrD, UUrUrr, UUUDrD, UUUrDD, UUUrrD, and UUUrrr. - Joerg Arndt, Jan 15 2024

Hankel transform of [1,3,10,36,137,543,...] is A000012 = [1,1,1,1,...]. - Philippe Deléham, Oct 24 2007

From Gary W. Adamson, May 17 2009: (Start)

Convolved with A026375, (1, 3, 11, 45, 195, ...) = A026378: (1, 4, 17, 75, ...)

(1, 3, 10, 36, 137, ...) convolved with A026375 = A026376: (1, 6, 30, 144, ...).

Starting (1, 3, 10, 36, ...) = INVERT transform of A007317: (1, 2, 5, 15, 51, ...). (End)

Binomial transform of A032357. - Philippe Deléham, Sep 17 2009

a(n) = number of rooted trees with n vertices in which each vertex has at most 2 children and in case a vertex has exactly one child, it is labeled left, middle or right. These are the hex trees of the Deutsch, Munarini, Rinaldi link. This interpretation yields the second MATHEMATICA recurrence below. - David Callan, Oct 14 2012

The left shift (1,3,10,36,...) of this sequence is the binomial transform of the left-shifted Catalan numbers (1,2,5,14,...). Example: 36 =1*14 + 3*5 + 3*2 + 1*1. - David Callan, Feb 01 2014

Number of Schroeder paths from (0,0) to (2n,0) with no level steps H=(2,0) at even level. Example: a(2)=3 because we have UUDD, UHD and UDUD. - José Luis Ramírez Ramírez, Apr 27 2015

This is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Catalan sequence A000108. See a Feb 17 2017 comment in A097805. - Wolfdieter Lang, Feb 17 2017

a(n) is the number of parking functions of size n avoiding the patterns 132 and 231. - Lara Pudwell, Apr 10 2023

In any generalized Fibonacci sequence {f(i)}, Sum_{i=0..4n+1} f(i) = a(n)*f(2n+2). - Lekraj Beedassy, Dec 31 2002

The continued fraction expansion for F((2n+1)*(k+1))/F((2n+1)*k), k>=1 is [a(n),a(n),...,a(n)] where there are exactly k elements (F(n) denotes the n-th Fibonacci number). E.g., continued fraction for F(12)/F(9) is [4, 4,4]. - Benoit Cloitre, Apr 10 2003

See A135064 for a possible connection with Galois groups of quintics.

Sequence of all positive integers k such that continued fraction [k,k,k,k,k,k,...] belongs to Q(sqrt(5)). - Thomas Baruchel, Sep 15 2003

All positive integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = -4 together with b(n)=A001519(n), n>=0.

a(n) = L(n,-3)*(-1)^n, where L is defined as in A108299; see also A001519 for L(n,+3).

Inverse binomial transform of A030191. - Philippe Deléham, Oct 04 2005

General recurrence is a(n) = (a(1)-1)*a(n-1) - a(n-2), a(1) >= 4, lim_{n->infinity} a(n) = x*(k*x+1)^n, k =(a(1)-3), x=(1+sqrt((a(1)+1)/(a(1)-3)))/2. Examples in OEIS: a(1)=4 gives A002878. a(1)=5 gives A001834. a(1)=6 gives A030221. a(1)=7 gives A002315. a(1)=8 gives A033890. a(1)=9 gives A057080. a(1)=10 gives A057081. - Ctibor O. Zizka, Sep 02 2008

Let r = (2n+1), then a(n), n>0 = Product_{k=1..floor((r-1)/2)} (1 + sin^2 k*Pi/r); e.g., a(3) = 29 = (3.4450418679...)*(4.801937735...)*(1.753020396...). - Gary W. Adamson, Nov 26 2008

a(n+1) is the Hankel transform of A001700(n)+A001700(n+1). - Paul Barry, Apr 21 2009

a(n) is equal to the permanent of the (2n) X (2n) tridiagonal matrix with sqrt(5)'s along the main diagonal, i's along the superdiagonal and the subdiagonal (i is the imaginary unit), and 0's everywhere else. - John M. Campbell, Jun 09 2011

Conjecture: for n > 0, a(n) = sqrt(Fibonacci(4*n+3) + Sum_{k=2..2*n} Fibonacci(2*k)). - Alex Ratushnyak, May 06 2012

Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... . - R. J. Mathar, Aug 10 2012

The continued fraction [a(n); a(n), a(n), ...] = phi^(2n+1), where phi is the golden ratio, A001622. - Thomas Ordowski, Jun 05 2013

Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy + 5. - Michel Lagneau, Feb 01 2014

Conjecture: except for the number 3, a(n) are the numbers such that a(n)^2+2 are Lucas numbers. - Michel Lagneau, Jul 22 2014

Comment on the preceding conjecture: It is clear that all a(n) satisfy a(n)^2 + 2 = L(2*(2*n+1)) due to the identity (17 c) of Vajda, p. 177: L(2*n) + 2*(-1)^n = L(n)^2 (take n -> 2*n+1). - Wolfdieter Lang, Oct 10 2014

Limit_{n->oo} a(n+1)/a(n) = phi^2 = phi + 1 = (3+sqrt(5))/2. - Derek Orr, Jun 18 2015

If d[k] denotes the sequence of k-th differences of this sequence, then d[0](0), d[1](1), d[2](2), d[3](3), ... = A048876, cf. message to SeqFan list by P. Curtz on March 2, 2016. - M. F. Hasler, Mar 03 2016

a(n-1) and a(n) are the least phi-antipalindromic numbers (A178482) with 2*n and 2*n+1 digits in base phi, respectively. - Amiram Eldar, Jul 07 2021

Triangulate (hyperbolic) 2-space such that around every vertex exactly 7 triangles touch. Call any 7 triangles having a common vertex the first layer and let the (n+1)-st layer be all triangles that do not appear in any of the first n layers and have a common vertex with the n-th layer. Then the n-th layer contains 7*a(n-1) triangles. E.g., the first layer (by definition) contains 7 triangles, the second layer (the "ring" of triangles around the first layer) consists of 28 triangles, the third layer (the next "ring") consists of 77 triangles, and so on. - Nicolas Nagel, Aug 13 2022