cp's OEIS Frontend

See A065091 for comments, formulas etc. concerning only odd primes. For all information concerning prime powers, see A000961. For contributions concerning "almost primes" see A002808.

A number p is prime if (and only if) it is greater than 1 and has no positive divisors except 1 and p.

A natural number is prime if and only if it has exactly two (positive) divisors.

A prime has exactly one proper positive divisor, 1.

The paper by Kaoru Motose starts as follows: "Let q be a prime divisor of a Mersenne number 2^p-1 where p is prime. Then p is the order of 2 (mod q). Thus p is a divisor of q - 1 and q > p. This shows that there exist infinitely many prime numbers." - Pieter Moree, Oct 14 2004

1 is not a prime, for if the primes included 1, then the factorization of a natural number n into a product of primes would not be unique, since n = n*1.

Prime(n) and pi(n) are inverse functions: A000720(a(n)) = n and a(n) is the least number m such that a(A000720(m)) = a(n). a(A000720(n)) = n if (and only if) n is prime.

Second sequence ever computed by electronic computer, on EDSAC, May 09 1949 (see Renwick link). - Russ Cox, Apr 20 2006

Every prime p > 3 is a linear combination of previous primes prime(n) with nonzero coefficients c(n) and |c(n)| < prime(n). - Amarnath Murthy, Franklin T. Adams-Watters and Joshua Zucker, May 17 2006; clarified by Chayim Lowen, Jul 17 2015

The Greek transliteration of 'Prime Number' is 'Protos Arithmos'. - Daniel Forgues, May 08 2009 [Edited by Petros Hadjicostas, Nov 18 2019]

A number n is prime if and only if it is different from zero and different from a unit and each multiple of n decomposes into factors such that n divides at least one of the factors. This applies equally to the integers (where a prime has exactly four divisors (the definition of divisors is relaxed such that they can be negative)) and the positive integers (where a prime has exactly two distinct divisors). - Peter Luschny, Oct 09 2012

Motivated by his conjecture on representations of integers by alternating sums of consecutive primes, for any positive integer n, Zhi-Wei Sun conjectured that the polynomial P_n(x) = Sum_{k=0..n} a(k+1)*x^k is irreducible over the field of rational numbers with the Galois group S_n, and moreover P_n(x) is irreducible mod a(m) for some m <= n(n+1)/2. It seems that no known criterion on irreducibility of polynomials implies this conjecture. - Zhi-Wei Sun, Mar 23 2013

Questions on a(2n) and Ramanujan primes are in A233739. - Jonathan Sondow, Dec 16 2013

From Hieronymus Fischer, Apr 02 2014: (Start)

Natural numbers such that there is exactly one base b such that the base-b alternate digital sum is 0 (see A239707).

Equivalently: Numbers p > 1 such that b = p-1 is the only base >= 1 for which the base-b alternate digital sum is 0.

Equivalently: Numbers p > 1 such that the base-b alternate digital sum is <> 0 for all bases 1 <= b < p-1. (End)

An integer n > 1 is a prime if and only if it is not the sum of positive integers in arithmetic progression with common difference 2. - Jean-Christophe Hervé, Jun 01 2014

Conjecture: Numbers having prime factors <= prime(n+1) are {k|k^f(n) mod primorial(n)=1}, where f(n) = lcm(prime(i)-1, i=1..n) = A058254(n) and primorial(n) = A002110(n). For example, numbers with no prime divisor <= prime(7) = 17 are {k|k^60 mod 30030=1}. - Gary Detlefs, Jun 07 2014

Cramer conjecture prime(n+1) - prime(n) < C log^2 prime(n) is equivalent to the inequality (log prime(n+1)/log prime(n))^n < e^C, as n tend to infinity, where C is an absolute constant. - Thomas Ordowski, Oct 06 2014

I conjecture that for any positive rational number r there are finitely many primes q_1,...,q_k such that r = Sum_{j=1..k} 1/(q_j-1). For example, 2 = 1/(2-1) + 1/(3-1) + 1/(5-1) + 1/(7-1) + 1/(13-1) with 2, 3, 5, 7 and 13 all prime, 1/7 = 1/(13-1) + 1/(29-1) + 1/(43-1) with 13, 29 and 43 all prime, and 5/7 = 1/(3-1) + 1/(7-1) + 1/(31-1) + 1/(71-1) with 3, 7, 31 and 71 all prime. - Zhi-Wei Sun, Sep 09 2015

I also conjecture that for any positive rational number r there are finitely many primes p_1,...,p_k such that r = Sum_{j=1..k} 1/(p_j+1). For example, 1 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(11+1) + 1/(23+1) with 2, 3, 5, 7, 11 and 23 all prime, and 10/11 = 1/(2+1) + 1/(3+1) + 1/(5+1) + 1/(7+1) + 1/(43+1) + 1/(131+1) + 1/(263+1) with 2, 3, 5, 7, 43, 131 and 263 all prime. - Zhi-Wei Sun, Sep 13 2015

Numbers k such that ((k-2)!!)^2 == +-1 (mod k). - Thomas Ordowski, Aug 27 2016

Does not satisfy Benford's law [Diaconis, 1977; Cohen-Katz, 1984; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 07 2017

Prime numbers are the integer roots of 1 - sin(Pi*Gamma(s)/s)/sin(Pi/s). - Peter Luschny, Feb 23 2018

Conjecture: log log a(n+1) - log log a(n) < 1/n. - Thomas Ordowski, Feb 17 2023

There are eleven uniform (or Archimedean) tilings (or planar nets), with vertex symbols 3^6, 3^4.6, 3^3.4^2, 3^2.4.3.4, 4^4, 3.4.6.4, 3.6.3.6, 6^3, 3.12^2, 4.6.12, and 4.8^2. Grünbaum and Shephard (1987) is the best reference.

a(n) is the number of vertices at graph distance n from any fixed vertex.

The Mathematica notebook can compute 30 or 40 iterations, and colors them with period 5. You could also change out images if you want to. These graphs are better for analyzing 5-iteration chunks of the pattern. You can see that under iteration all fragments of the circumferences are preserved in shape and translated outwards a distance approximately sqrt(21) (relative to small triangle edge), the length of a long diagonal of larger rhombus unit cell. The conjectured recurrence should follow from an analysis of how new pieces occur in between the translated pieces. - Bradley Klee, Nov 26 2014

D. E. Knuth writes: "Before Fibonacci wrote his work, the sequence F_{n} had already been discussed by Indian scholars, who had long been interested in rhythmic patterns that are formed from one-beat and two-beat notes. The number of such rhythms having n beats altogether is F_{n+1}; therefore both Gopāla (before 1135) and Hemachandra (c. 1150) mentioned the numbers 1, 2, 3, 5, 8, 13, 21, ... explicitly." (TAOCP Vol. 1, 2nd ed.) - Peter Luschny, Jan 11 2015

In keeping with historical accounts (see the references by P. Singh and S. Kak), the generalized Fibonacci sequence a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, ... can also be described as the Gopala-Hemachandra numbers H(n) = H(n-1) + H(n-2), with F(n) = H(n) for a = b = 1, and Lucas sequence L(n) = H(n) for a = 2, b = 1. - Lekraj Beedassy, Jan 11 2015

Susantha Goonatilake writes: "[T]his sequence was well known in South Asia and used in the metrical sciences. Its development is attributed in part to Pingala (200 BC), later being associated with Virahanka (circa 700 AD), Gopala (circa 1135), and Hemachandra (circa 1150)—all of whom lived and worked prior to Fibonacci." (Toward a Global Science: Mining Civilizational Knowledge, p. 126) - Russ Cox, Sep 08 2021

Also sometimes called Hemachandra numbers.

Also sometimes called Lamé's sequence.

For a photograph of "Fibonacci"'s 1202 book, see the Leonardo of Pisa link below.

F(n+2) = number of binary sequences of length n that have no consecutive 0's.

F(n+2) = number of subsets of {1,2,...,n} that contain no consecutive integers.

F(n+1) = number of tilings of a 2 X n rectangle by 2 X 1 dominoes.

F(n+1) = number of matchings (i.e., Hosoya index) in a path graph on n vertices: F(5)=5 because the matchings of the path graph on the vertices A, B, C, D are the empty set, {AB}, {BC}, {CD} and {AB, CD}. - Emeric Deutsch, Jun 18 2001

F(n) = number of compositions of n+1 with no part equal to 1. [Cayley, Grimaldi]

Positive terms are the solutions to z = 2*x*y^4 + (x^2)*y^3 - 2*(x^3)*y^2 - y^5 - (x^4)*y + 2*y for x,y >= 0 (Ribenboim, page 193). When x=F(n), y=F(n + 1) and z > 0 then z=F(n + 1).

For Fibonacci search see Knuth, Vol. 3; Horowitz and Sahni; etc.

F(n) is the diagonal sum of the entries in Pascal's triangle at 45 degrees slope. - Amarnath Murthy, Dec 29 2001 (i.e., row sums of A030528, R. J. Mathar, Oct 28 2021)

F(n+1) is the number of perfect matchings in ladder graph L_n = P_2 X P_n. - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002

F(n+1) = number of (3412,132)-, (3412,213)- and (3412,321)-avoiding involutions in S_n.

This is also the Horadam sequence (0,1,1,1). - Ross La Haye, Aug 18 2003

An INVERT transform of A019590. INVERT([1,1,2,3,5,8,...]) gives A000129. INVERT([1,2,3,5,8,13,21,...]) gives A028859. - Antti Karttunen, Dec 12 2003

Number of meaningful differential operations of the k-th order on the space R^3. - Branko Malesevic, Mar 02 2004

F(n) = number of compositions of n-1 with no part greater than 2. Example: F(4) = 3 because we have 3 = 1+1+1 = 1+2 = 2+1.

F(n) = number of compositions of n into odd parts; e.g., F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling, Jun 22 2004

F(n) = number of binary words of length n beginning with 0 and having all runlengths odd; e.g., F(6) counts 010101, 010111, 010001, 011101, 011111, 000101, 000111, 000001. - Clark Kimberling, Jun 22 2004

The number of sequences (s(0),s(1),...,s(n)) such that 0 < s(i) < 5, |s(i)-s(i-1)|=1 and s(0)=1 is F(n+1); e.g., F(5+1) = 8 corresponds to 121212, 121232, 121234, 123212, 123232, 123234, 123432, 123434. - Clark Kimberling, Jun 22 2004 [corrected by Neven Juric, Jan 09 2009]

Likewise F(6+1) = 13 corresponds to these thirteen sequences with seven numbers: 1212121, 1212123, 1212321, 1212323, 1212343, 1232121, 1232123, 1232321, 1232323, 1232343, 1234321, 1234323, 1234343. - Neven Juric, Jan 09 2008

A relationship between F(n) and the Mandelbrot set is discussed in the link "Le nombre d'or dans l'ensemble de Mandelbrot" (in French). - Gerald McGarvey, Sep 19 2004

For n > 0, the continued fraction for F(2n-1)*phi = [F(2n); L(2n-1), L(2n-1), L(2n-1), ...] and the continued fraction for F(2n)*phi = [F(2n+1)-1; 1, L(2n)-2, 1, L(2n)-2, ...]. Also true: F(2n)*phi = [F(2n+1); -L(2n), L(2n), -L(2n), L(2n), ...] where L(i) is the i-th Lucas number (A000204). - Clark Kimberling, Nov 28 2004 [corrected by Hieronymus Fischer, Oct 20 2010]

For any nonzero number k, the continued fraction [4,4,...,4,k], which is n 4's and a single k, equals (F(3n) + k*F(3n+3))/(F(3n-3) + k*F(3n)). - Greg Dresden, Aug 07 2019

F(n+1) (for n >= 1) = number of permutations p of 1,2,3,...,n such that |k-p(k)| <= 1 for k=1,2,...,n. (For <= 2 and <= 3, see A002524 and A002526.) - Clark Kimberling, Nov 28 2004

The ratios F(n+1)/F(n) for n > 0 are the convergents to the simple continued fraction expansion of the golden section. - Jonathan Sondow, Dec 19 2004

Lengths of successive words (starting with a) under the substitution: {a -> ab, b -> a}. - Jeroen F.J. Laros, Jan 22 2005

The Fibonacci sequence, like any additive sequence, naturally tends to be geometric with common ratio not a rational power of 10; consequently, for a sufficiently large number of terms, Benford's law of first significant digit (i.e., first digit 1 <= d <= 9 occurring with probability log_10(d+1) - log_10(d)) holds. - Lekraj Beedassy, Apr 29 2005 (See Brown-Duncan, 1970. - N. J. A. Sloane, Feb 12 2017)

F(n+2) = Sum_{k=0..n} binomial(floor((n+k)/2),k), row sums of A046854. - Paul Barry, Mar 11 2003

Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - Mitch Harris, Dec 27 2005

F(n+1)/F(n) is also the Farey fraction sequence (see A097545 for explanation) for the golden ratio, which is the only number whose Farey fractions and continued fractions are the same. - Joshua Zucker, May 08 2006

a(n+2) is the number of paths through 2 plates of glass with n reflections (reflections occurring at plate/plate or plate/air interfaces). Cf. A006356-A006359. - Mitch Harris, Jul 06 2006

