cp's OEIS Frontend

Or, odd primes p such that -1 is not a square mod p, i.e., the Legendre symbol (-1/p) = -1. [LeVeque I, p. 66]. - N. J. A. Sloane, Jun 28 2008

Primes which are not the sum of two squares, see the comment in A022544. - Artur Jasinski, Nov 15 2006

Natural primes which are also Gaussian primes. (It is a common error to refer to this sequence as "the Gaussian primes".)

Inert rational primes in the field Q(sqrt(-1)). - N. J. A. Sloane, Dec 25 2017

Numbers n such that the product of coefficients of (2n)-th cyclotomic polynomial equals -1. - Benoit Cloitre, Oct 22 2002

For p and q both belonging to the sequence, exactly one of the congruences x^2 = p (mod q), x^2 = q (mod p) is solvable, according to Gauss reciprocity law. - Lekraj Beedassy, Jul 17 2003

Also primes p that divide L((p-1)/2) or L((p+1)/2), where L(n) = A000032(n), the Lucas numbers. Union of A122869 and A122870. - Alexander Adamchuk, Sep 16 2006

Also odd primes p that divide ((p-1)!! + 1) or ((p-2)!! + 1). - Alexander Adamchuk, Nov 30 2006

Also odd primes p that divide ((p-1)!! - 1) or ((p-2)!! - 1). - Alexander Adamchuk, Apr 18 2007

This sequence is a proper subset of the set of the absolute values of negative fundamental discriminants (A003657). - Paul Muljadi, Mar 29 2008

Bernard Frénicle de Bessy discovered that such primes cannot be the hypotenuse of a Pythagorean triangle in opposition to primes of the form 4*n+1 (see A002144). - after Paul Curtz, Sep 10 2008

A079261(a(n)) = 1; complement of A145395. - Reinhard Zumkeller, Oct 12 2008

Subsequence of A007970. - Reinhard Zumkeller, Jun 18 2011

A151763(a(n)) = -1.

Primes p such that p XOR 2 = p - 2. Brad Clardy, Oct 25 2011 (Misleading in the sense that this is a formula for the super-sequence A004767. - R. J. Mathar, Jul 28 2014)

It appears that each term of A004767 is the mean of two terms of this subsequence of primes therein; cf. A245203. - M. F. Hasler, Jul 13 2014

Numbers n > 2 such that ((n-2)!!)^2 == 1 (mod n). - Thomas Ordowski, Jul 24 2016

Odd numbers n > 1 such that ((n-1)!!)^2 == 1 (mod n). - Thomas Ordowski, Jul 25 2016

Primes p such that (p-2)!! == (p-3)!! (mod p). - Thomas Ordowski, Jul 28 2016

See Granville and Martin for a discussion of the relative numbers of primes of the form 4k+1 and 4k+3. - Editors, May 01 2017

Sometimes referred to as Blum primes for their connection to A016105 and the Blum Blum Shub generator. - Charles R Greathouse IV, Jun 14 2018

Conjecture: a(n) for n > 4 can be written as a sum of 3 primes of the form 4k+1, which would imply that primes of the form 4k+3 >= 23 can be decomposed into a sum of 6 nonzero squares. - Thomas Scheuerle, Feb 09 2023

Number of spanning trees in complete graph K_n on n labeled nodes.

Robert Castelo, Jan 06 2001, observes that n^(n-2) is also the number of transitive subtree acyclic digraphs on n-1 vertices.

a(n) is also the number of ways of expressing an n-cycle in the symmetric group S_n as a product of n-1 transpositions, see example. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 12 2001

Also counts parking functions, critical configurations of the chip firing game, allowable pairs sorted by a priority queue [Hamel].

The parking functions of length n can be described as all permutations of all words [d(1),d(2), ..., d(n)] where 1 <= d(k) <= k; see example. There are (n+1)^(n-1) = a(n+1) parking functions of length n. - Joerg Arndt, Jul 15 2014

a(n+1) is the number of endofunctions with no cycles of length > 1; number of forests of rooted labeled trees on n vertices. - Mitch Harris, Jul 06 2006

