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

Number of permutations of [n] with 2 sequences.

Number of 2 X n binary matrices that avoid simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1Sergey Kitaev, Nov 11 2004

The number of edges in the dual Edwards-Venn diagram graph with n-1 digits when n>2.

a(n) (n>=6) is the number of vertices in the molecular graph NS2[n-5], defined pictorially in the Ashrafi et al. reference (Fig. 2, where NS2[2] is shown). - Emeric Deutsch, May 16 2018

From Petros Hadjicostas, Aug 08 2019: (Start)

With regard to the comment above about a(n) being the "number of permutations of [n] with 2 sequences", we refer to Ex. 13 (pp. 260-261) of Comtet (1974), who uses the definition of a "séquence" given by André in several of his papers in the 19th century.

In the terminology of array A059427, these so-called "séquences" in permutations (defined by Comtet and André) are called "alternating runs" (or just "runs"). We discuss these so-called "séquences" below.

If b = (b_1, b_2, ..., b_n) is a permutation of [n], written in one-line notation (not in cycle notation), a "séquence" in a permutation of length l >= 2 (according to Comtet) is a maximal interval of integers {i, i+1, ..., i+l-1} for some i (where 1 <= i <= n-l+1) such that b_i < b_{i+1} < ... < b_{i+l-1} or b_i > b_{i+1} > ... > b_{i+l-1}. (The word "maximal" means that, in the first case, we have b_{i-1} > b_i and b_{i+l} < b_{i+l-1}, while in the second case, we have b_{i-1} < b_i and b_{i+l} > b_{i+l-1} provided b_{i-1} and b_{i+l} can be defined.)

When defining a "séquence", André (1884) actually refers to the list of terms (b_i, b_{i+1}, ..., b_{i+l-1}) rather than the corresponding index set {i, i+1, ..., i+l-1} (which is essentially the same thing).

For more details about these so-called "séquences" (or "alternate runs"), see the comments and examples for sequence A000708.

(End)

For n >= 1, a(n+2) is the number of shortest paths from (0,0) of a square grid to {(x,y): |x|+|y| = n} along the grid line. - Jianing Song, Aug 23 2021

Row n has 1+floor(n/2) terms.

T(n,k) is also the number of permutations of [n] with k "exterior peaks" where we count peaks in the usual way, but add a peak at the beginning if the permutation begins with a descent, e.g. 213 has one exterior peak. T(3,1) = 5 since all permutations of [3] have an exterior peak except 123. This is also the definition for peaks of signed permutations, where we assume that a signed permutation always begins with a zero. - Kyle Petersen, Jan 14 2005

From Petros Hadjicostas, Aug 09 2019: (Start)

In their book, David and Barton (1962) use the notation T_{N,v*}^* for this array, where N is the length of the permutation and v* is the so-called "number of runs up" in the permutation. In modern terminology, a "run up" in a permutation is an increasing run of length >= 2. See their discussion on p. 154 of their book and see p. 163 for the definition of T_{N,v*}^*.