F(n+1) equals the number of downsets (i.e., decreasing subsets) of an n-element fence, i.e., an ordered set of height 1 on {1,2,...,n} with 1 > 2 < 3 > 4 < ... n and no other comparabilities. Alternatively, F(n+1) equals the number of subsets A of {1,2,...,n} with the property that, if an odd k is in A, then the adjacent elements of {1,2,...,n} belong to A, i.e., both k - 1 and k + 1 are in A (provided they are in {1,2,...,n}). - Brian Davey, Aug 25 2006

Number of Kekulé structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - Parthasarathy Nambi, Aug 22 2006

Inverse: With phi = (sqrt(5) + 1)/2, round(log_phi(sqrt((sqrt(5) a(n) + sqrt(5 a(n)^2 - 4))(sqrt(5) a(n) + sqrt(5 a(n)^2 + 4)))/2)) = n for n >= 3, obtained by rounding the arithmetic mean of the inverses given in A001519 and A001906. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007

A result of Jacobi from 1848 states that every symmetric matrix over a p.i.d. is congruent to a triple-diagonal matrix. Consider the maximal number T(n) of summands in the determinant of an n X n triple-diagonal matrix. This is the same as the number of summands in such a determinant in which the main-, sub- and superdiagonal elements are all nonzero. By expanding on the first row we see that the sequence of T(n)'s is the Fibonacci sequence without the initial stammer on the 1's. - Larry Gerstein (gerstein(AT)math.ucsb.edu), Mar 30 2007

Suppose psi=log(phi). We get the representation F(n)=(2/sqrt(5))*sinh(n*psi) if n is even; F(n)=(2/sqrt(5))*cosh(n*psi) if n is odd. There is a similar representation for Lucas numbers (A000032). Many Fibonacci formulas now easily follow from appropriate sinh and cosh formulas. For example: the de Moivre theorem (cosh(x)+sinh(x))^m = cosh(mx)+sinh(mx) produces L(n)^2 + 5F(n)^2 = 2L(2n) and L(n)F(n) = F(2n) (setting x=n*psi and m=2). - Hieronymus Fischer, Apr 18 2007

Inverse: floor(log_phi(sqrt(5)*F(n)) + 1/2) = n, for n > 1. Also for n > 0, floor((1/2)*log_phi(5*F(n)*F(n+1))) = n. Extension valid for integer n, except n=0,-1: floor((1/2)*sign(F(n)*F(n+1))*log_phi|5*F(n)*F(n+1)|) = n (where sign(x) = sign of x). - Hieronymus Fischer, May 02 2007

F(n+2) = the number of Khalimsky-continuous functions with a two-point codomain. - Shiva Samieinia (shiva(AT)math.su.se), Oct 04 2007

This is a_1(n) in the Doroslovacki reference.

Let phi = A001622 then phi^n = (1/phi)*a(n) + a(n+1). - Gary W. Adamson, Dec 15 2007

The sequence of first differences, F(n+1)-F(n), is essentially the same sequence: 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... - Colm Mulcahy, Mar 03 2008

Equals row sums of triangle A144152. - Gary W. Adamson, Sep 12 2008

Except for the initial term, the numerator of the convergents to the recursion x = 1/(x+1). - Cino Hilliard, Sep 15 2008

F(n) is the number of possible binary sequences of length n that obey the sequential construction rule: if last symbol is 0, add the complement (1); else add 0 or 1. Here 0,1 are metasymbols for any 2-valued symbol set. This rule has obvious similarities to JFJ Laros's rule, but is based on addition rather than substitution and creates a tree rather than a single sequence. - Ross Drewe, Oct 05 2008

F(n) = Product_{k=1..(n-1)/2} (1 + 4*cos^2 k*Pi/n), where terms = roots to the Fibonacci product polynomials, A152063. - Gary W. Adamson, Nov 22 2008

Fp == 5^((p-1)/2) mod p, p = prime [Schroeder, p. 90]. - Gary W. Adamson & Alexander R. Povolotsky, Feb 21 2009

A000032(n)^2 - 5*F(n)^2 = 4*(-1)^n. - Gary W. Adamson, Mar 11 2009

Output of Kasteleyn's formula for the number of perfect matchings of an m X n grid specializes to the Fibonacci sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009

(F(n),F(n+4)) satisfies the Diophantine equation: X^2 + Y^2 - 7XY = 9*(-1)^n. - Mohamed Bouhamida, Sep 06 2009

(F(n),F(n+2)) satisfies the Diophantine equation: X^2 + Y^2 - 3XY = (-1)^n. - Mohamed Bouhamida, Sep 08 2009

a(n+2) = A083662(A131577(n)). - Reinhard Zumkeller, Sep 26 2009

Difference between number of closed walks of length n+1 from a node on a pentagon and number of walks of length n+1 between two adjacent nodes on a pentagon. - Henry Bottomley, Feb 10 2010

F(n+1) = number of Motzkin paths of length n having exactly one weak ascent. A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps. Example: a(5)=5 because we have (HHHH), (HHU)D, (HUH)D, (UHH)D, and (UU)DD (the unique weak ascent is shown between parentheses; see A114690). - Emeric Deutsch, Mar 11 2010

(F(n-1) + F(n+1))^2 - 5*F(n-2)*F(n+2) = 9*(-1)^n. - Mohamed Bouhamida, Mar 31 2010

From the Pinter and Ziegler reference's abstract: authors "show that essentially the Fibonacci sequence is the unique binary recurrence which contains infinitely many three-term arithmetic progressions. A criterion for general linear recurrences having infinitely many three-term arithmetic progressions is also given." - Jonathan Vos Post, May 22 2010

F(n+1) = number of paths of length n starting at initial node on the path graph P_4. - Johannes W. Meijer, May 27 2010

F(k) = number of cyclotomic polynomials in denominator of generating function for number of ways to place k nonattacking queens on an n X n board. - Vaclav Kotesovec, Jun 07 2010

As n->oo, (a(n)/a(n-1) - a(n-1)/a(n)) tends to 1.0. Example: a(12)/a(11) - a(11)/a(12) = 144/89 - 89/144 = 0.99992197.... - Gary W. Adamson, Jul 16 2010

From Hieronymus Fischer, Oct 20 2010: (Start)

Fibonacci numbers are those numbers m such that m*phi is closer to an integer than k*phi for all k, 1 <= k < m. More formally: a(0)=0, a(1)=1, a(2)=1, a(n+1) = minimal m > a(n) such that m*phi is closer to an integer than a(n)*phi.

For all numbers 1 <= k < F(n), the inequality |k*phi-round(k*phi)| > |F(n)*phi-round(F(n)*phi)| holds.

F(n)*phi - round(F(n)*phi) = -((-phi)^(-n)), for n > 1.

Fract(1/2 + F(n)*phi) = 1/2 -(-phi)^(-n), for n > 1.

Fract(F(n)*phi) = (1/2)*(1 + (-1)^n) - (-phi)^(-n), n > 1.

Inverse: n = -log_phi |1/2 - fract(1/2 + F(n)*phi)|.

(End)

F(A001177(n)*k) mod n = 0, for any integer k. - Gary Detlefs, Nov 27 2010

F(n+k)^2 - F(n)^2 = F(k)*F(2n+k), for even k. - Gary Detlefs, Dec 04 2010

F(n+k)^2 + F(n)^2 = F(k)*F(2n+k), for odd k. - Gary Detlefs, Dec 04 2010

F(n) = round(phi*F(n-1)) for n > 1. - Joseph P. Shoulak, Jan 13 2012

For n > 0: a(n) = length of n-th row in Wythoff array A003603. - Reinhard Zumkeller, Jan 26 2012

From Bridget Tenner, Feb 22 2012: (Start)

The number of free permutations of [n].

The number of permutations of [n] for which s_k in supp(w) implies s_{k+-1} not in supp(w).

The number of permutations of [n] in which every decomposition into length(w) reflections is actually composed of simple reflections. (End)

The sequence F(n+1)^(1/n) is increasing. The sequence F(n+2)^(1/n) is decreasing. - Thomas Ordowski, Apr 19 2012

Two conjectures: For n > 1, F(n+2)^2 mod F(n+1)^2 = F(n)*F(n+1) - (-1)^n. For n > 0, (F(2n) + F(2n+2))^2 = F(4n+3) + Sum_{k = 2..2n} F(2k). - Alex Ratushnyak, May 06 2012

From Ravi Kumar Davala, Jan 30 2014: (Start)

Proof of Ratushnyak's first conjecture: For n > 1, F(n+2)^2 - F(n)*F(n+1) + (-1)^n = 2*F(n+1)^2.

Consider: F(n+2)^2 - F(n)*F(n+1) - 2*F(n+1)^2

= F(n+2)^2 - F(n+1)^2 - F(n+1)^2 - F(n)*F(n+1)

= (F(n+2) + F(n+1))*(F(n+2) - F(n+1)) - F(n+1)*(F(n+1) + F(n))

= F(n+3)*F(n) - F(n+1)*F(n+2) = -(-1)^n.

Proof of second conjecture: L(n) stands for Lucas number sequence from A000032.

Consider the fact that

L(2n+1)^2 = L(4n+2) - 2

(F(2n) + F(2n+2))^2 = F(4n+1) + F(4n+3) - 2

(F(2n) + F(2n+2))^2 = (Sum_{k = 2..2n} F(2k)) + F(4n+3).

(End)

The relationship: INVERT transform of (1,1,0,0,0,...) = (1, 2, 3, 5, 8, ...), while the INVERT transform of (1,0,1,0,1,0,1,...) = (1, 1, 2, 3, 5, 8, ...) is equivalent to: The numbers of compositions using parts 1 and 2 is equivalent to the numbers of compositions using parts == 1 (mod 2) (i.e., the odd integers). Generally, the numbers of compositions using parts 1 and k is equivalent to the numbers of compositions of (n+1) using parts 1 mod k. Cf. A000930 for k = 3 and A003269 for k = 4. Example: for k = 2, n = 4 we have the compositions (22; 211, 121; 112; 1111) = 5; but using parts 1 and 3 we have for n = 5: (311, 131, 113, 11111, 5) = 5. - Gary W. Adamson, Jul 05 2012

The sequence F(n) is the binomial transformation of the alternating sequence (-1)^(n-1)*F(n), whereas the sequence F(n+1) is the binomial transformation of the alternating sequence (-1)^n*F(n-1). Both of these facts follow easily from the equalities a(n;1)=F(n+1) and b(n;1)=F(n) where a(n;d) and b(n;d) are so-called "delta-Fibonacci" numbers as defined in comments to A014445 (see also the papers of Witula et al.). - Roman Witula, Jul 24 2012

F(n) is the number of different (n-1)-digit binary numbers such that all substrings of length > 1 have at least one digit equal to 1. Example: for n = 5 there are 8 binary numbers with n - 1 = 4 digits (1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111), only the F(n) = 5 numbers 1010, 1011, 1101, 1110 and 1111 have the desired property. - Hieronymus Fischer, Nov 30 2012

For positive n, F(n+1) equals the determinant of the n X n tridiagonal matrix with 1's along the main diagonal, i's along the superdiagonal and along the subdiagonal where i = sqrt(-1). Example: Det([1,i,0,0; i,1,i,0; 0,i,1,i; 0,0,i,1]) = F(4+1) = 5. - Philippe Deléham, Feb 24 2013

For n >= 1, number of compositions of n where there is a drop between every second pair of parts, starting with the first and second part; see example. Also, a(n+1) is the number of compositions where there is a drop between every second pair of parts, starting with the second and third part; see example. - Joerg Arndt, May 21 2013 [see the Hopkins/Tangboonduangjit reference for a proof, see also the Checa reference for alternative proofs and statistics]

Central terms of triangles in A162741 and A208245, n > 0. - Reinhard Zumkeller, Jul 28 2013

For n >= 4, F(n-1) is the number of simple permutations in the geometric grid class given in A226433. - Jay Pantone, Sep 08 2013

a(n) are the pentagon (not pentagonal) numbers because the algebraic degree 2 number rho(5) = 2*cos(Pi/5) = phi (golden section), the length ratio diagonal/side in a pentagon, has minimal polynomial C(5,x) = x^2 - x - 1 (see A187360, n=5), hence rho(5)^n = a(n-1)*1 + a(n)*rho(5), n >= 0, in the power basis of the algebraic number field Q(rho(5)). One needs a(-1) = 1 here. See also the P. Steinbach reference under A049310. - Wolfdieter Lang, Oct 01 2013

A010056(a(n)) = 1. - Reinhard Zumkeller, Oct 10 2013

Define F(-n) to be F(n) for n odd and -F(n) for n even. Then for all n and k, F(n+2k)^2 - F(n)^2 = F(n+k)*( F(n+3k) - F(n-k) ). - Charlie Marion, Dec 20 2013

( F(n), F(n+2k) ) satisfies the Diophantine equation: X^2 + Y^2 - L(2k)*X*Y = F(4k)^2*(-1)^n. This generalizes Bouhamida's comments dated Sep 06 2009 and Sep 08 2009. - Charlie Marion, Jan 07 2014

For any prime p there is an infinite periodic subsequence within F(n) divisible by p, that begins at index n = 0 with value 0, and its first nonzero term at n = A001602(i), and period k = A001602(i). Also see A236479. - Richard R. Forberg, Jan 26 2014

