cp's OEIS Frontend

Number of linear extensions of the "zig-zag" poset. See ch. 3, prob. 23 of Stanley. - Mitch Harris, Dec 27 2005

Number of increasing 0-1-2 trees on n vertices. - David Callan, Dec 22 2006

Also the number of refinements of partitions. - Heinz-Richard Halder (halder.bichl(AT)t-online.de), Mar 07 2008

The ratio a(n)/n! is also the probability that n numbers x1,x2,...,xn randomly chosen uniformly and independently in [0,1] satisfy x1 > x2 < x3 > x4 < ... xn. - Pietro Majer, Jul 13 2009

For n >= 2, a(n-2) = number of permutations w of an ordered n-set {x_1 < ... x_n} with the following properties: w(1) = x_n, w(n) = x_{n-1}, w(2) > w(n-1), and neither any subword of w, nor its reversal, has the first three properties. The count is unchanged if the third condition is replaced with w(2) < w(n-1). - Jeremy L. Martin, Mar 26 2010

A partition of zigzag permutations of order n+1 by the smallest or the largest, whichever is behind. This partition has the same recurrent relation as increasing 1-2 trees of order n, by induction the bijection follows. - Wenjin Woan, May 06 2011

As can be seen from the asymptotics given in the FORMULA section, one has lim_{n->oo} 2*n*a(n-1)/a(n) = Pi; see A132049/A132050 for the simplified fractions. - M. F. Hasler, Apr 03 2013

a(n+1) is the sum of row n in triangle A008280. - Reinhard Zumkeller, Nov 05 2013

M. Josuat-Verges, J.-C. Novelli and J.-Y. Thibon (2011) give a far-reaching generalization of the bijection between Euler numbers and alternating permutations. - N. J. A. Sloane, Jul 09 2015

Number of treeshelves avoiding pattern T321. Treeshelves are ordered binary (0-1-2) increasing trees where every child is connected to its parent by a left or a right link, see A278678 for more definitions and examples. - Sergey Kirgizov, Dec 24 2016

Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that no three terms are equal. [Theorem 7 of Corteel, Martinez, Savage, and Weselcouch] - Eric M. Schmidt, Jul 17 2017

Number of self-dual edge-labeled trees with n vertices under "mind-body" duality. Also number of self-dual rooted edge-labeled trees with n vertices. See my paper linked below. - Nikos Apostolakis, Aug 01 2018

The ratio a(n)/n! is the volume of the convex polyhedron defined as the set of (x_1,...,x_n) in [0,1]^n such that x_i + x_{i+1} <= 1 for every 1 <= i <= n-1; see the solutions by Macdonald and Nelsen to the Amer. Math. Monthly problem referenced below. - Sanjay Ramassamy, Nov 02 2018

Number of total cyclic orders on {0,1,...,n} such that the triple (i-1,i,i+1) is positively oriented for every 1 <= i <= n-1; see my paper on cyclic orders linked below. - Sanjay Ramassamy, Nov 02 2018

The number of binary, rooted, unlabeled histories with n+1 leaves (following the definition of Rosenberg 2006). Also termed Tajima trees, Tajima genealogies, or binary, rooted, unlabeled ranked trees (Palacios et al. 2015). See Disanto & Wiehe (2013) for a proof. - Noah A Rosenberg, Mar 10 2019

From Gus Wiseman, Dec 31 2019: (Start)

Also the number of non-isomorphic balanced reduced multisystems with n + 1 distinct atoms and maximum depth. A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. The labeled version is A006472. For example, non-isomorphic representatives of the a(0) = 1 through a(4) = 5 multisystems are (commas elided):

{1} {12} {{1}{23}} {{{1}}{{2}{34}}} {{{{1}}}{{{2}}{{3}{45}}}}

{{{12}}{{3}{4}}} {{{{1}}}{{{23}}{{4}{5}}}}

{{{{1}{2}}}{{{3}}{{45}}}}

{{{{1}{23}}}{{{4}}{{5}}}}

{{{{12}}}{{{3}}{{4}{5}}}}

Also the number of balanced reduced multisystems with n + 1 equal atoms and maximum depth. This is possibly the meaning of Heinz-Richard Halder's comment (see also A002846, A213427, A265947). The non-maximum-depth version is A318813. For example, the a(0) = 1 through a(4) = 5 multisystems are (commas elided):

{1} {11} {{1}{11}} {{{1}}{{1}{11}}} {{{{1}}}{{{1}}{{1}{11}}}}

{{{11}}{{1}{1}}} {{{{1}}}{{{11}}{{1}{1}}}}

{{{{1}{1}}}{{{1}}{{11}}}}

{{{{1}{11}}}{{{1}}{{1}}}}

{{{{11}}}{{{1}}{{1}{1}}}}

(End)