a(n) is also the number of nilpotent partial bijections (of an n-element set). Equivalently, the number of nilpotents in the partial symmetric semigroup, P sub n. - Abdullahi Umar, Aug 25 2008

a(n) is also the number of edge-labeled rooted trees on n nodes. - Nikos Apostolakis, Nov 30 2008

a(n+1) is the number of length n sequences on an alphabet of {1,2,...,n} that have a partial sum equal to n. For example a(4)=16 because there are 16 length 3 sequences on {1,2,3} in which the terms (beginning with the first term and proceeding sequentially) sum to 3 at some point in the sequence. {1, 1, 1}, {1, 2, 1}, {1, 2, 2}, {1, 2, 3}, {2, 1, 1}, {2, 1, 2}, {2, 1, 3}, {3, 1, 1}, {3, 1, 2}, {3, 1, 3}, {3, 2, 1}, {3, 2, 2}, {3, 2, 3}, {3, 3, 1}, {3, 3, 2}, {3, 3, 3}. - Geoffrey Critzer, Jul 20 2009

a(n) is the number of acyclic functions from {1,2,...,n-1} to {1,2,...,n}. An acyclic function f satisfies the following property: for any x in the domain, there exists a positive integer k such that (f^k)(x) is not in the domain. Note that f^k denotes the k-fold composition of f with itself, e.g., (f^2)(x)=f(f(x)). - Dennis P. Walsh, Mar 02 2011

a(n) is the absolute value of the discriminant of the polynomial x^{n-1}+...+x+1. More precisely, a(n) = (-1)^{(n-1)(n-2)/2} times the discriminant. - Zach Teitler, Jan 28 2014

For n > 2, a(n+2) is the number of nodes in the canonical automaton for the affine Weyl group of type A_n. - Tom Edgar, May 12 2016

The tree formula a(n) = n^(n-2) is due to Cayley (see the first comment). - Jonathan Sondow, Jan 11 2018

a(n) is the number of topologically distinct lines of play for the game Planted Brussels Sprouts on n vertices. See Ji and Propp link. - Caleb Ji, May 11 2018

a(n+1) is also the number of bases of R^n, that can be made from the n(n+1)/2 vectors of the form [0 ... 0 1 ... 1 0 ... 0]^T, where the initial or final zeros are optional, but at least one 1 has to be included. - Nicolas Nagel, Jul 31 2018

Cooper et al. show that every connected k-chromatic graph contains at least k^(k-2) spanning trees. - Michel Marcus, May 14 2020

Might be called the "Lichtenberg sequence" after Georg Christoph Lichtenberg, who discussed it in 1769 in connection with the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017

Number of steps to change from a binary string of n 0's to n 1's using a Gray code. - Jon Stadler (jstadler(AT)coastal.edu)

Popular puzzles such as Spin-Out and The Brain Puzzler are based on the Gray binary system and require a(n) steps to complete for some number n.