Range of row n of the circular Pascal array of order 5. - Shaun V. Ault, May 30 2014 [orig. Kicey-Klimko 2011, and observations by Glen Whitehead; more general work found in Ault-Kicey 2014]

Nonnegative range of the quintic polynomial 2*y - y^5 + 2*x*y^4 + x^2*y^3 - 2*x^3*y^2 - x^4*y with x, y >= 0, see Jones 1975. - Charles R Greathouse IV, Jun 01 2014

The expression round(1/(F(k+1)/F(n) + F(k)/F(n+1))), for n > 0, yields a Fibonacci sequence with k-1 leading zeros (with rounding 0.5 to 0). - Richard R. Forberg, Aug 04 2014

Conjecture: For n > 0, F(n) is the number of all admissible residue classes for which specific finite subsequences of the Collatz 3n + 1 function consists of n+2 terms. This has been verified for 0 < n < 51. For details see Links. - Mike Winkler, Oct 03 2014

a(4)=3 and a(6)=8 are the only Fibonacci numbers that are of the form prime+1. - Emmanuel Vantieghem, Oct 02 2014

a(1)=1=a(2), a(3)=2 are the only Fibonacci numbers that are of the form prime-1. - Emmanuel Vantieghem, Jun 07 2015

Any consecutive pair (m, k) of the Fibonacci sequence a(n) illustrates a fair equivalence between m miles and k kilometers. For instance, 8 miles ~ 13 km; 13 miles ~ 21 km. - Lekraj Beedassy, Oct 06 2014

a(n+1) counts closed walks on K_2, containing one loop on the other vertex. Equivalently the (1,1)entry of A^(n+1) where the adjacency matrix of digraph is A=(0,1; 1,1). - _David Neil McGrath, Oct 29 2014

a(n-1) counts closed walks on the graph G(1-vertex;l-loop,2-loop). - David Neil McGrath, Nov 26 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).

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)

F(n+1) equals the number of binary words of length n avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015

From Russell Jay Hendel, Apr 12 2015: (Start)

We prove Conjecture 1 of Rashid listed in the Formula section.

We use the following notation: F(n)=A000045(n), the Fibonacci numbers, and L(n) = A000032(n), the Lucas numbers. The fundamental Fibonacci-Lucas recursion asserts that G(n) = G(n-1) + G(n-2), with "L" or "F" replacing "G".

We need the following prerequisites which we label (A), (B), (C), (D). The prerequisites are formulas in the Koshy book listed in the References section. (A) F(m-1) + F(m+1) = L(m) (Koshy, p. 97, #32), (B) L(2m) + 2*(-1)^m = L(m)^2 (Koshy p. 97, #41), (C) F(m+k)*F(m-k) = (-1)^n*F(k)^2 (Koshy, p. 113, #24, Tagiuri's identity), and (D) F(n)^2 + F(n+1)^2 = F(2n+1) (Koshy, p. 97, #30).

We must also prove (E), L(n+2)*F(n-1) = F(2n+1)+2*(-1)^n. To prove (E), first note that by (A), proof of (E) is equivalent to proving that F(n+1)*F(n-1) + F(n+3)*F(n-1) = F(2n+1) + 2*(-1)^n. But by (C) with k=1, we have F(n+1)*F(n-1) = F(n)^2 + (-1)^n. Applying (C) again with k=2 and m=n+1, we have F(n+3)*F(n-1) = F(n+1) + (-1)^n. Adding these two applications of (C) together and using (D) we have F(n+1)*F(n-1) + F(n+3)*F(n-1) = F(n)^2 + F(n+1)^2 + 2*(-1)^n = F(2n+1) + 2(-1)^n, completing the proof of (E).

We now prove Conjecture 1. By (A) and the Fibonacci-Lucas recursion, we have F(2n+1) + F(2n+2) + F(2n+3) + F(2n+4) = (F(2n+1) + F(2n+3)) + (F(2n+2) + F(2n+4)) = L(2n+2) +L(2n+3) = L(2n+4). But then by (B), with m=2n+4, we have sqrt(L(2n+4) + 2(-1)^n) = L(n+2). Finally by (E), we have L(n+2)*F(n-1) = F(2n+1) + 2*(-1)^n. Dividing both sides by F(n-1), we have (F(2n+1) + 2*(-1)^n)/F(n-1) = L(n+2) = sqrt(F(2n+1) + F(2n+2) + F(2n+3) + F(2n+4) + 2(-1)^n), as required.

(End)

In Fibonacci's Liber Abaci the rabbit problem appears in the translation of L. E. Sigler on pp. 404-405, and a remark [27] on p. 637. - Wolfdieter Lang, Apr 17 2015

a(n) counts partially ordered partitions of (n-1) into parts 1,2,3 where only the order of adjacent 1's and 2's are unimportant. (See example.) - David Neil McGrath, Jul 27 2015

F(n) divides F(n*k). Proved by Marjorie Bicknell and Verner E Hoggatt Jr. - Juhani Heino, Aug 24 2015

F(n) is the number of UDU-equivalence classes of ballot paths of length n. Two ballot paths of length n with steps U = (1,1), D = (1,-1) are UDU-equivalent whenever the positions of UDU are the same in both paths. - Kostas Manes, Aug 25 2015

Cassini's identity F(2n+1) * F(2n+3) = F(2n+2)^2 + 1 is the basis for a geometrical paradox (or dissection fallacy) in A262342. - Jonathan Sondow, Oct 23 2015

For n >= 4, F(n) is the number of up-down words on alphabet {1,2,3} of length n-2. - Ran Pan, Nov 23 2015

F(n+2) is the number of terms in p(n), where p(n)/q(n) is the n-th convergent of the formal infinite continued fraction [a(0),a(1),...]; e.g., p(3) = a(0)a(1)a(2)a(3) + a(0)a(1) + a(0)a(3) + a(2)a(3) + 1 has F(5) terms. Also, F(n+1) is the number of terms in q(n). - Clark Kimberling, Dec 23 2015

F(n+1) (for n >= 1) is the permanent of an n X n matrix M with M(i,j)=1 if |i-j| <= 1 and 0 otherwise. - Dmitry Efimov, Jan 08 2016

A trapezoid has three sides of lengths in order F(n), F(n+2), F(n). For increasing n a very close approximation to the maximum area will have the fourth side equal to 2*F(n+1). For a trapezoid with lengths of sides in order F(n+2), F(n), F(n+2), the fourth side will be F(n+3). - J. M. Bergot, Mar 17 2016

(1) Join two triangles with lengths of sides L(n), F(n+3), L(n+2) and F(n+2), L(n+1), L(n+2) (where L(n)=A000032(n)) along the common side of length L(n+2) to create an irregular quadrilateral. Its area is approximately 5*F(2*n-1) - (F(2*n-7) - F(2*n-13))/5. (2) Join two triangles with lengths of sides L(n), F(n+2), F(n+3) and L(n+1), F(n+1), F(n+3) along the common side F(n+3) to form an irregular quadrilateral. Its area is approximately 4*F(2*n-1) - 2*(F(2*n-7) + F(2*n-18)). - J. M. Bergot, Apr 06 2016

From Clark Kimberling, Jun 13 2016: (Start)

Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*.

Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2, x}, g(3) = {3, 2x, x+1, x^2}, etc.

Let T(r) be the tree obtained by substituting r for x.

If a positive integer N is not a square and r = sqrt(N), then the number of (not necessarily distinct) integers in g(n) is A000045(n), for n >= 1. See A274142. (End)

Consider the partitions of n, with all summands initially listed in nonincreasing order. Freeze all the 1's in place and then allow all the other summands to change their order, without displacing any of the 1's. The resulting number of arrangements is a(n+1). - Gregory L. Simay, Jun 14 2016

Limit of the matrix power M^k shown in A163733, Sep 14 2016, as k->infinity results in a single column vector equal to the Fibonacci sequence. - Gary W. Adamson, Sep 19 2016

F(n) and Lucas numbers L(n), being related by the formulas F(n) = (F(n-1) + L(n-1))/2 and L(n) = 2 F(n+1) - F(n), are a typical pair of "autosequences" (see the link to OEIS Wiki). - Jean-François Alcover, Jun 10 2017

Also the number of independent vertex sets and vertex covers in the (n-2)-path graph. - Eric W. Weisstein, Sep 22 2017

Shifted numbers of {UD, DU, FD, DF}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - Sergey Kirgizov, Apr 08 2018

For n > 0, F(n) = the number of Markov equivalence classes with skeleton the path on n nodes. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - Liam Solus, Aug 23 2018

For n >= 2, also: number of terms in A032858 (every other base-3 digit is strictly smaller than its neighbors) with n-2 digits in base 3. - M. F. Hasler, Oct 05 2018

F(n+1) is the number of fixed points of the Foata transformation on S_n. - Kevin Long, Oct 17 2018

F(n+2) is the dimension of the Hecke algebra of type A_n with independent parameters (0,1,0,1,...) or (1,0,1,0,...). See Corollary 1.5 in the link "Hecke algebras with independent parameters". - Jia Huang, Jan 20 2019

The sequence is the second INVERT transform of (1, -1, 2, -3, 5, -8, 13, ...) and is the first sequence in an infinite set of successive INVERT transforms generated from (1, 0, 1, 0, 1, ...). Refer to the array shown in A073133. - Gary W. Adamson, Jul 16 2019

From Kai Wang, Dec 16 2019: (Start)

F(n*k)/F(k) = Sum_{i=0..n-1; j=0..n-1; i+2*j=n-1} (-1)^(j*(k-1))*L(k)^i*((i+j)!/(i!*j!)).

F((2*m+1)*k)/F(k) = Sum_{i=0..m-1} (-1)^(i*k)*L((2*m-2*i)*k) + (-1)^(m*k).

F(2*m*k)/F(k) = Sum_{i=0..m-1} (-1)^(i*k)*L((2*m-2*i-1)*k).

F(m+s)*F(n+r) - F(m+r)*F(n+s) = (-1)^(n+s)*F(m-n)*F(r-s).

F(m+r)*F(n+s) + F(m+s)*F(n+r) = (2*L(m+n+r+s) - (-1)^(n+s)*L(m-n)*L(r-s))/5.

L(m+r)*L(n+s) - 5*F(m+s)*F(n+r) = (-1)^(n+s)*L(m-n)*L(r-s).

L(m+r)*L(n+s) + 5*F(m+s)*F(n+r) = 2*L(m+n+r+s) + (-1)^(n+s)*5*F(m-n)*F(r-s).

L(m+r)*L(n+s) - L(m+s)*L(n+r) = (-1)^(n+s)*5*F(m-n)*F(r-s). (End)

F(n+1) is the number of permutations in S_n whose principal order ideals in the weak order are Boolean lattices. - Bridget Tenner, Jan 16 2020

F(n+1) is the number of permutations w in S_n that form Boolean intervals [s, w] in the weak order for every simple reflection s in the support of w. - Bridget Tenner, Jan 16 2020

F(n+1) is the number of subsets of {1,2,.,.,n} in which all differences between successive elements of subsets are odd. For example, for n = 6, F(7) = 13 and the 13 subsets are {6}, {1,6}, {3,6}, {5,6}, {2,3,6}, {2,5,6}, {4,5,6}, {1,2,3,6}, {1,2,5,6}, {1,4,5,6}, {3,4,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6}. For even differences between elements see Comment in A016116. - Enrique Navarrete, Jul 01 2020

F(n) is the number of subsets of {1,2,...,n} in which the smallest element of the subset equals the size of the subset (this type of subset is sometimes called extraordinary). For example, F(6) = 8 and the subsets are {1}, {2,3}, {2,4}, {2,5}, {3,4,5}, {2,6}, {3,4,6}, {3,5,6}. It is easy to see that these subsets follow the Fibonacci recursion F(n) = F(n-1) + F(n-2) since we get F(n) such subsets by keeping all F(n-1) subsets from the previous stage (in the example, the F(5)=5 subsets that don't include 6), and by adding one to all elements and appending an additional element n to each subset in F(n-2) subsets (in the example, by applying this to the F(4)=3 subsets {1}, {2,3}, {2,4} we obtain {2,6}, {3,4,6}, {3,5,6}). - Enrique Navarrete, Sep 28 2020

Named "série de Fibonacci" by Lucas (1877) after the Italian mathematician Fibonacci (Leonardo Bonacci, c. 1170 - c. 1240/50). In 1876 he named the sequence "série de Lamé" after the French mathematician Gabriel Lamé (1795 - 1870). - Amiram Eldar, Apr 16 2021

F(n) is the number of edge coverings of the path with n edges. - M. Farrokhi D. G., Sep 30 2021

LCM(F(m), F(n)) is a Fibonacci number if and only if either F(m) divides F(n) or F(n) divides F(m). - M. Farrokhi D. G., Sep 30 2021

Every nonunit positive rational number has at most one representation as the quotient of two Fibonacci numbers. - M. Farrokhi D. G., Sep 30 2021

The infinite sum F(n)/10^(n-1) for all natural numbers n is equal to 100/89. More generally, the sum of F(n)/(k^(n-1)) for all natural numbers n is equal to k^2/(k^2-k-1). Jonatan Djurachkovitch, Dec 31 2023

For n >= 1, number of compositions (c(1),c(2),...,c(k)) of n where c(1), c(3), c(5), ... are 1. To obtain such compositions K(n) of length n increase all parts c(2) by one in all of K(n-1) and prepend two parts 1 in all of K(n-2). - Joerg Arndt, Jan 05 2024

Cohn (1964) proved that a(12) = 12^2 is the only square in the sequence greater than a(1) = 1. - M. F. Hasler, Dec 18 2024

Product_{i=n-2..n+2} F(i) = F(n)^5 - F(n). For example, (F(4)F(5)F(6)F(7)F(8))=(3 * 5 * 8 * 13 * 21) = 8^5 - 8. - Jules Beauchamp, Apr 28 2025

F(n) is even iff n is a multiple of 3. - Stefano Spezia, Jul 06 2025

Multiplicative: If the canonical factorization of n into prime powers is the product of p^e(p) then sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1).