With s_n denoting the sum of n independent uniformly random numbers chosen from [-1/2,1/2], the probability that the closest integer to s_n is even is exactly 1/2 + a(n)/(2*n!). (See Hambardzumyan et al. 2023, Appendix B.) - Suhail Sherif, Mar 31 2024

The number of permutations of size n+1 that require exactly n passes through a stack (i.e. have reverse-tier n-1) with an algorithm that prioritizes outputting the maximum possible prefix of the identity in a given pass and reverses the remainder of the permutation for prior to the next pass. - Rebecca Smith, Jun 05 2024

a(n) is the number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.

A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - N. J. A. Sloane, Aug 03 2016

Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004

Row sums of unsigned A134685. - Tom Copeland, Oct 11 2008

Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018

From Gus Wiseman, Dec 28 2019: (Start)

Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(End)

Product of first (n-1) positive triangular numbers. - Amarnath Murthy, May 19 2002, corrected by Alex Ratushnyak, Dec 03 2013

Number of ways of transforming n distinguishable objects into n singletons via a sequence of n-1 refinements. Example: a(3)=3 because we have XYZ->X|YZ->X|Y|Z, XYZ->Y|XZ->X|Y|Z and XYZ->Z|XY->X|Y|Z. - Emeric Deutsch, Jan 23 2005

In other words, a(n) is the number of maximal chains in the lattice of set partitions of {1, ..., n} ordered by refinement. - Gus Wiseman, Jul 22 2018

From David Callan, Aug 27 2009: (Start)

With offset 0, a(n) = number of unordered increasing full binary trees of 2n edges with leaf set {n,n+1,...,2n}, where full binary means each nonleaf vertex has two children, increasing means the vertices are labeled 0,1,2,...,2n and each child is greater than its parent, unordered might as well mean ordered and each pair of sibling vertices is increasing left to right. For example, a(2)=3 counts the trees with edge lists {01,02,13,14}, {01,03,12,14}, {01,04,12,13}.

PROOF. Given such a tree of size n, to produce a tree of size n+1, two new leaves must be added to the leaf n. Choose any two of the leaf set {n+1,...,2n,2n+1,2n+2} for the new leaves and use the rest to replace the old leaves n+1,...,2n, maintaining relative order. Thus each tree of size n yields (n+2)-choose-2 trees of the next size up. Since the ratio a(n+1)/a(n)=(n+2)-choose-2, the result follows by induction.

Without the condition on the leaves, these trees are counted by the reduced tangent numbers A002105. (End)

a(n) = Sum(M(t)N(t)), where summation is over all rooted trees t with n vertices, M(t) is the number of ways to take apart t by sequentially removing terminal edges (see A206494) and N(t) is the number of ways to build up t from the one-vertex tree by adding successively edges to the existing vertices (the Connes-Moscovici weight; see A206496). See Remark on p. 3801 of the Hoffman reference. Example: a(3) = 3; indeed, there are two rooted trees with 3 vertices: t' = the path r-a-b and t" = V; we have M(t')=N(t')=1 and M(t") =1, N(t")=2, leading to M(t')N(t') + M(t")N(t")=3. - Emeric Deutsch, Jul 20 2012

Number of coalescence sequences or labeled histories for n lineages: the number of sequences by which n distinguishable leaves can coalesce to a single sequence. The coalescence process merges pairs of lineages into new lineages, labeling each newly formed lineage l by a subset of the n initial lineages corresponding to the union of all initial lineages that feed into lineage l. - Noah A Rosenberg, Jan 28 2019

Conjecture: For n > 1, n divides 2*a(n-1) + 4 if and only if n is prime. - Werner Schulte, Oct 04 2020

For a proof of the above conjecture see Himane. The list of primes p such that p^2 divides (2*a(p-1) + 4) (analog of A007540 - Wilson primes) begins [239, 24049, ...]. - Peter Bala, Nov 06 2024

Only the leaves are colored. Equivalence is up to permutation of the colors.

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

Also the number of labeled lone-child-avoiding rooted trees with n nodes. A rooted tree is lone-child-avoiding if it has no unary branchings, meaning every non-leaf node covers at least two other nodes. The unlabeled version is A001678(n + 1). - Gus Wiseman, Jan 20 2020

A total multiset partition of m is either m itself or a total multiset partition of a multiset partition of m that is neither minimal nor maximal.

a(n) depends only on the prime signature of n. - Andrew Howroyd, Dec 30 2019

For n > 1, also the number of balanced reduced multisystems whose atoms are an integer partition of n with at least one part > 1. A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. - Gus Wiseman, Dec 31 2019

The weight of an atom is 1, and the weight of a multiset is the sum of weights of its elements, counting multiplicity.

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. The weight of an atom is 1, while the weight of a multiset is the sum of weights of its elements.

A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem.

A finite multiset is strongly normal if it covers an initial interval of positive integers with weakly decreasing multiplicities.