Conjecture: {a(n)} also gives all j for which A048702(j) = A000217(j); i.e., if we take the a(n)-th triangular number (a(n)^2 + a(n))/2 and multiply it by 3, we get a(n)-th even-length binary palindrome A048701(a(n)) concatenated from a(n) and its reverse. E.g., a(4) = 10, which is 1010 in binary; the tenth triangular number is 55, and 55*3 = 165 = 10100101 in binary. - Antti Karttunen, circa 1999. (This has been now proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016

Number of ways to tie a tie of n or fewer half turns, excluding mirror images. Also number of walks of length n or less on a triangular lattice with the following restrictions; given l, r and c as the lattice axes. 1. All steps are taken in the positive axis direction. 2. No two consecutive steps are taken on the same axis. 3. All walks begin with l. 4. All walks end with rlc or lrc. - Bill Blewett, Dec 21 2000

a(n) is the minimal number of vertices to be selected in a vertex-cover of the balanced tree B_n. - Sen-peng Eu, Jun 15 2002

A087117(a(n)) = A038374(a(n)) = 1 for n > 1; see also A090050. - Reinhard Zumkeller, Nov 20 2003

Intersection of A003754 and A003714; complement of A107907. - Reinhard Zumkeller, May 28 2005

Equivalently, numbers m whose binary representation is effectively, for some number k, both the lazy Fibonacci and the Zeckendorf representation of k (in which case k = A022290(m)). - Peter Munn, Oct 06 2022

a(n+1) gives row sums of Riordan array (1/(1-x), x(1+2x)). - Paul Barry, Jul 18 2005

Total number of initial 01's in all binary words of length n+1. Example: a(3) = 5 because the binary words of length 4 that start with 01 are (01)00, (01)(01), (01)10 and (01)11 and the total number of initial 01's is 5 (shown between parentheses). a(n) = Sum_{k >= 0} k*A119440(n+1, k). - Emeric Deutsch, May 19 2006

In Norway we call the 10-ring puzzle "strikketoy" or "knitwear" (see link). It takes 682 moves to free the two parts. - Hans Isdahl, Jan 07 2008

Equals A002450 and A020988 interlaced. - Zak Seidov, Feb 10 2008

For n > 1, let B_n = the complete binary tree with vertex set V where |V| = 2^n - 1. If VC is a minimum-size vertex cover of B_n, Sen-Peng Eu points out that a(n) = |VC|. It also follows that if IS = V\VC, a(n+1) = |IS|. - K.V.Iyer, Apr 13 2009

Starting with 1 and convolved with [1, 2, 2, 2, ...] = A000295. - Gary W. Adamson, Jun 02 2009

a(n) written in base 2 is sequence A056830(n). - Jaroslav Krizek, Aug 05 2009

This is the sequence A(0, 1; 1, 2; 1) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010

From Vladimir Shevelev, Jan 30 2012, Feb 13 2012: (Start)

1) Denote by {n, k} the number of permutations of 1, ..., n with the up-down index k (for definition, see comment in A203827). Then max_k{n, k} = {n, a(n)} = A000111(n).

2) a(n) is the minimal number > a(n-1) with the Hamming distance d_H(a(n-1), a(n)) = n. Thus this sequence is the Hamming analog of triangular numbers 0, 1, 3, 6, 10, ... (End)

From Hieronymus Fischer, Nov 22 2012: (Start)

Represented in binary form each term after the second one contains every previous term as a substring.

The terms a(2) = 2 and a(3) = 5 are the only primes. Proof: For even n we get a(n) = 2*(2^(2*n) - 1)/3, which shows that a(n) is even, too, and obviously a(n) > 2 for all even n > 2. For odd n we have a(n) = (2^(n+1) - 1)/3 = (2^((n+1)/2) - 1) * (2^((n+1)/2) + 1)/3. Evidently, at least one of these factors is divisible by 3, both are greater than 6, provided n > 3. Hence it follows that a(n) is composite for all odd n > 3.

Represented as a binary number, a(n+1) has exactly n prime substrings. Proof: Evidently, a(1) = 1_2 has zero and a(2) = 10_2 has 1 prime substring. Let n > 1. Written in binary, a(n+1) is 101010101...01 (if n + 1 is odd) and is 101010101...10 (if n + 1 is even) with n + 1 digits. Only the 2- and 3-digits substrings 10_2 (=2) and 101_2 (=5) are prime substrings. All the other substrings are nonprime since every substring is a previous term and all terms unequal to 2 and 5 are nonprime. For even n + 1, the number of prime substrings equal to 2 = 10_2 is (n+1)/2, and the number of prime substrings equal to 5 = 101_2 is (n-1)/2, makes a sum of n. For odd n + 1 we get n/2 for both, the number of 2's and 5's prime substrings, in any case, the sum is n. (End)

Number of different 3-colorings for the vertices of all triangulated planar polygons on a base with n+2 vertices if the colors of the two base vertices are fixed. - Patrick Labarque, Feb 09 2013

A090079(a(n)) = a(n) and A090079(m) <> a(n) for m < a(n). - Reinhard Zumkeller, Feb 16 2013

a(n) is the number of length n binary words containing at least one 1 and ending in an even number (possibly zero) of 0's. a(3) = 5 because we have: 001, 011, 100, 101, 111. - Geoffrey Critzer, Dec 15 2013

a(n) is the number of permutations of length n+1 having exactly one descent such that the first element of the permutation is an even number. - Ran Pan, Apr 18 2015