They do not consider as "runs up" single elements b_i in a permutation b = (b_1, b_2, ..., b_n) even if they satisfy b_{i-1} > b_i > b_{i+1} (with b_{n-1} > b_n when i = n and b_1 > b_2 when i = 1). (The command Runs[b] for permutation b in Mathematica, using the package Combinatorica`, will generate not only the "runs up" of b but also the single elements in the permutation b that satisfy one of the above inequalities. For example, Runs[{3,2,1}] gives the set of runs {{3}, {2}, {1}}, none of which is a "run up".)

So, here n = N and k = v*. On p. 163 of their book they give the recurrence shown below in the FORMULA section from Charalambides' (2002) book: T(n+1, k) = (2*k + 1) * T(n,k) + (n - 2*k + 2) * T(n, k-1) for n >= 0 and 1 <= k <= floor(n/2) + 1. The values of T_{N,v*}^* = T(n, k) appear in Table 10.5 (p. 163) of their book.

Since the complement of a permutation (b_1, b_2, ..., b_n) is (n+1-b_1, n+1-b_2, ..., n+1-b_n), it is clear that the current array T(n, k) is also the number of permutations of [n] with k decreasing runs of length >= 2 (i.e., the number of permutations of [n] with k "runs down" according to David and Barton (1962)).

Note that the number of permutations of [n] with k runs of length >= 2 that are either increasing or decreasing (i.e., the number of permutations of [n] that contain k "runs up" and "runs down" in total) is given by array A059427. One half of array A059427 is given in Table 10.4 (p. 159) in David and Barton (1962)--see also array A008970.

A run that is either a "run up" or "run down" (i.e., an ascending or a descending run of length >= 2) is called "séquence" by André (19th century) and Comtet (1974). See the references for sequence A000708 or for array A059427. (Again, recall that David and Barton do not consider single numbers as either a "run up" or a "run down".)

Morley (1897) proved that in a permutation of [n], #("runs up") + #("runs down") + #(monotonic triplets of adjacent numbers in the permutation) = n - 1. (His definition of a run is highly non-standard!) See the example below.

The number Q(n,k) of circular permutations of [n] that contain k runs that are either "runs up" or "runs down" (that is, k ascending or descending runs of length >= 2) is given by array A008303. More precisely, Q(n+1, 2*(k+1)) = A008303(n, k) for n >= 1 and 0 <= k <= ceiling(n/2)-1. In addition, Q(n, s) = 0 when either s is odd, or n <= 1, or s > n. Also, Q_{n,2} = 2^(n-2) for n >= 2.

The numbers in array A008303 appear in Table 10.6 (p. 163) in David and Barton (1962).

(End)

The number of permutations of [n] with n-2 sequences (see Comtet).

From Petros Hadjicostas, Aug 08 2019: (Start)

We clarify the word "sequences" used above because it may not be standard. On pp. 260-261 of his book, Comtet (1974) defines a so-called "sequence" in a permutation b of [n]. Using one-line notation (not cycle notation), write b = (b_1, b_2, ..., b_n) for the elements of a permutation of [n]. A maximal list of indices of length l (where l >= 2) is called a "sequence" in the permutation b if it is of the form {i, i+1, ..., i+l-1} for some integer i (with 1 <= i <= n-l+1) such that b_i < b_{i+1} < ... < b_{i+l-1} or b_i > b_{i+1} > ... > b_{i+l-1}. (The word "maximal" means that in the first case, b_{i-1} > b_i and b_{i+l} < b_{i+l-1}, while in the second case, b_{i-1} < b_i and b_{i+l} > b_{i+l-1}, provided that b_{i-1} and b_{i+l} can be defined.) The assumption l >= 2 is important; i.e., these so-called "sequences" should have length >= 2.

Comtet (1974) has borrowed this confusing terminology about "séquences" in permutations from André (see links to some of his papers below). André actually uses the term "séquence" for the list of terms (b_i, b_{i+1}, ..., b_{i+l-1}) rather than the index set {i, i+1, ..., i+l-1}.

Some authors today use the term "alternate runs" (or just "runs") to discuss these so-called "séquences" defined by Comtet and André but we must have l >= 2.

Thus, here a(n) is the number of permutations of [n] with n-2 such "séquences" ("alternate runs").

For an extensive discussion of these so-called "séquences" in permutations ("alternate runs"), maxima and minima in a permutation, alternate and quasi-alternate permutations, and other related information, see the four papers by André, or see my comments for sequence A000708 (which equals one-half of the current sequence).

David and Barton (1962, p. 154) call these "séquences" "runs up" if they are ascending and "runs down" if they are descending. In modern terminology, "runs up" are ascending runs of length >= 2 while "runs down" are descending runs of length >= 2. Thus, a modern terminology for these "séquences" is "ascending or descending runs of length >= 2".

(End)