Sum_{d|n} 1/d^k is equal to sigma_k(n)/n^k. So sequences A017665-A017712 also give the numerators and denominators of sigma_k(n)/n^k for k = 1..24. The power sums sigma_k(n) are in sequences A000203 (this sequence) (k=1), A001157-A001160 (k=2,3,4,5), A013954-A013972 for k = 6,7,...,24. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 05 2001

A number n is abundant if sigma(n) > 2n (cf. A005101), perfect if sigma(n) = 2n (cf. A000396), deficient if sigma(n) < 2n (cf. A005100).

a(n) is the number of sublattices of index n in a generic 2-dimensional lattice. - Avi Peretz (njk(AT)netvision.net.il), Jan 29 2001 [In the language of group theory, a(n) is the number of index-n subgroups of Z x Z. - Jianing Song, Nov 05 2022]

The sublattices of index n are in one-to-one correspondence with matrices [a b; 0 d] with a>0, ad=n, b in [0..d-1]. The number of these is Sum_{d|n} d = sigma(n), which is a(n). A sublattice is primitive if gcd(a,b,d) = 1; the number of these is n * Product_{p|n} (1+1/p), which is A001615. [Cf. Grady reference.]

Sum of number of common divisors of n and m, where m runs from 1 to n. - Naohiro Nomoto, Jan 10 2004

a(n) is the cardinality of all extensions over Q_p with degree n in the algebraic closure of Q_p, where p>n. - Volker Schmitt (clamsi(AT)gmx.net), Nov 24 2004. Cf. A100976, A100977, A100978 (p-adic extensions).

Let s(n) = a(n-1) + a(n-2) - a(n-5) - a(n-7) + a(n-12) + a(n-15) - a(n-22) - a(n-26) + ..., then a(n) = s(n) if n is not pentagonal, i.e., n != (3 j^2 +- j)/2 (cf. A001318), and a(n) is instead s(n) - ((-1)^j)*n if n is pentagonal. - Gary W. Adamson, Oct 05 2008 [corrected Apr 27 2012 by William J. Keith based on Ewell and by Andrey Zabolotskiy, Apr 08 2022]

Write n as 2^k * d, where d is odd. Then a(n) is odd if and only if d is a square. - Jon Perry, Nov 08 2012

Also total number of parts in the partitions of n into equal parts. - Omar E. Pol, Jan 16 2013

Note that sigma(3^4) = 11^2. On the other hand, Kanold (1947) shows that the equation sigma(q^(p-1)) = b^p has no solutions b > 2, q prime, p odd prime. - N. J. A. Sloane, Dec 21 2013, based on postings to the Number Theory Mailing List by Vladimir Letsko and Luis H. Gallardo

Limit_{m->infinity} (Sum_{n=1..prime(m)} a(n)) / prime(m)^2 = zeta(2)/2 = Pi^2/12 (A072691). See more at A244583. - Richard R. Forberg, Jan 04 2015

a(n) + A000005(n) is an odd number iff n = 2m^2, m>=1. - Richard R. Forberg, Jan 15 2015

a(n) = a(n+1) for n = 14, 206, 957, 1334, 1364 (A002961). - Zak Seidov, May 03 2016

Equivalent to the Riemann hypothesis: a(n) < H(n) + exp(H(n))*log(H(n)), for all n>1, where H(n) is the n-th harmonic number (Jeffrey Lagarias). See A057641 for more details. - Ilya Gutkovskiy, Jul 05 2016

a(n) is the total number of even parts in the partitions of 2*n into equal parts. More generally, a(n) is the total number of parts congruent to 0 mod k in the partitions of k*n into equal parts (the comment dated Jan 16 2013 is the case for k = 1). - Omar E. Pol, Nov 18 2019

From Jianing Song, Nov 05 2022: (Start)

a(n) is also the number of order-n subgroups of C_n X C_n, where C_n is the cyclic group of order n. Proof: by the correspondence theorem in the group theory, there is a one-to-one correspondence between the order-n subgroups of C_n X C_n = (Z x Z)/(nZ x nZ) and the index-n subgroups of Z x Z containing nZ x nZ. But an index-n normal subgroup of a (multiplicative) group G contains {g^n : n in G} automatically. The desired result follows from the comment from Naohiro Nomoto above.

The number of subgroups of C_n X C_n that are isomorphic to C_n is A001615(n). (End)

If the canonical factorization of n into prime powers is Product p^e(p) then d(n) = Product (e(p) + 1). More generally, for k > 0, sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1) is the sum of the k-th powers of the divisors of n.

Number of ways to write n as n = x*y, 1 <= x <= n, 1 <= y <= n. For number of unordered solutions to x*y=n, see A038548.

Note that d(n) is not the number of Pythagorean triangles with radius of the inscribed circle equal to n (that is A078644). For number of primitive Pythagorean triangles having inradius n, see A068068(n).

Number of factors in the factorization of the polynomial x^n-1 over the integers. - T. D. Noe, Apr 16 2003

Also equal to the number of partitions p of n such that all the parts have the same cardinality, i.e., max(p)=min(p). - Giovanni Resta, Feb 06 2006

Equals A127093 as an infinite lower triangular matrix * the harmonic series, [1/1, 1/2, 1/3, ...]. - Gary W. Adamson, May 10 2007

For odd n, this is the number of partitions of n into consecutive integers. Proof: For n = 1, clearly true. For n = 2k + 1, k >= 1, map each (necessarily odd) divisor to such a partition as follows: For 1 and n, map k + (k+1) and n, respectively. For any remaining divisor d <= sqrt(n), map (n/d - (d-1)/2) + ... + (n/d - 1) + (n/d) + (n/d + 1) + ... + (n/d + (d-1)/2) {i.e., n/d plus (d-1)/2 pairs each summing to 2n/d}. For any remaining divisor d > sqrt(n), map ((d-1)/2 - (n/d - 1)) + ... + ((d-1)/2 - 1) + (d-1)/2 + (d+1)/2 + ((d+1)/2 + 1) + ... + ((d+1)/2 + (n/d - 1)) {i.e., n/d pairs each summing to d}. As all such partitions must be of one of the above forms, the 1-to-1 correspondence and proof is complete. - Rick L. Shepherd, Apr 20 2008

Number of subgroups of the cyclic group of order n. - Benoit Jubin, Apr 29 2008

Equals row sums of triangle A143319. - Gary W. Adamson, Aug 07 2008

Equals row sums of triangle A159934, equivalent to generating a(n) by convolving A000005 prefaced with a 1; (1, 1, 2, 2, 3, 2, ...) with the INVERTi transform of A000005, (A159933): (1, 1,-1, 0, -1, 2, ...). Example: a(6) = 4 = (1, 1, 2, 2, 3, 2) dot (2, -1, 0, -1, 1, 1) = (2, -1, 0, -2, 3, 2) = 4. - Gary W. Adamson, Apr 26 2009

Number of times n appears in an n X n multiplication table. - Dominick Cancilla, Aug 02 2010

Number of k >= 0 such that (k^2 + k*n + k)/(k + 1) is an integer. - Juri-Stepan Gerasimov, Oct 25 2015

The only numbers k such that tau(k) >= k/2 are 1,2,3,4,6,8,12. - Michael De Vlieger, Dec 14 2016

a(n) is also the number of partitions of 2*n into equal parts, minus the number of partitions of 2*n into consecutive parts. - Omar E. Pol, May 03 2017

From Tomohiro Yamada, Oct 27 2020: (Start)

Let k(n) = log d(n)*log log n/(log 2 * log n), then lim sup k(n) = 1 (Hardy and Wright, Chapter 18, Theorem 317) and k(n) <= k(6983776800) = 1.537939... (the constant A280235) for every n (Nicolas and Robin, 1983).

There exist infinitely many n such that d(n) = d(n+1) (Heath-Brown, 1984). The number of such integers n <= x is at least c*x/(log log x)^3 (Hildebrand, 1987) but at most O(x/sqrt(log log x)) (Erdős, Carl Pomerance and Sárközy, 1987). (End)

Number of 2D grids of n congruent rectangles with two different side lengths, in a rectangle, modulo rotation (cf. A038548 for squares instead of rectangles). Also number of ways to arrange n identical objects in a rectangle (NOT modulo rotation, cf. A038548 for modulo rotation); cf. A007425 and A140773 for the 3D case. - Manfred Boergens, Jun 08 2021

The constant quoted above from Nicolas and Robin, 6983776800 = 2^5 * 3^3 * 5^2 * 7 * 11 * 13 * 17 * 19, appears arbitrary, but interestingly equals 2 * A095849(36). That second factor is highly composite and deeply composite. - Hal M. Switkay, Aug 08 2025

Also referred to as T(n) or C(n+1, 2) or binomial(n+1, 2) (preferred).

Also generalized hexagonal numbers: n*(2*n-1), n=0, +-1, +-2, +-3, ... Generalized k-gonal numbers are second k-gonal numbers and positive terms of k-gonal numbers interleaved, k >= 5. In this case k = 6. - Omar E. Pol, Sep 13 2011 and Aug 04 2012

Number of edges in complete graph of order n+1, K_{n+1}.

Number of legal ways to insert a pair of parentheses in a string of n letters. E.g., there are 6 ways for three letters: (a)bc, (ab)c, (abc), a(b)c, a(bc), ab(c). Proof: there are C(n+2,2) ways to choose where the parentheses might go, but n + 1 of them are illegal because the parentheses are adjacent. Cf. A002415.

For n >= 1, a(n) is also the genus of a nonsingular curve of degree n+2, such as the Fermat curve x^(n+2) + y^(n+2) = 1. - Ahmed Fares (ahmedfares(AT)my_deja.com), Feb 21 2001

From Harnack's theorem (1876), the number of branches of a nonsingular curve of order n is bounded by a(n-1)+1, and the bound can be achieved. See also A152947. - Benoit Cloitre, Aug 29 2002. Corrected by Robert McLachlan, Aug 19 2024

Number of tiles in the set of double-n dominoes. - Scott A. Brown, Sep 24 2002

Number of ways a chain of n non-identical links can be broken up. This is based on a similar problem in the field of proteomics: the number of ways a peptide of n amino acid residues can be broken up in a mass spectrometer. In general, each amino acid has a different mass, so AB and BC would have different masses. - James A. Raymond, Apr 08 2003

Triangular numbers - odd numbers = shifted triangular numbers; 1, 3, 6, 10, 15, 21, ... - 1, 3, 5, 7, 9, 11, ... = 0, 0, 1, 3, 6, 10, ... - Xavier Acloque, Oct 31 2003 [Corrected by Derek Orr, May 05 2015]

Centered polygonal numbers are the result of [number of sides * A000217 + 1]. E.g., centered pentagonal numbers (1,6,16,31,...) = 5 * (0,1,3,6,...) + 1. Centered heptagonal numbers (1,8,22,43,...) = 7 * (0,1,3,6,...) + 1. - Xavier Acloque, Oct 31 2003

Maximum number of lines formed by the intersection of n+1 planes. - Ron R. King, Mar 29 2004

Number of permutations of [n] which avoid the pattern 132 and have exactly 1 descent. - Mike Zabrocki, Aug 26 2004

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

Number of ways two different numbers can be selected from the set {0,1,2,...,n} without repetition, or, number of ways two different numbers can be selected from the set {1,2,...,n} with repetition.

Conjecturally, 1, 6, 120 are the only numbers that are both triangular and factorial. - Christopher M. Tomaszewski (cmt1288(AT)comcast.net), Mar 30 2005

Binomial transform is {0, 1, 5, 18, 56, 160, 432, ...}, A001793 with one leading zero. - Philippe Deléham, Aug 02 2005

Each pair of neighboring terms adds to a perfect square. - Zak Seidov, Mar 21 2006

Number of transpositions in the symmetric group of n+1 letters, i.e., the number of permutations that leave all but two elements fixed. - Geoffrey Critzer, Jun 23 2006

With rho(n):=exp(i*2*Pi/n) (an n-th root of 1) one has, for n >= 1, rho(n)^a(n) = (-1)^(n+1). Just use the triviality a(2*k+1) == 0 (mod (2*k+1)) and a(2*k) == k (mod (2*k)).

a(n) is the number of terms in the expansion of (a_1 + a_2 + a_3)^(n-1). - Sergio Falcon, Feb 12 2007

a(n+1) is the number of terms in the complete homogeneous symmetric polynomial of degree n in 2 variables. - Richard Barnes, Sep 06 2017

The number of distinct handshakes in a room with n+1 people. - Mohammad K. Azarian, Apr 12 2007 [corrected, Joerg Arndt, Jan 18 2016]

