cp's OEIS Frontend

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

a(n) mod 10 for n >= 2 is the periodic sequence repeat: 0, 1, 6, 9.

For n >= 2, a(n) is the number of permutations on [n] that have n-2 "sequences" (which are maximal monotone runs in Comtet terminology) and start increasing. - Michael Somos, Aug 28 2013

From Petros Hadjicostas, Aug 07 2019: (Start)

With regard to the comment by Michael Somos above, a "sequence" in a permutation according to Ex. 13 (pp. 260-261) of Comtet (1974) is actually a "séquence" in a permutation according to André. He uses this terminology in several of his papers cited in the links below.

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

We clarify that a(n) is actually one-half the number of permutations on [n] that have n-2 "séquences" as defined by Comtet and André.

André (1884) defines a "maximum" of a permutation of [n] to be any number in the permutation that is greater than both of its neighbors, if it is an interior number, or greater than its single neighbor, if it is either at the beginning or at the end of the permutation.

André (1884) also defines a "minimum" of a permutation of [n] to be any number in the permutation that is less than both of its neighbors, if it is an interior number, or less than its single neighbor, if it is either at the beginning or at the end of the permutation.

A "séquence" in a permutation of [n] according to André and Comtet is a list of consecutive numbers in the permutation that begins with a maximum and ends with a minimum, or vice versa, but has no interior maxima and minima. As mentioned above, other authors call these so-called "séquences" "alternate runs" (or just "runs").

For example, in the permutation 78125436 of [8], we have three maxima, 8, 5, and 6; three minima, 7, 1, and 3; and the so-called "séquences" ("alternate runs") 78, 81, 125, 543, 36 (see p. 122 in André (1884)).

If in the above permutation we take the difference 8-7, 1-8, 2-1, 5-2, 4-5, 3-4, 6-3, we may form a word (list) of signs of consecutive differences: +-++--+.

In general, if in a permutation of [n], say a_1,a_2,...,a_n (written in one-line notation, but not in cycle notation), we form the differences a_2 - a_1, a_3 - a_2, ..., a_n - a_{n-1}, then we get a list of n-1 signs (+ or -).

For n >= 2, André (1885) calls a permutation of [n] "alternate" if it has n - 1 so-called "séquences" ("alternate runs"); i.e., if the corresponding list of signs alternates between + and -. See the documentation and references for sequences A000111 and A001250.

For n >= 2, André (1885) calls a permutation of [n] "quasi-alternate" if it has n - 2 so-called "séquences" ("alternate runs"); i.e., if the corresponding list of signs alternates between + and - except for a single ++ or a single --, but not both.

In the above example, the permutation 78125436 has 5 so-called "séquences" ("alternate signs") and 5 < 8-2 < 8-1; that is, it is neither alternate nor quasi-alternate. We can reach the same conclusion by looking at its corresponding list of signs +-++--+. The permutation is neither alternate nor quasi-alternate because we have one ++ and one --.

On p. 316, André (1885) gives the following two examples of permutations of [8]: 31426587 and 32541768 (using one-line notation for permutations). The first one has list of signs -+-+-+- while the second one has list of signs -+--+-+. The first one is alternate while the second one is quasi-alternate (because of a single --). Alternatively, the first one has n-1 = 7 so-called "séquences" ("alternate runs")--31, 14, 42, 26, 65, 58, 87--while the second one has n-2 = 6 so-called "séquences" ("alternate runs")--32, 25, 541, 17, 76, 68.

Here 2*a(n) is the total number of quasi-alternate permutations of [n]. Actually, André (1884, 1885) uses P_{n,s} to denote the number of permutations of [n] with exactly s of his so-called "séquences" ("alternate runs"). He uses the notation A_n to denote half the number of alternate permutations of [n] and B_n to denote half the number of quasi-alternate permutations of [n].

Thus, P_{n,n-1} = 2*A_n = 2*A000111(n) = A001250(n) for n >= 2 and P_{n,n-2} = 2*B_n = 2*a(n) for n >= 2.

We have P_{n,s} = A059427(n,s) for n >= 2 and s >= 1. See also p. 261 in Comtet (1974). They satisfy André's recurrence P_{n,s} = s*P_{n-1,s} + 2*P_{n-1,s-1} + (n-s)*P_{n-1,s-2} for n >= 3 and s >= 3 with P(n, 1) = 2 for n >= 2 and P(n, s) = 0 for s >= n.

The numbers Q(n,s) that count the circular permutations of [n] with exactly s so-called "séquences" ("alternate runs") appear in array A008303. They have also been studied by Désiré André (see the references there).

(End)

The up-down runs of a permutation p are the alternating runs of the permutation p endowed with a 0 in the front. For example, 75814632 has 6 up-down runs: 07, 75, 58, 81, 146, and 632.

Table starts

.......1........1.........1.........1.........1.........1.........1.........1

.......2........2.........2.........2.........2.........2.........2.........2

.......4........6.........6.........6.........6.........6.........6.........6

......10.......22........24........24........24........24........24........24

......32.......90.......118.......120.......120.......120.......120.......120

.....122......422.......658.......718.......720.......720.......720.......720

.....544.....2226......4078......4914......5038......5040......5040......5040

....2770....13102.....27724.....37300.....40066.....40318.....40320.....40320

...15872....85170....205134....308460....353556....362370....362878....362880

..101042...606542...1641534...2748354...3399246...3600306...3627778...3628798

..707584..4697946..14132390..26194542..35142546..38963958..39830282..39914754

.5405530.39330982.130299584.265691456.387129588.453658380.475089392.478739984

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)

Number of permutations of [2n] such that the differences have n runs with the same signs where the first run does not have negative signs.