a(n) is the sequence of the last row of the Hadamard matrix H(2^n) obtained via Sylvester's construction: H(2) = [1,1;1,-1], H(2^n) = H(2^(n-1))*H(2), where * is the Kronecker product. - William P. Orrick, Jun 28 2015

Conjectured record values of A264784: a(n) = A264784(A155051(n-1)). - Reinhard Zumkeller, Dec 04 2015. (This is proved by Paul K. Stockmeyer in his arXiv:1608.08245 paper.) - Antti Karttunen, Aug 31 2016

Decimal representation of the x-axis, from the origin to the right edge, of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 131", based on the 5-celled von Neumann neighborhood. See A279053 for references and links. - Robert Price, Dec 05 2016

For n > 4, a(n-2) is the second-largest number in row n of A127824. - Dmitry Kamenetsky, Feb 11 2017

Conjecture: a(n+1) is the number of compositions of n with two kinds of parts, n and n', where the order of the 1 and 1' does not matter. For n=2, a(3) = 5 compositions, enumerated as follows: 2; 2'; 1,1; 1',1 = 1',1; 1',1'. - Gregory L. Simay, Sep 02 2017

Conjecture proved by recognizing the appropriate g.f. is x/(1 - x)(1 - x)(1 - 2*x^2 - 2x^3 - ...) = x/(1 - 2*x - x^2 + 2x^3). - Gregory L. Simay, Sep 10 2017

a(n) = 2^(n-1) + 2^(n-3) + 2^(n-5) + ... a(2*k -1) = A002450(k) is the sum of the powers of 4. a(2*k) = 2*A002450(k). - Gregory L. Simay, Sep 27 2017

a(2*n) = n times the string [10] in binary representation, a(2*n+1) = n times the string [10] followed with [1] in binary representation. Example: a(7) = 85 = (1010101) in binary, a(8) = 170 = (10101010) in binary. - Ctibor O. Zizka, Nov 06 2018

Except for 0, these are the positive integers whose binary expansion has cuts-resistance 1. For the operation of shortening all runs by 1, cuts-resistance is the number of applications required to reach an empty word. Cuts-resistance 2 is A329862. - Gus Wiseman, Nov 27 2019

From Markus Sigg, Sep 14 2020: (Start)

Let s(k) be the length of the Collatz orbit of k, e.g. s(1) = 1, s(2) = 2, s(3) = 5. Then s(a(n)) = n+3 for n >= 3. Proof by induction: s(a(3)) = s(5) = 6 = 3+3. For odd n >= 5 we have s(a(n)) = s(4*a(n-2)+1) = s(12*a(n-2)+4)+1 = s(3*a(n-2)+1)+3 = s(a(n-2))+2 = (n-2)+3+2 = n+3, and for even n >= 4 this gives s(a(n)) = s(2*a(n-1)) = s(a(n-1))+1 = (n-1)+3+1 = n+3.

Conjecture: For n >= 3, a(n) is the second largest natural number whose Collatz orbit has length n+3. (End)

From Gary W. Adamson, May 14 2021: (Start)

With offset 1 the sequence equals the numbers of 1's from n = 1 to 3, 3 to 7, 7 to 15, ...; of A035263; as shown below:

..1 3 7 15...

..1 0 1 1 1 0 1 0 1 0 1 1 1 0 1...

..1.....2...........5......................10...; a(n) = Sum_(k=1..2n-1)A035263(k)

.....1...........2.......................5...; as to zeros.

..1's in the Tower of Hanoi game represent CW moves On disks in the pattern:

..0, 1, 2, 0, 1, 2, ... whereas even numbered disks move in the pattern:

..0, 2, 1, 0, 2, 1, ... (End)

Except for 0, numbers that are repunits in Gray-code representation (A014550). - Amiram Eldar, May 21 2021

From Gus Wiseman, Apr 20 2023: (Start)

Also the number of nonempty subsets of {1..n} with integer median, where the median of a multiset is the middle part in the odd-length case, and the average of the two middle parts in the even-length case. For example, the a(1) = 1 through a(4) = 10 subsets are:

{1} {1} {1} {1}

{2} {2} {2}

{3} {3}

{1,3} {4}

{1,2,3} {1,3}