Equal to the rank (minimal cardinality of a generating set) of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, May 03 2007

a(n) gives the total number of triangles found when cevians are drawn from a single vertex on a triangle to the side opposite that vertex, where n = the number of cevians drawn+1. For instance, with 1 cevian drawn, n = 1+1 = 2 and a(n)= 2*(2+1)/2 = 3 so there is a total of 3 triangles in the figure. If 2 cevians are drawn from one point to the opposite side, then n = 1+2 = 3 and a(n) = 3*(3+1)/2 = 6 so there is a total of 6 triangles in the figure. - Noah Priluck (npriluck(AT)gmail.com), Apr 30 2007

For n >= 1, a(n) is the number of ways in which n-1 can be written as a sum of three nonnegative integers if representations differing in the order of the terms are considered to be different. In other words, for n >= 1, a(n) is the number of nonnegative integral solutions of the equation x + y + z = n-1. - Amarnath Murthy, Apr 22 2001 (edited by Robert A. Beeler)

a(n) is the number of levels with energy n + 3/2 (in units of h*f0, with Planck's constant h and the oscillator frequency f0) of the three-dimensional isotropic harmonic quantum oscillator. See the comment by A. Murthy above: n = n1 + n2 + n3 with positive integers and ordered. Proof from the o.g.f. See the A. Messiah reference. - Wolfdieter Lang, Jun 29 2007

From Hieronymus Fischer, Aug 06 2007: (Start)

Numbers m >= 0 such that round(sqrt(2m+1)) - round(sqrt(2m)) = 1.

Numbers m >= 0 such that ceiling(2*sqrt(2m+1)) - 1 = 1 + floor(2*sqrt(2m)).

Numbers m >= 0 such that fract(sqrt(2m+1)) > 1/2 and fract(sqrt(2m)) < 1/2, where fract(x) is the fractional part of x (i.e., x - floor(x), x >= 0). (End)

If Y and Z are 3-blocks of an n-set X, then, for n >= 6, a(n-1) is the number of (n-2)-subsets of X intersecting both Y and Z. - Milan Janjic, Nov 09 2007

Equals row sums of triangle A143320, n > 0. - Gary W. Adamson, Aug 07 2008

a(n) is also an even perfect number in A000396 iff n is a Mersenne prime A000668. - Omar E. Pol, Sep 05 2008. Unnecessary assumption removed and clarified by Rick L. Shepherd, Apr 14 2025

Equals row sums of triangle A152204. - Gary W. Adamson, Nov 29 2008

The number of matches played in a round robin tournament: n*(n-1)/2 gives the number of matches needed for n players. Everyone plays against everyone else exactly once. - Georg Wrede (georg(AT)iki.fi), Dec 18 2008

-a(n+1) = E(2)*binomial(n+2,2) (n >= 0) where E(n) are the Euler numbers in the enumeration A122045. Viewed this way, a(n) is the special case k=2 in the sequence of diagonals in the triangle A153641. - Peter Luschny, Jan 06 2009

Equivalent to the first differences of successive tetrahedral numbers. See A000292. - Jeremy Cahill (jcahill(AT)inbox.com), Apr 15 2009

The general formula for alternating sums of powers is in terms of the Swiss-Knife polynomials P(n,x) A153641 2^(-n-1)(P(n,1)-(-1)^k P(n,2k+1)). Thus a(k) = |2^(-3)(P(2,1)-(-1)^k P(2,2k+1))|. - Peter Luschny, Jul 12 2009

a(n) is the smallest number > a(n-1) such that gcd(n,a(n)) = gcd(n,a(n-1)). If n is odd this gcd is n; if n is even it is n/2. - Franklin T. Adams-Watters, Aug 06 2009

Partial sums of A001477. - Juri-Stepan Gerasimov, Jan 25 2010. [A-number corrected by Omar E. Pol, Jun 05 2012]

The numbers along the right edge of Floyd's triangle are 1, 3, 6, 10, 15, .... - Paul Muljadi, Jan 25 2010

From Charlie Marion, Dec 03 2010: (Start)

More generally, a(2k+1) == j*(2j-1) (mod 2k+2j+1) and

a(2k) == [-k + 2j*(j-1)] (mod 2k+2j).

Column sums of:

1 3 5 7 9 ...

1 3 5 ...

1 ...

...............

---------------

1 3 6 10 15 ...

Sum_{n>=1} 1/a(n)^2 = 4*Pi^2/3-12 = 12 less than the volume of a sphere with radius Pi^(1/3).

(End)

A004201(a(n)) = A000290(n); A004202(a(n)) = A002378(n). - Reinhard Zumkeller, Feb 12 2011

1/a(n+1), n >= 0, has e.g.f. -2*(1+x-exp(x))/x^2, and o.g.f. 2*(x+(1-x)*log(1-x))/x^2 (see the Stephen Crowley formula line). -1/(2*a(n+1)) is the z-sequence for the Sheffer triangle of the coefficients of the Bernoulli polynomials A196838/A196839. - Wolfdieter Lang, Oct 26 2011

From Charlie Marion, Feb 23 2012: (Start)

a(n) + a(A002315(k)*n + A001108(k+1)) = (A001653(k+1)*n + A001109(k+1))^2. For k=0 we obtain a(n) + a(n+1) = (n+1)^2 (identity added by N. J. A. Sloane on Feb 19 2004).

a(n) + a(A002315(k)*n - A055997(k+1)) = (A001653(k+1)*n - A001109(k))^2.

(End)

Plot the three points (0,0), (a(n), a(n+1)), (a(n+1), a(n+2)) to form a triangle. The area will be a(n+1)/2. - J. M. Bergot, May 04 2012

The sum of four consecutive triangular numbers, beginning with a(n)=n*(n+1)/2, minus 2 is 2*(n+2)^2. a(n)*a(n+2)/2 = a(a(n+1)-1). - J. M. Bergot, May 17 2012

(a(n)*a(n+3) - a(n+1)*a(n+2))*(a(n+1)*a(n+4) - a(n+2)*a(n+3))/8 = a((n^2+5*n+4)/2). - J. M. Bergot, May 18 2012

a(n)*a(n+1) + a(n+2)*a(n+3) + 3 = a(n^2 + 4*n + 6). - J. M. Bergot, May 22 2012

In general, a(n)*a(n+1) + a(n+k)*a(n+k+1) + a(k-1)*a(k) = a(n^2 + (k+2)*n + k*(k+1)). - Charlie Marion, Sep 11 2012

a(n)*a(n+3) + a(n+1)*a(n+2) = a(n^2 + 4*n + 2). - J. M. Bergot, May 22 2012

In general, a(n)*a(n+k) + a(n+1)*a(n+k-1) = a(n^2 + (k+1)*n + k-1). - Charlie Marion, Sep 11 2012

a(n)*a(n+2) + a(n+1)*a(n+3) = a(n^2 + 4*n + 3). - J. M. Bergot, May 22 2012

Three points (a(n),a(n+1)), (a(n+1),a(n)) and (a(n+2),a(n+3)) form a triangle with area 4*a(n+1). - J. M. Bergot, May 23 2012

a(n) + a(n+k) = (n+k)^2 - (k^2 + (2n-1)*k -2n)/2. For k=1 we obtain a(n) + a(n+1) = (n+1)^2 (see below). - Charlie Marion, Oct 02 2012

In n-space we can define a(n-1) nontrivial orthogonal projections. For example, in 3-space there are a(2)=3 (namely point onto line, point onto plane, line onto plane). - Douglas Latimer, Dec 17 2012

From James East, Jan 08 2013: (Start)

For n >= 1, a(n) is equal to the rank (minimal cardinality of a generating set) and idempotent rank (minimal cardinality of an idempotent generating set) of the semigroup P_n\S_n, where P_n and S_n denote the partition monoid and symmetric group on [n].

For n >= 3, a(n-1) is equal to the rank and idempotent rank of the semigroup T_n\S_n, where T_n and S_n denote the full transformation semigroup and symmetric group on [n].

(End)

For n >= 3, a(n) is equal to the rank and idempotent rank of the semigroup PT_n\S_n, where PT_n and S_n denote the partial transformation semigroup and symmetric group on [n]. - James East, Jan 15 2013

Conjecture: For n > 0, there is always a prime between A000217(n) and A000217(n+1). Sequence A065383 has the first 1000 of these primes. - Ivan N. Ianakiev, Mar 11 2013

The formula, a(n)*a(n+4k+2)/2 + a(k) = a(a(n+2k+1) - (k^2+(k+1)^2)), is a generalization of the formula a(n)*a(n+2)/2 = a(a(n+1)-1) in Bergot's comment dated May 17 2012. - Charlie Marion, Mar 28 2013

The series Sum_{k>=1} 1/a(k) = 2, given in a formula below by Jon Perry, Jul 13 2003, has partial sums 2*n/(n+1) (telescopic sum) = A022998(n)/A026741(n+1). - Wolfdieter Lang, Apr 09 2013

For odd m = 2k+1, we have the recurrence a(m*n + k) = m^2*a(n) + a(k). Corollary: If number T is in the sequence then so is 9*T+1. - Lekraj Beedassy, May 29 2013

Euler, in Section 87 of the Opera Postuma, shows that whenever T is a triangular number then 9*T + 1, 25*T + 3, 49*T + 6 and 81*T + 10 are also triangular numbers. In general, if T is a triangular number then (2*k + 1)^2*T + k*(k + 1)/2 is also a triangular number. - Peter Bala, Jan 05 2015

Using 1/b and 1/(b+2) will give a Pythagorean triangle with sides 2*b + 2, b^2 + 2*b, and b^2 + 2*b + 2. Set b=n-1 to give a triangle with sides of lengths 2*n,n^2-1, and n^2 + 1. One-fourth the perimeter = a(n) for n > 1. - J. M. Bergot, Jul 24 2013

a(n) = A028896(n)/6, where A028896(n) = s(n) - s(n-1) are the first differences of s(n) = n^3 + 3*n^2 + 2*n - 8. s(n) can be interpreted as the sum of the 12 edge lengths plus the sum of the 6 face areas plus the volume of an n X (n-1) X (n-2) rectangular prism. - J. M. Bergot, Aug 13 2013

Dimension of orthogonal group O(n+1). - Eric M. Schmidt, Sep 08 2013

Number of positive roots in the root system of type A_n (for n > 0). - Tom Edgar, Nov 05 2013

A formula for the r-th successive summation of k, for k = 1 to n, is binomial(n+r,r+1) [H. W. Gould]. - Gary Detlefs, Jan 02 2014

Also the alternating row sums of A095831. Also the alternating row sums of A055461, for n >= 1. - Omar E. Pol, Jan 26 2014

For n >= 3, a(n-2) is the number of permutations of 1,2,...,n with the distribution of up (1) - down (0) elements 0...011 (n-3 zeros), or, the same, a(n-2) is up-down coefficient {n,3} (see comment in A060351). - Vladimir Shevelev, Feb 14 2014

a(n) is the dimension of the vector space of symmetric n X n matrices. - Derek Orr, Mar 29 2014

Non-vanishing subdiagonal of A132440^2/2, aside from the initial zero. First subdiagonal of unsigned A238363. Cf. A130534 for relations to colored forests, disposition of flags on flagpoles, and colorings of the vertices of complete graphs. - Tom Copeland, Apr 05 2014

The number of Sidon subsets of {1,...,n+1} of size 2. - Carl Najafi, Apr 27 2014

Number of factors in the definition of the Vandermonde determinant V(x_1,x_2,...,x_n) = Product_{1 <= i < k <= n} x_i - x_k. - Tom Copeland, Apr 27 2014

Number of weak compositions of n into three parts. - Robert A. Beeler, May 20 2014

Suppose a bag contains a(n) red marbles and a(n+1) blue marbles, where a(n), a(n+1) are consecutive triangular numbers. Then, for n > 0, the probability of choosing two marbles at random and getting two red or two blue is 1/2. In general, for k > 2, let b(0) = 0, b(1) = 1 and, for n > 1, b(n) = (k-1)*b(n-1) - b(n-2) + 1. Suppose, for n > 0, a bag contains b(n) red marbles and b(n+1) blue marbles. Then the probability of choosing two marbles at random and getting two red or two blue is (k-1)/(k+1). See also A027941, A061278, A089817, A053142, A092521. - Charlie Marion, Nov 03 2014

Let O(n) be the oblong number n(n+1) = A002378 and S(n) the square number n^2 = A000290(n). Then a(4n) = O(3n) - O(n), a(4n+1) = S(3n+1) - S(n), a(4n+2) = S(3n+2) - S(n+1) and a(4n+3) = O(3n+2) - O(n). - Charlie Marion, Feb 21 2015

Consider the partition of the natural numbers into parts from the set S=(1,2,3,...,n). The length (order) of the signature of the resulting sequence is given by the triangular numbers. E.g., for n=10, the signature length is 55. - David Neil McGrath, May 05 2015

a(n) counts the partitions of (n-1) unlabeled objects into three (3) parts (labeled a,b,c), e.g., a(5)=15 for (n-1)=4. These are (aaaa),(bbbb),(cccc),(aaab),(aaac),(aabb),(aacc),(aabc),(abbc),(abcc),(abbb),(accc),(bbcc),(bccc),(bbbc). - David Neil McGrath, May 21 2015

Conjecture: the sequence is the genus/deficiency of the sinusoidal spirals of index n which are algebraic curves. The value 0 corresponds to the case of the Bernoulli Lemniscate n=2. So the formula conjectured is (n-1)(n-2)/2. - Wolfgang Tintemann, Aug 02 2015

Conjecture: Let m be any positive integer. Then, for each n = 1,2,3,... the set {Sum_{k=s..t} 1/k^m: 1 <= s <= t <= n} has cardinality a(n) = n*(n+1)/2; in other words, all the sums Sum_{k=s..t} 1/k^m with 1 <= s <= t are pairwise distinct. (I have checked this conjecture via a computer and found no counterexample.) - Zhi-Wei Sun, Sep 09 2015

The Pisano period lengths of reading the sequence modulo m seem to be A022998(m). - R. J. Mathar, Nov 29 2015

For n >= 1, a(n) is the number of compositions of n+4 into n parts avoiding the part 2. - Milan Janjic, Jan 07 2016

In this sequence only 3 is prime. - Fabian Kopp, Jan 09 2016

Suppose you are playing Bulgarian Solitaire (see A242424 and Chamberland's and Gardner's books) and, for n > 0, you are starting with a single pile of a(n) cards. Then the number of operations needed to reach the fixed state {n, n-1,...,1} is a(n-1). For example, {6}->{5,1}->{4,2}->{3,2,1}. - Charlie Marion, Jan 14 2016

Numbers k such that 8k + 1 is a square. - Juri-Stepan Gerasimov, Apr 09 2016

Every perfect cube is the difference of the squares of two consecutive triangular numbers. 1^2-0^2 = 1^3, 3^2-1^2 = 2^3, 6^2-3^2 = 3^3. - Miquel Cerda, Jun 26 2016

For n > 1, a(n) = tau_n(k*) where tau_n(k) is the number of ordered n-factorizations of k and k* is the square of a prime. For example, tau_3(4) = tau_3(9) = tau_3(25) = tau_3(49) = 6 (see A007425) since the number of divisors of 4, 9, 25, and 49's divisors is 6, and a(3) = 6. - Melvin Peralta, Aug 29 2016

In an (n+1)-dimensional hypercube, number of two-dimensional faces congruent with a vertex (see also A001788). - Stanislav Sykora, Oct 23 2016

Generalizations of the familiar formulas, a(n) + a(n+1) = (n+1)^2 (Feb 19 2004) and a(n)^2 + a(n+1)^2 = a((n+1)^2) (Nov 22 2006), follow: a(n) + a(n+2k-1) + 4a(k-1) = (n+k)^2 + 6a(k-1) and a(n)^2 + a(n+2k-1)^2 + (4a(k-1))^2 + 3a(k-1) = a((n+k)^2 + 6a(k-1)). - Charlie Marion, Nov 27 2016

a(n) is also the greatest possible number of diagonals in a polyhedron with n+4 vertices. - Vladimir Letsko, Dec 19 2016

For n > 0, 2^5 * (binomial(n+1,2))^2 represents the first integer in a sum of 2*(2*n + 1)^2 consecutive integers that equals (2*n + 1)^6. - Patrick J. McNab, Dec 25 2016

Does not satisfy Benford's law (cf. Ross, 2012). - N. J. A. Sloane, Feb 12 2017

Number of ordered triples (a,b,c) of positive integers not larger than n such that a+b+c = 2n+1. - Aviel Livay, Feb 13 2017

Number of inequivalent tetrahedral face colorings using at most n colors so that no color appears only once. - David Nacin, Feb 22 2017

Also the Wiener index of the complete graph K_{n+1}. - Eric W. Weisstein, Sep 07 2017

Number of intersections between the Bernstein polynomials of degree n. - Eric Desbiaux, Apr 01 2018

a(n) is the area of a triangle with vertices at (1,1), (n+1,n+2), and ((n+1)^2, (n+2)^2). - Art Baker, Dec 06 2018

For n > 0, a(n) is the smallest k > 0 such that n divides numerator of (1/a(1) + 1/a(2) + ... + 1/a(n-1) + 1/k). It should be noted that 1/1 + 1/3 + 1/6 + ... + 2/(n(n+1)) = 2n/(n+1). - Thomas Ordowski, Aug 04 2019

Upper bound of the number of lines in an n-homogeneous supersolvable line arrangement (see Theorem 1.1 in Dimca). - Stefano Spezia, Oct 04 2019

For n > 0, a(n+1) is the number of lattice points on a triangular grid with side length n. - Wesley Ivan Hurt, Aug 12 2020

From Michael Chu, May 04 2022: (Start)

Maximum number of distinct nonempty substrings of a string of length n.

Maximum cardinality of the sumset A+A, where A is a set of n numbers. (End)

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

Suppose two rows, each consisting of n evenly spaced dots, are drawn in parallel. Suppose we bijectively draw lines between the dots of the two rows. For n >= 1, a(n - 1) is the maximal possible number of intersections between the lines. Equivalently, the maximal number of inversions in a permutation of [n]. - Sela Fried, Apr 18 2023

The following equation complements the generalization in Bala's Comment (Jan 05 2015). (2k + 1)^2*a(n) + a(k) = a((2k + 1)*n + k). - Charlie Marion, Aug 28 2023

a(n) + a(n+k) + a(k-1) + (k-1)*n = (n+k)^2. For k = 1, we have a(n) + a(n+1) = (n+1)^2. - Charlie Marion, Nov 17 2023

a(n+1)/3 is the expected number of steps to escape from a linear row of n positions starting at a random location and randomly performing steps -1 or +1 with equal probability. - Hugo Pfoertner, Jul 22 2025

a(n+1) is the number of nonnegative integer solutions to p + q + r = n. By Sylvester's law of inertia, it is also the number of congruence classes of real symmetric n-by-n matrices or equivalently, the number of symmetric bilinear forms on a real n-dimensional vector space. - Paawan Jethva, Jul 24 2025

Number of elements in a reduced residue system modulo n.

Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre, Oct 12 2002

Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity. (A primitive n-th root x is such that x^k is not equal to 1 for k = 1, 2, ..., n - 1, but x^n = 1.) - Lekraj Beedassy, Mar 31 2005

Also number of complex Dirichlet characters modulo n; Sum_{k=1..n} a(k) is asymptotic to (3/Pi^2)*n^2. - Steven Finch, Feb 16 2006

a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk, Sep 02 2006, corrected Sep 27 2006

a(p) = p - 1 for prime p. a(n) is even for n > 2. For n > 2, a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk, Jan 25 2007

Number of automorphisms of the cyclic group of order n. - Benoit Jubin, Aug 09 2008

a(n+2) equals the number of palindromic Sturmian words of length n which are "bispecial", prefix or suffix of two Sturmian words of length n + 1. - Fred Lunnon, Sep 05 2010

Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n) - 1. - Lei Zhou, Feb 28 2012

