cp's OEIS Frontend

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)

As we showed in A160485 the n-th term of the coefficients of matrix row BS1[1-2*m,n] for m = 1 , 2, 3, .. , can be generated with the RBS1(1-2*m,n) polynomials.

We define the o.g.f.s. of these polynomials by GFRBS1(z,1-2*m) = sum(RBS1(1-2*m,n)*z^(n-1), n=1..infinity) for m = 1, 2, 3, .. . The general expression of these o.g.f.s. is GFRBS1(z,1-2*m) = (-1)*RB(z,1-2*m)/(z-1)^m.

The RB(z,1-2*m) polynomials lead to a triangle that is a subtriangle of the 'double triangle' A008971. The even rows of the latter triangle are identical to the rows of our triangle.

The Maple program given below is derived from the one given in A008971.

From Petros Hadjicostas, Aug 10 2019: (Start)

The recurrence about T(n, k) and the equation that connects T(n, k) to P(n, k) = A059427(n,k), which are given below, appear on p. 159 of the book by David and Barton (1962). The initial conditions, however, for their triangular array S^*{N,t} are slightly different, but there is an agreement starting at t = k = 1. They do not provide tables for S^*{N,t} (that matches the current array T(n, k) for N = n >= 0 and t = k >= 1).

Despite the slightly different initial conditions between T(n, k) and S^*_{N,t} (from p. 159 in the book), the recurrence given below can be proved very easily from the recurrence for the row polynomials R_n(x) given in Shi-Mei Ma (2011, 2012). (End)