{2,4}

{1,2,3}

{1,2,4}

{1,3,4}

{2,3,4}

The complement is counted by A005578.

For mean instead of median we have A051293, counting empty sets A327475.

For normal multisets we have A056450, strongly normal A361202.

For partitions we have A325347, strict A359907, complement A307683.

(End)

In binary form, because the sequence 10101_2... keeps repeating, one can represent a(n) = floor(0.(10)2 * 2^n). Because 0.(10)_2 = 0.(10)_2 * 4 - 2, then 0.(10)_2 = 2/3. Substituting this value in the first expression, we obtain a(n) = floor(2^(n+1)/3). This also agrees with the formula of Paul Barry, Oct 08 2005. - _Giovanni Ciriani, Mar 31 2025

Inverse Gudermannian gd^(-1)(x) = log(sec(x) + tan(x)) = log(tan(Pi/4 + x/2)) = arctanh(sin(x)) = 2 * arctanh(tan(x/2)) = 2 * arctanh(csc(x) - cot(x)). - Michael Somos, Mar 19 2011

a(n) is the number of downup permutations of [2n]. Example: a(2)=5 counts 4231, 4132, 3241, 3142, 2143. - David Callan, Nov 21 2011

a(n) is the number of increasing full binary trees on vertices {0,1,2,...,2n} for which the leftmost leaf is labeled 2n. - David Callan, Nov 21 2011

a(n) is the number of unordered increasing trees of size 2n+1 with only even degrees allowed and degree-weight generating function given by cosh(t). - Markus Kuba, Sep 13 2014

a(n) is the number of standard Young tableaux of skew shape (n+1,n,n-1,...,3,2)/(n-1,n-2,...2,1). - Ran Pan, Apr 10 2015

Since cos(z) has a root at z = Pi/2 and no other root in C with a smaller |z|, the radius of convergence of the e.g.f. (intended complex-valued) is Pi/2 = A019669 (see also A028296). - Stanislav Sykora, Oct 07 2016

All terms are odd. - Alois P. Heinz, Jul 22 2018

The sequence starting with a(1) is periodic modulo any odd prime p. The minimal period is (p-1)/2 if p == 1 mod 4 and p-1 if p == 3 mod 4 [Knuth & Buckholtz, 1967, Theorem 2]. - Allen Stenger, Aug 03 2020

Conjecture: taking the sequence [a(n) : n >= 1] modulo an integer k gives a purely periodic sequence with period dividing phi(k). For example, the sequence taken modulo 21 begins [1, 5, 19, 20, 16, 2, 1, 5, 19, 20, 16, 2, 1, 5, 19, 20, 16, 2, 1, 5, 19, ...] with an apparent period of 6 = phi(21)/2. - Peter Bala, May 08 2023

If you are looking for the Schroeder numbers (a.k.a. large Schroder numbers, or big Schroeder numbers), see A006318.

Yang & Jiang (2021) call these the small 2-Schroeder numbers. - N. J. A. Sloane, Mar 28 2021

There are two schools of thought about the index for the first term. I prefer the indexing a(0) = a(1) = 1, a(2) = 3, a(3) = 11, etc.

a(n) is the number of ways to insert parentheses in a string of n+1 symbols. The parentheses must be balanced but there is no restriction on the number of pairs of parentheses. The number of letters inside a pair of parentheses must be at least 2. Parentheses enclosing the whole string are ignored.

Also length of list produced by a variant of the Catalan producing iteration: replace each integer k with the list 0,1,..,k,k+1,k,...,1,0 and get the length a(n) of the resulting (flattened) list after n iterations. - Wouter Meeussen, Nov 11 2001

Stanley gives several other interpretations for these numbers.

Number of Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D(1,-1) and not going below the x-axis) with no peaks at level 1. Example: a(2)=3 because among the six Schroeder paths of semilength two HH, UHD, UUDD, HUD, UDH and UDUD, only the first three have no peaks at level 1. - Emeric Deutsch, Dec 27 2003

a(n+1) is the number of Dyck n-paths in which the interior vertices of the ascents are colored white or black. - David Callan, Mar 14 2004

Number of possible schedules for n time slots in the first-come first-served (FCFS) printer policy.