If m has k prime factors, (p_1, p_2, ..., p_k), then phi(m*n) = (Product_{i=1..k} phi (p_i*n))/phi(n)^(k-1). For example, phi(42*n) = phi(2*n)*phi(3*n)*phi(7*n)/phi(n)^2. - Gary Detlefs, Apr 21 2012

Sum_{n>=1} a(n)/n! = 1.954085357876006213144... This sum is referenced in Plouffe's inverter. - Alexander R. Povolotsky, Feb 02 2013 (see A336334. - Hugo Pfoertner, Jul 22 2020)

The order of the multiplicative group of units modulo n. - Michael Somos, Aug 27 2013

A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 30 2016

From Eric Desbiaux, Jan 01 2017: (Start)

a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle A054533).

a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377, which are the Jordan functions J_2, J_3, J_4, respectively). (End)

For n > 1, a(n) appears to be equal to the number of semi-meander solutions for n with top arches containing exactly 2 mountain ranges and exactly 2 arches of length 1. - Roger Ford, Oct 11 2017

a(n) is the minimum dimension of a lattice able to generate, via cut-and-project, the quasilattice whose diffraction pattern features n-fold rotational symmetry. The case n=15 is the first n > 1 in which the following simpler definition fails: "a(n) is the minimum dimension of a lattice with n-fold rotational symmetry". - Felix Flicker, Nov 08 2017

Number of cyclic Latin squares of order n with the first row in ascending order. - Eduard I. Vatutin, Nov 01 2020

a(n) is the number of rational numbers p/q >= 0 (in lowest terms) such that p + q = n. - Rémy Sigrist, Jan 17 2021

From Richard L. Ollerton, May 08 2021: (Start)

Formulas for the numerous OEIS entries involving Dirichlet convolution of a(n) and some sequence h(n) can be derived using the following (n >= 1):

Sum_{d|n} phi(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k)) [see P. H. van der Kamp link] = Sum_{d|n} h(d)*phi(n/d) = Sum_{k=1..n} h(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). Similarly,

Sum_{d|n} phi(d)*h(d) = Sum_{k=1..n} h(n/gcd(n,k)) = Sum_{k=1..n} h(gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).

More generally,

Sum_{d|n} h(d) = Sum_{k=1..n} h(gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))/phi(n/gcd(n,k)).

In particular, for sequences involving the Möbius transform:

Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where mu = A008683.

Use of gcd(n,k)*lcm(n,k) = n*k and phi(gcd(n,k))*phi(lcm(n,k)) = phi(n)*phi(k) provide further variations. (End)

From Richard L. Ollerton, Nov 07 2021: (Start)

Formulas for products corresponding to the sums above may found using the substitution h(n) = log(f(n)) where f(n) > 0 (for example, cf. formulas for the sum A018804 and product A067911 of gcd(n,k)):

Product_{d|n} f(n/d)^phi(d) = Product_{k=1..n} f(gcd(n,k)) = Product_{d|n} f(d)^phi(n/d) = Product_{k=1..n} f(n/gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),

Product_{d|n} f(d)^phi(d) = Product_{k=1..n} f(n/gcd(n,k)) = Product_{k=1..n} f(gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),

Product_{d|n} f(d) = Product_{k=1..n} f(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(1/phi(n/gcd(n,k))),

Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))), where mu = A008683. (End)

a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - Radoslaw Zak, Nov 29 2021

These were formerly sometimes called Segner numbers.

A very large number of combinatorial interpretations are known - see references, esp. R. P. Stanley, "Catalan Numbers", Cambridge University Press, 2015. This is probably the longest entry in the OEIS, and rightly so.

The solution to Schröder's first problem: number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]

Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - Joerg Arndt, Jul 11 2011

Noncrossing partitions are partitions of genus 0. - Robert Coquereaux, Feb 13 2024

a(n-1) is the number of ways of expressing an n-cycle (123...n) in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_iA000272. - Joerg Arndt and Greg Stevenson, Jul 11 2011

a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. - Wolfdieter Lang, Aug 07 2007

As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - M. F. Hasler, Feb 22 2012

Shifts one place left when convolved with itself.

For n >= 1, a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001

Number of ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then the number of ways of forming n chords is given by (2n-1)!! = (2n)!/(n!*2^n) = A001147(n).)

Arises in Schubert calculus - see Sottile reference.

Inverse Euler transform of sequence is A022553.

With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry, Jul 18 2003

The Hankel transforms of this sequence or of this sequence with the first term omitted give A000012 = 1, 1, 1, 1, 1, 1, ...; example: Det([1, 1, 2, 5; 1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132]) = 1 and Det([1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132; 14, 42, 132, 429]) = 1. - Philippe Deléham, Mar 04 2004

a(n) equals the sum of squares of terms in row n of triangle A053121, which is formed from successive self-convolutions of the Catalan sequence. - Paul D. Hanna, Apr 23 2005

Also coefficients of the Mandelbrot polynomial M iterated an infinite number of times. Examples: M(0) = 0 = 0*c^0 = [0], M(1) = c = c^1 + 0*c^0 = [1 0], M(2) = c^2 + c = c^2 + c^1 + 0*c^0 = [1 1 0], M(3) = (c^2 + c)^2 + c = [0 1 1 2 1], ... ... M(5) = [0 1 1 2 5 14 26 44 69 94 114 116 94 60 28 8 1], ... - Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005

The multiplicity with which a prime p divides C_n can be determined by first expressing n+1 in base p. For p=2, the multiplicity is the number of 1 digits minus 1. For p an odd prime, count all digits greater than (p+1)/2; also count digits equal to (p+1)/2 unless final; and count digits equal to (p-1)/2 if not final and the next digit is counted. For example, n=62, n+1 = 223_5, so C_62 is not divisible by 5. n=63, n+1 = 224_5, so 5^3 | C_63. - Franklin T. Adams-Watters, Feb 08 2006

Koshy and Salmassi give an elementary proof that the only prime Catalan numbers are a(2) = 2 and a(3) = 5. Is the only semiprime Catalan number a(4) = 14? - Jonathan Vos Post, Mar 06 2006

The answer is yes. Using the formula C_n = binomial(2n,n)/(n+1), it is immediately clear that C_n can have no prime factor greater than 2n. For n >= 7, C_n > (2n)^2, so it cannot be a semiprime. Given that the Catalan numbers grow exponentially, the above consideration implies that the number of prime divisors of C_n, counted with multiplicity, must grow without limit. The number of distinct prime divisors must also grow without limit, but this is more difficult. Any prime between n+1 and 2n (exclusive) must divide C_n. That the number of such primes grows without limit follows from the prime number theorem. - Franklin T. Adams-Watters, Apr 14 2006

The number of ways to place n indistinguishable balls in n numbered boxes B1,...,Bn such that at most a total of k balls are placed in boxes B1,...,Bk for k=1,...,n. For example, a(3)=5 since there are 5 ways to distribute 3 balls among 3 boxes such that (i) box 1 gets at most 1 ball and (ii) box 1 and box 2 together get at most 2 balls:(O)(O)(O), (O)()(OO), ()(OO)(O), ()(O)(OO), ()()(OOO). - Dennis P. Walsh, Dec 04 2006

a(n) is also the order of the semigroup of order-decreasing and order-preserving full transformations (of an n-element chain) - now known as the Catalan monoid. - Abdullahi Umar, Aug 25 2008

a(n) is the number of trivial representations in the direct product of 2n spinor (the smallest) representations of the group SU(2) (A(1)). - Rutger Boels (boels(AT)nbi.dk), Aug 26 2008

The invert transform appears to converge to the Catalan numbers when applied infinitely many times to any starting sequence. - Mats Granvik, Gary W. Adamson and Roger L. Bagula, Sep 09 2008, Sep 12 2008

Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008

Starting with offset 1 = row sums of triangle A154559. - Gary W. Adamson, Jan 11 2009

C(n) is the degree of the Grassmannian G(1,n+1): the set of lines in (n+1)-dimensional projective space, or the set of planes through the origin in (n+2)-dimensional affine space. The Grassmannian is considered a subset of N-dimensional projective space, N = binomial(n+2,2) - 1. If we choose 2n general (n-1)-planes in projective (n+1)-space, then there are C(n) lines that meet all of them. - Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009

Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84, ...) convolved with Fine numbers, A000957: (1, 0, 1, 2, 6, 18, ...). a(6) = 132 = (1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. - Gary W. Adamson, May 01 2009

Convolved with A032443: (1, 3, 11, 42, 163, ...) = powers of 4, A000302: (1, 4, 16, ...). - Gary W. Adamson, May 15 2009

Sum_{k>=1} C(k-1)/2^(2k-1) = 1. The k-th term in the summation is the probability that a random walk on the integers (beginning at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. - Geoffrey Critzer, Sep 12 2009

C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009

Leonhard Euler used the formula C(n) = Product_{i=3..n} (4*i-10)/(i-1) in his 'Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne' and computes by recursion C(n+2) for n = 1..8. (Berlin, 4th September 1751, in a letter to Goldbach.) - Peter Luschny, Mar 13 2010

Let A179277 = A(x). Then C(x) is satisfied by A(x)/A(x^2). - Gary W. Adamson, Jul 07 2010

a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - Christian Stump, Nov 02 2010

From Matthew Vandermast, Nov 22 2010: (Start)

Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions: 1. No two colors are chosen the same positive number of times. 2. For any two colors (c, d) that are chosen at least once, color c is chosen more times than color d iff color c appears more times in the original set than color d.

If the second requirement is lifted, the number of acceptable ways equals A000110(n+1). See related comments for A016098, A085082. (End)

Deutsch and Sagan prove the Catalan number C_n is odd if and only if n = 2^a - 1 for some nonnegative integer a. Lin proves for every odd Catalan number C_n, we have C_n == 1 (mod 4). - Jonathan Vos Post, Dec 09 2010

a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} such that f(1)=1 and for all n >= 1 f(n+1) <= f(n)+1. For a nice bijection between this set of functions and the set of length 2n Dyck words, see page 333 of the Fxtbook (see link below). - Geoffrey Critzer, Dec 16 2010

Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see A000984). - N. J. A. Sloane, Dec 10 2011

Number of permutations in S(n) for which length equals depth. - Bridget Tenner, Feb 22 2012

a(n) is also the number of standard Young tableau of shape (n,n). - Thotsaporn Thanatipanonda, Feb 25 2012

a(n) is the number of binary sequences of length 2n+1 in which the number of ones first exceed the number of zeros at entry 2n+1. See the example below in the example section. - Dennis P. Walsh, Apr 11 2012

Number of binary necklaces of length 2*n+1 containing n 1's (or, by symmetry, 0's). All these are Lyndon words and their representatives (as cyclic maxima) are the binary Dyck words. - Joerg Arndt, Nov 12 2012

Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - Jon Perry, Nov 16 2012

a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps come in 2 colors. Example: a(4)=14 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 8 paths of shape HHH, 2 paths of shape UHD, 2 paths of shape UDH, and 2 paths of shape HUD. - José Luis Ramírez Ramírez, Jan 16 2013

If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - Gary Detlefs, Feb 20 2013

Conjecture: For any positive integer n, the polynomial Sum_{k=0..n} a(k)*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013

a(n) is the size of the Jones monoid on 2n points (cf. A225798). - James Mitchell, Jul 28 2013

For 0 < p < 1, define f(p) = Sum_{n>=0} a(n)*(p*(1-p))^n, then f(p) = min{1/p, 1/(1-p)}, so f(p) reaches its maximum value 2 at p = 0.5, and p*f(p) is constant 1 for 0.5 <= p < 1. - Bob Selcoe, Nov 16 2013 [Corrected by Jianing Song, May 21 2021]

No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013

From Alexander Adamchuk, Dec 27 2013: (Start)

Prime p divides a((p+1)/2) for p > 3. See A120303(n) = Largest prime factor of Catalan number.

Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.80613.. = A121839.

Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See A002390 = Decimal expansion of natural logarithm of golden ratio.

3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = A161581(n) = A006480(n) / ((n+1)^2*(n+2)), where A006480(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End)

For a relation to the inviscid Burgers's, or Hopf, equation, see A001764. - Tom Copeland, Feb 15 2014

From Fung Lam, May 01 2014: (Start)

One class of generalized Catalan numbers can be defined by g.f. A(x) = (1-sqrt(1-q*4*x*(1-(q-1)*x)))/(2*q*x) with nonzero parameter q. Recurrence: (n+3)*a(n+2) -2*q*(2*n+3)*a(n+1) +4*q*(q-1)*n*a(n) = 0 with a(0)=1, a(1)=1.

Asymptotic approximation for q >= 1: a(n) ~ (2*q+2*sqrt(q))^n*sqrt(2*q*(1+sqrt(q))) /sqrt(4*q^2*Pi*n^3).

For q <= -1, the g.f. defines signed sequences with asymptotic approximation: a(n) ~ Re(sqrt(2*q*(1+sqrt(q)))*(2*q+2*sqrt(q))^n) / sqrt(q^2*Pi*n^3), where Re denotes the real part. Due to Stokes' phenomena, accuracy of the asymptotic approximation deteriorates at/near certain values of n.

Special cases are A000108 (q=1), A068764 to A068772 (q=2 to 10), A240880 (q=-3).

(End)

Number of sequences [s(0), s(1), ..., s(n)] with s(n)=0, Sum_{j=0..n} s(j) = n, and Sum_{j=0..k} s(j)-1 >= 0 for k < n-1 (and necessarily Sum_{j=0..n-1} s(j)-1 = 0). These are the branching sequences of the (ordered) trees with n non-root nodes, see example. - Joerg Arndt, Jun 30 2014

Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - Joerg Arndt, Jul 01 2014

a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 132. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014

In a one-dimensional medium with elastic scattering (zig-zag walk), first recurrence after 2n+1 scattering events has the probability C(n)/2^(2n+1). - Joachim Wuttke, Sep 11 2014

The o.g.f. C(x) = (1 - sqrt(1-4x))/2, for the Catalan numbers, with comp. inverse Cinv(x) = x*(1-x) and the functions P(x) = x / (1 + t*x) and its inverse Pinv(x,t) = -P(-x,t) = x / (1 - t*x) form a group under composition that generates or interpolates among many classic arrays, such as the Motzkin (Riordan, A005043), Fibonacci (A000045), and Fine (A000957) numbers and polynomials (A030528), and enumerating arrays for Motzkin, Dyck, and Łukasiewicz lattice paths and different types of trees and non-crossing partitions (A091867, connected to sums of the refined Narayana numbers A134264). - Tom Copeland, Nov 04 2014

Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015

The Catalan number series A000108(n+3), offset n=0, gives Hankel transform revealing the square pyramidal numbers starting at 5, A000330(n+2), offset n=0 (empirical observation). - Tony Foster III, Sep 05 2016

Hankel transforms of the Catalan numbers with the first 2, 4, and 5 terms omitted give A001477, A006858, and A091962, respectively, without the first 2 terms in all cases. More generally, the Hankel transform of the Catalan numbers with the first k terms omitted is H_k(n) = Product_{j=1..k-1} Product_{i=1..j} (2*n+j+i)/(j+i) [see Cigler (2011), Eq. (1.14) and references therein]; together they form the array A078920/A123352/A368025. - Andrey Zabolotskiy, Oct 13 2016

Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. See S. J. Miller, ed., 2015, p. 5. - N. J. A. Sloane, Feb 09 2017

Coefficients of the generating series associated to the Magmatic and Dendriform operadic algebras. Cf. p. 422 and 435 of the Loday et al. paper. - Tom Copeland, Jul 08 2018

Let M_n be the n X n matrix with M_n(i,j) = binomial(i+j-1,2j-2); then det(M_n) = a(n). - Tony Foster III, Aug 30 2018

Also the number of Catalan trees, or planted plane trees (Bona, 2015, p. 299, Theorem 4.6.3). - N. J. A. Sloane, Dec 25 2018

Number of coalescent histories for a caterpillar species tree and a matching caterpillar gene tree with n+1 leaves (Rosenberg 2007, Corollary 3.5). - Noah A Rosenberg, Jan 28 2019

Finding solutions of eps*x^2+x-1 = 0 for eps small, that is, writing x = Sum_{n>=0} x_{n}*eps^n and expanding, one finds x = 1 - eps + 2*eps^2 - 5*eps^3 + 14*eps^3 - 42*eps^4 + ... with x_{n} = (-1)^n*C(n). Further, letting x = 1/y and expanding y about 0 to find large roots, that is, y = Sum_{n>=1} y_{n}*eps^n, one finds y = 0 - eps + eps^2 - 2*eps^3 + 5*eps^3 - ... with y_{n} = (-1)^n*C(n-1). - Derek Orr, Mar 15 2019

Permutations of length n that produce a bipartite permutation graph of order n [see Knuth (1973), Busch (2006), Golumbic and Trenk (2004)]. - Elise Anderson, R. M. Argus, Caitlin Owens, Tessa Stevens, Jun 27 2019

For n > 0, a random selection of n + 1 objects (the minimum number ensuring one pair by the pigeonhole principle) from n distinct pairs of indistinguishable objects contains only one pair with probability 2^(n-1)/a(n) = b(n-1)/A098597(n), where b is the 0-offset sequence with the terms of A120777 repeated (1,1,4,4,8,8,64,64,128,128,...). E.g., randomly selecting 6 socks from 5 pairs that are black, blue, brown, green, and white, results in only one pair of the same color with probability 2^(5-1)/a(5) = 16/42 = 8/21 = b(4)/A098597(5). - Rick L. Shepherd, Sep 02 2019

See Haran & Tabachnikov link for a video discussing Conway-Coxeter friezes. The Conway-Coxeter friezes with n nontrivial rows are generated by the counts of triangles at each vertex in the triangulations of regular n-gons, of which there are a(n). - Charles R Greathouse IV, Sep 28 2019

For connections to knot theory and scattering amplitudes from Feynman diagrams, see Broadhurst and Kreimer, and Todorov. Eqn. 6.12 on p. 130 of Bessis et al. becomes, after scaling, -12g * r_0(-y/(12g)) = (1-sqrt(1-4y))/2, the o.g.f. (expressed as a Taylor series in Eqn. 7.22 in 12gx) given for the Catalan numbers in Copeland's (Sep 30 2011) formula below. (See also Mizera p. 34, Balduf pp. 79-80, Keitel and Bartosch.) - Tom Copeland, Nov 17 2019

Number of permutations in S_n whose principal order ideals in the weak order are modular lattices. - Bridget Tenner, Jan 16 2020

Number of permutations in S_n whose principal order ideals in the weak order are distributive lattices. - Bridget Tenner, Jan 16 2020

Legendre gives the following formula for computing the square root modulo 2^m:

sqrt(1 + 8*a) mod 2^m = (1 + 4*a*Sum_{i=0..m-4} C(i)*(-2*a)^i) mod 2^m

as cited by L. D. Dickson, History of the Theory of Numbers, Vol. 1, 207-208. - Peter Schorn, Feb 11 2020

a(n) is the number of length n permutations sorted to the identity by a consecutive-132-avoiding stack followed by a classical-21-avoiding stack. - Kai Zheng, Aug 28 2020

Number of non-crossing partitions of a 2*n-set with n blocks of size 2. Also number of non-crossing partitions of a 2*n-set with n+1 blocks of size at most 3, and without cyclical adjacencies. The two partitions can be mapped by rotated Kreweras bijection. - Yuchun Ji, Jan 18 2021

Named by Riordan (1968, and earlier in Mathematical Reviews, 1948 and 1964) after the French and Belgian mathematician Eugène Charles Catalan (1814-1894) (see Pak, 2014). - Amiram Eldar, Apr 15 2021