Also row sums of A086810, A033282, A126216. - Philippe Deléham, May 09 2004

a(n+1) is the number of pairs (u,v) of same-length compositions of n, 0's allowed in u but not in v and u dominates v (meaning u_1 >= v_1, u_1 + u_2 >= v_1 + v_2 and so on). For example, with n=2, a(3) counts (2,2), (1+1,1+1), (2+0,1+1). - David Callan, Jul 20 2005

The big Schroeder number (A006318) is the number of Schroeder paths from (0,0) to (n,n) (subdiagonal paths with steps (1,0) (0,1) and (1,1)). These paths fall in two classes: those with steps on the main diagonal and those without. These two classes are equinumerous and the number of paths in either class is the little Schroeder number a(n) (half the big Schroeder number). - Marcelo Aguiar (maguiar(AT)math.tamu.edu), Oct 14 2005

With offset 0, a(n) = number of (colored) Motzkin (n-1)-paths with each upstep U getting one of 2 colors and each flatstep F getting one of 3 colors. Example. With their colors immediately following upsteps/flatsteps, a(2) = 3 counts F1, F2, F3 and a(3)=11 counts U1D, U2D, F1F1, F1F2, F1F3, F2F1, F2F2, F2F3, F3F1, F3F2, F3F3. - David Callan, Aug 16 2006

Shifts left when INVERT transform applied twice. - Alois P. Heinz, Apr 01 2009

Number of increasing tableaux of shape (n,n). An increasing tableau is a semistandard tableaux with strictly increasing rows and columns, and set of entries an initial segment of the positive integers. Example: a(2) = 3 because of the three tableaux (12)(34), (13)(24), (12)(23). - Oliver Pechenik, Apr 22 2014

Number of ordered trees with no vertex of outdegree 1 and having n+1 leaves (called sometimes Schröder trees). - Emeric Deutsch, Dec 13 2014

Number of dissections of a convex (n+2)-gon by nonintersecting diagonals. Example: a(2)=3 because for a square ABCD we have (i) no diagonal, (ii) dissection with diagonal AC, and (iii) dissection with diagonal BD. - Emeric Deutsch, Dec 13 2014

The little Schroeder numbers are the moments of the Marchenko-Pastur law for the case c=2 (although the moment m0 is 1/2 instead of 1): 1/2, 1, 3, 11, 45, 197, 903, ... - Jose-Javier Martinez, Apr 07 2015

Number of generalized Motzkin paths with no level steps at height 0, from (0,0) to (2n,0), and consisting of steps U=(1,1), D=(1,-1) and H2=(2,0). For example, for n=3, we have the 11 paths: UDUDUD, UUDDUD, UDUUDD, UH2DUD, UDUH2D, UH2H2D, UUDUDD, UUUDDD, UUH2DD, UUDH2D, UH2UDD. - José Luis Ramírez Ramírez, Apr 20 2015

REVERT transform of A225883. - Vladimir Reshetnikov, Oct 25 2015

Total number of (nonempty) faces of all dimensions in the associahedron K_{n+1} of dimension n-1. For example, K_4 (a pentagon) includes 5 vertices and 5 edges together with K_4 itself (5 + 5 + 1 = 11), while K_5 includes 14 vertices, 21 edges and 9 faces together with K_5 itself (14 + 21 + 9 + 1 = 45). - Noam Zeilberger, Sep 17 2018

a(n) is the number of interval posets of permutations with n minimal elements that have exactly two realizers, up to a shift by 1 in a(4). See M. Bouvel, L. Cioni, B. Izart, Theorem 17 page 13. - Mathilde Bouvel, Oct 21 2021

a(n) is the number of sequences of nonnegative integers (u_1, u_2, ..., u_n) such that (i) u_1 = 1, (ii) u_i <= i for all i, (iii) the nonzero u_i are weakly increasing. For example, a(2) = 3 counts 10, 11, 12, and a(3) = 11 counts 100, 101, 102, 103, 110, 111, 112, 113, 120, 122, 123. See link below. - David Callan, Dec 19 2021

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

a(n+1) is the number of Schroeder paths from (0,0) to (2n,0) in which level steps at height 0 come in 2 colors. - Alexander Burstein, Jul 23 2023