For n >= 1, a(n-1) is the number of interpretations of x^n is an algebra where power-associativity is not assumed. For example, for n = 4 there are a(3) = 5 interpretations: x(x(xx)), x((xx)x), (xx)(xx), (x(xx))x, ((xx)x)x. See the link "Non-associate powers and a functional equation" from I. M. H. Etherington and the page "Nonassociative Product" from Eric Weisstein's World of Mathematics for detailed information. See also A001190 for the case where multiplication is commutative. - Jianing Song, Apr 29 2022

Number of states in the transition diagram associated with the Laplacian system over the complete graph K_N, corresponding to ordered initial conditions x_1 < x_2 < ... < x_N. - Andrea Arlette España, Nov 06 2022

a(n) is the number of 132-avoiding stabilized-interval-free permutations of size n+1. - Juan B. Gil, Jun 22 2023

Number of rooted polyominoes composed of n triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {3,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024

a(n) is the number of extremely lucky Stirling permutations of order n; i.e., the number of Stirling permutations of order n that have exactly n lucky cars. (see Colmenarejo et al. reference) - Bridget Tenner, Apr 16 2024

Also number of nonnegative solutions to b + 2c + 3d + 4e + ... = n and the number of nonnegative solutions to 2c + 3d + 4e + ... <= n. - Henry Bottomley, Apr 17 2001

a(n) is also the number of conjugacy classes in the symmetric group S_n (and the number of irreducible representations of S_n).

Also the number of rooted trees with n+1 nodes and height at most 2.

Coincides with the sequence of numbers of nilpotent conjugacy classes in the Lie algebras gl(n). A006950, A015128 and this sequence together cover the nilpotent conjugacy classes in the classical A,B,C,D series of Lie algebras. - Alexander Elashvili, Sep 08 2003

Number of distinct Abelian groups of order p^n, where p is prime (the number is independent of p). - Lekraj Beedassy, Oct 16 2004

Number of graphs on n vertices that do not contain P3 as an induced subgraph. - Washington Bomfim, May 10 2005

Numbers of terms to be added when expanding the n-th derivative of 1/f(x). - Thomas Baruchel, Nov 07 2005

Sequence agrees with expansion of Molien series for symmetric group S_n up to the term in x^n. - Maurice D. Craig (towenaar(AT)optusnet.com.au), Oct 30 2006

Also the number of nonnegative integer solutions to x_1 + x_2 + x_3 + ... + x_n = n such that n >= x_1 >= x_2 >= x_3 >= ... >= x_n >= 0, because by letting y_k = x_k - x_(k+1) >= 0 (where 0 < k < n) we get y_1 + 2y_2 + 3y_3 + ... + (n-1)y_(n-1) + nx_n = n. - Werner Grundlingh (wgrundlingh(AT)gmail.com), Mar 14 2007

Let P(z) := Sum_{j>=0} b_j z^j, b_0 != 0. Then 1/P(z) = Sum_{j>=0} c_j z^j, where the c_j must be computed from the infinite triangular system b_0 c_0 = 1, b_0 c_1 + b_1 c_0 = 0 and so on (Cauchy products of the coefficients set to zero). The n-th partition number arises as the number of terms in the numerator of the expression for c_n: The coefficient c_n of the inverted power series is a fraction with b_0^(n+1) in the denominator and in its numerator having a(n) products of n coefficients b_i each. The partitions may be read off from the indices of the b_i. - Peter C. Heinig (algorithms(AT)gmx.de), Apr 09 2007

A sequence of positive integers p = p_1 ... p_k is a descending partition of the positive integer n if p_1 + ... + p_k = n and p_1 >= ... >= p_k. If formally needed p_j = 0 is appended to p for j > k. Let P_n denote the set of these partition for some n >= 1. Then a(n) = 1 + Sum_{p in P_n} floor((p_1-1)/(p_2+1)). (Cf. A000065, where the formula reduces to the sum.) Proof in Kelleher and O'Sullivan (2009). For example a(6) = 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 2 + 5 = 11. - Peter Luschny, Oct 24 2010

Let n = Sum( k_(p_m) p_m ) = k_1 + 2k_2 + 5k_5 + 7k_7 + ..., where p_m is the m-th generalized pentagonal number (A001318). Then a(n) is the sum over all such pentagonal partitions of n of (-1)^(k_5+k_7 + k_22 + ...) ( k_1 + k_2 + k_5 + ...)! /( k_1! k_2! k_5! ...), where the exponent of (-1) is the sum of all the k's corresponding to even-indexed GPN's. - Jerome Malenfant, Feb 14 2011

From Jerome Malenfant, Feb 14 2011: (Start)

The matrix of a(n) values

a(0)

a(1) a(0)

a(2) a(1) a(0)

a(3) a(2) a(1) a(0)

....

a(n) a(n-1) a(n-2) ... a(0)

is the inverse of the matrix

1

-1 1

-1 -1 1

0 -1 -1 1

....

-d_n -d_(n-1) -d_(n-2) ... -d_1 1

where d_q = (-1)^(m+1) if q = m(3m-1)/2 = the m-th generalized pentagonal number (A001318), = 0 otherwise. (End)

Let k > 0 be an integer, and let i_1, i_2, ..., i_k be distinct integers such that 1 <= i_1 < i_2 < ... < i_k. Then, equivalently, a(n) equals the number of partitions of N = n + i_1 + i_2 + ... + i_k in which each i_j (1 <= j <= k) appears as a part at least once. To see this, note that the partitions of N of this class must be in 1-to-1 correspondence with the partitions of n, since N - i_1 - i_2 - ... - i_k = n. - L. Edson Jeffery, Apr 16 2011

a(n) is the number of distinct degree sequences over all free trees having n + 2 nodes. Take a partition of the integer n, add 1 to each part and append as many 1's as needed so that the total is 2n + 2. Now we have a degree sequence of a tree with n + 2 nodes. Example: The partition 3 + 2 + 1 = 6 corresponds to the degree sequence {4, 3, 2, 1, 1, 1, 1, 1} of a tree with 8 vertices. - Geoffrey Critzer, Apr 16 2011

a(n) is number of distinct characteristic polynomials among n! of permutations matrices size n X n. - Artur Jasinski, Oct 24 2011

Conjecture: starting with offset 1 represents the numbers of ordered compositions of n using the signed (++--++...) terms of A001318 starting (1, 2, -5, -7, 12, 15, ...). - Gary W. Adamson, Apr 04 2013 (this is true by the pentagonal number theorem, Joerg Arndt, Apr 08 2013)

a(n) is also number of terms in expansion of the n-th derivative of log(f(x)). In Mathematica notation: Table[Length[Together[f[x]^n * D[Log[f[x]], {x, n}]]], {n, 1, 20}]. - Vaclav Kotesovec, Jun 21 2013

Conjecture: No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013

Partitions of n that contain a part p are the partitions of n - p. Thus, number of partitions of m*n - r that include k*n as a part is A000041(h*n-r), where h = m - k >= 0, n >= 2, 0 <= r < n; see A111295 as an example. - Clark Kimberling, Mar 03 2014

a(n) is the number of compositions of n into positive parts avoiding the pattern [1, 2]. - Bob Selcoe, Jul 08 2014

Conjecture: For any j there exists k such that all primes p <= A000040(j) are factors of one or more a(n) <= a(k). Growth of this coverage is slow and irregular. k = 1067 covers the first 102 primes, thus slower than A000027. - Richard R. Forberg, Dec 08 2014

a(n) is the number of nilpotent conjugacy classes in the order-preserving, order-decreasing and (order-preserving and order-decreasing) injective transformation semigroups. - Ugbene Ifeanyichukwu, Jun 03 2015

Define a segmented partition a(n,k, ) to be a partition of n with exactly k parts, with s(j) parts t(j) identical to each other and distinct from all the other parts. Note that n >= k, j <= k, 0 <= s(j) <= k, s(1)t(1) + ... + s(j)t(j) = n and s(1) + ... + s(j) = k. Then there are up to a(k) segmented partitions of n with exactly k parts. - Gregory L. Simay, Nov 08 2015

(End)

From Gregory L. Simay, Nov 09 2015: (Start)

The polynomials for a(n, k, ) have degree j-1.

a(n, k, ) = 1 if n = 0 mod k, = 0 otherwise

a(rn, rk, ) = a(n, k, )

a(n odd, k, ) = 0

Established results can be recast in terms of segmented partitions:

For j(j+1)/2 <= n < (j+1)(j+2)/2, A000009(n) = a(n, 1, <1>) + ... + a(n, j, ), j < n

a(n, k, ) = a(n - j(j-1)/2, k)

(End)

a(10^20) was computed using the NIST Arb package. It has 11140086260 digits and its head and tail sections are 18381765...88091448. See the Johansson 2015 link. - Stanislav Sykora, Feb 01 2016

Satisfies Benford's law [Anderson-Rolen-Stoehr, 2011]. - N. J. A. Sloane, Feb 08 2017

The partition function p(n) is log-concave for all n>25 [DeSalvo-Pak, 2014]. - Michel Marcus, Apr 30 2019

a(n) is also the dimension of the n-th cohomology of the infinite real Grassmannian with coefficients in Z/2. - Luuk Stehouwer, Jun 06 2021

Number of equivalence relations on n unlabeled nodes. - Lorenzo Sauras Altuzarra, Jun 13 2022

Equivalently, number of idempotent mappings f from a set X of n elements into itself (i.e., satisfying f o f = f) up to permutation (i.e., f~f' :<=> There is a permutation sigma in Sym(X) such that f' o sigma = sigma o f). - Philip Turecek, Apr 17 2023

Conjecture: Each integer n > 2 different from 6 can be written as a sum of finitely many numbers of the form a(k) + 2 (k > 0) with no summand dividing another. This has been verified for n <= 7140. - Zhi-Wei Sun, May 16 2023

a(n) is also the number of partitions of n*(n+3)/2 into n distinct parts. - David García Herrero, Aug 20 2024

a(n) is also the number of non-isomorphic sigma algebras on {1,...,n}. A000110(n) counts all sigma algebras on {1,...,n}. Every sigma algebra on a finite set X is exactly the collection of all unions of its atoms (its minimal nonempty members), and those atoms partition X. An isomorphism of sigma algebras must map atoms to atoms, so the isomorphism class of a sigma algebra is determined by the multiset of its atom-sizes, which is an integer partition of n. - Matthew Azar, Jul 18 2025

2^0 = 1 is the only odd power of 2.

Number of subsets of an n-set.

There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670.

This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.]

Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003

a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.

Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences.

With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. Wilson

Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004

Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.]

Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.

The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.

The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).

The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005

With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005

The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.

The first differences are the sequence itself. - Alexandre Wajnberg and Eric Angelini, Sep 07 2005

a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006

Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006

For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007

Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008

a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008

2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008

a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008

Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008

A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1); examples for Jacobsthal A001045 and successive differences: A092808, A094359, A140505. a(n) = A000079 leads to 2, 1, 8, 4, 32, 16, ... = A135520. - Paul Curtz, Jan 05 2009

This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009

a(n) = a(n-1)-th even natural number (A005843) for n > 1. - Jaroslav Krizek, Apr 25 2009

For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009

Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009

Catalan transform of A099087. - R. J. Mathar, Jun 29 2009

a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009

Or, phi(n) is equal to the number of perfect partitions of n. - Juri-Stepan Gerasimov, Oct 10 2009

These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009

A064614(a(n)) = A000244(n) and A064614(m) < A000244(n) for m < a(n). - Reinhard Zumkeller, Feb 08 2010

a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010

a(n) is the smallest proper multiple of a(n-1). - Dominick Cancilla, Aug 09 2010

The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2*A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010

Records in the number of prime factors. - Juri-Stepan Gerasimov, Mar 12 2011

Row sums of A152538. - Gary W. Adamson, Dec 10 2008

A078719(a(n)) = 1; A006667(a(n)) = 0. - Reinhard Zumkeller, Oct 08 2011

The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011

Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011

The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011

a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012

A204455(k) = 1 if and only if k is in this sequence. - Wolfdieter Lang, Feb 04 2012

For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012

First differences of A000225. - Omar E. Pol, Feb 19 2013

This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013

a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013

Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013

More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013

Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013

Numbers n such that sigma(2n) = 2n + sigma(n). - Jahangeer Kholdi, Nov 23 2013

a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013

Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013

A072219(a(n)) = 1. - Reinhard Zumkeller, Feb 20 2014

a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014

If x = A083420(n), y = a(n+1) and z = A087289(n), then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014

The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014

The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014

a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014

Numbers n such that sigma(n) = sigma(2n) - phi(4n). - Farideh Firoozbakht, Aug 14 2014

This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014

a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014

a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015

b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015

a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015

a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015

Subsequence of A028982 (the squares or twice squares sequence). - Timothy L. Tiffin, Jul 18 2016

A000120(a(n)) = 1. A000265(a(n)) = 1. A000593(a(n)) = 1. - Juri-Stepan Gerasimov, Aug 16 2016

Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016

Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016

Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017

Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017

Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017

Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018

The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018

k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019

Solutions to the equation Phi(2n + 2*Phi(2n)) = 2n. - M. Farrokhi D. G., Jan 03 2020

a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020

a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021

For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - Greg Dresden and Bora Bursalı, Aug 31 2023