When viewed as a triangular array, the row sum values are 0 1 1 1 2 3 3 3 4 5 5 5 6 ... (A004525).

This is the r=0 member of the r-family of sequences S_r(n) defined in A092184 where more information can be found.

Successive binomial transforms of this sequence: A011782, A007051, A007582, A081186, A081187, A081188, A081189, A081190, A060531, A081192.

Characteristic function of even numbers: a(A005843(n))=1, a(A005408(n))=0. - Reinhard Zumkeller, Sep 29 2008

This sequence is the Euler transformation of A185012. - Jason Kimberley, Oct 14 2011

a(n) is the parity of n+1. - Omar E. Pol, Jan 17 2012

Read as partial sequences, we get to A000975. - Jon Perry, Nov 11 2014

Elementary Cellular Automata rule 77 produces this sequence. See Wolfram, Weisstein and Index links below. - Robert Price, Jan 30 2016

Column k = 1 of A051159. - John Keith, Jun 28 2021

When read as a constant: decimal expansion of 10/99, binary expansion of 2/3. - Jason Bard, Aug 25 2025

Also, number of unlabeled 2-gonal 2-trees with n-1 2-gons, for n>0. [Corrected by Andrei Zabolotskii, Jul 29 2025]

Main diagonal of A054924.

Left border of A157905. - Gary W. Adamson, Mar 08 2009

From Robert Munafo, Jan 24 2010: (Start)

Also counts classifications of n items that require exactly n-1 binary partitions; see Munafo link at A005646, also A171871 and A171872.

The 11 trees for n = 7 are illustrated at the Munafo web link.

Link to A171871/A171872 conjectured by Robert Munafo, then proved by Andrew Weimholt and Franklin T. Adams-Watters on Dec 29 2009. (End)

This is also "Number of tree perfect graphs on n nodes" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

For n > 0, a(n) is the number of ways to arrange n-1 unlabeled non-intersecting circles on a sphere. - Vladimir Reshetnikov, Aug 25 2016

All trees for n=1 through n=12 are depicted in Chapter 1 of the Steinbach reference. On p. 6 appear encircled two trees (with n=10) which seem inequivalent only when considered as ordered (planar) trees. Earlier instances of such possibly (in)equivalent trees could appear from n=6 on (and from n=9 on without equivalence modulo plane symmetry) but are not drawn separately there. - M. F. Hasler, Aug 29 2017

These are different from plane partitions.

For ordered partitions of partitions see A055887 which may be computed from A036036 and A048996. - Alford Arnold, May 19 2006

Twice partitioned numbers correspond to triangles (or compositions) in the multiorder of integer partitions. - Gus Wiseman, Oct 28 2015

Number of primes with at most n digits; or pi(10^n).

Partial sums of A006879. - Lekraj Beedassy, Jun 25 2004

Also omega( (10^n)! ), where omega(x): number of distinct prime divisors of x. - Cino Hilliard, Jul 04 2007

This sequence also gives a good approximation for the sum of primes less than 10^(n/2). This is evident from the fact that the number of primes less than 10^2n closely approximates the sum of primes less than 10^n. See link on Sum of Primes for the derivation. - Cino Hilliard, Jun 08 2008

It appears that (10^n)/log((n+3)!) is a lower bound close to a(n), see A025201. - Eric Desbiaux, Jul 20 2010, edited by M. F. Hasler, Dec 03 2018

Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence.

This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix, Nov 17 2005

Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206-A006208. - Jonathan Vos Post, Jun 18 2007

"Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2Pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler, Jan 14 2007

Also the number of dynamical cycles of period n of a threshold Boolean automata network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009

Also, the number of periodic points with (minimal) period n in the iteration of the tent map f(x):=2min{x,1-x} on the unit interval. - Pietro Majer, Sep 22 2009

Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013

From Jean-Christophe Hervé, Oct 26 2014: (Start)

For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n.

For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End)

Warning: A000031 and A001037 are easily confused, since they have similar formulas.

From Petros Hadjicostas, Jul 14 2020: (Start)

Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.

Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N).

For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w.

For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.

For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.

He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)

Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).

For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)