cp's OEIS Frontend

Permutations on n letters without double falls. A permutation w has a double fall at k if w(k) > w(k+1) > w(k+2) and has an initial fall if w(1) > w(2).

Hankel transform is A055209. - Paul Barry, Jan 12 2009

Increasing colored 1-2 trees of order n with choice of two colors for the right branches of the vertices of outdegree 2 except those vertices on the path from the root to the leftmost leaf. - Wenjin Woan, May 21 2011

a(n) is the number of permutations of length n that avoid the consecutive pattern 12345 (or equivalently 54321).

Sum_{k>0} k*T(n,k) = A249249(n).

a(n) is the number of permutations on [n] that avoid the consecutive pattern 1234. It is the same as the number of permutations which avoid 4321.

From Petros Hadjicostas, Aug 06 2019: (Start)

André (1895) first defined these numbers. In his notation, T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1.

His triangle is as follows (p. 148):

Q_{2,2}

Q_{3,2}

Q_{4,2} Q_{4,4}

Q_{5,2} Q_{5,4}

Q_{6,2} Q_{6,4} Q_{6,6}

Q_{7,2} Q_{7,4} Q_{7,6}

...

He has 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.

His recurrence is Q(n, s) = s * Q(n-1, s) + (n - s + 1) * Q(n-1, s-2) for n >= 3 and s >= 2. (Obviously, for s odd, we get Q(n, s) = 0 + 0 = 0.)

In terms of the current array, André's (1895) recurrence becomes T(n, k) = (2*k + 2) * T(n-1, k) + (n - 2*k) * T(n-1, k-1) for n >= 2 and 1 <= k <= n with T(n, 0) = 2^(n-1) for n >= 1. In this recurrence, we assume T(n, k) = 0 for k >= ceiling(n/2) or k < 0. (End)

From Petros Hadjicostas, Aug 07 2019: (Start)

We clarify further the quantity Q(n, s) defined by André (1895). In his paper, André considers circular permutations of [n] and deals with maxima, minima, and so-called "séquences" in a permutation.

The term "séquence" in a permutation, as used by André in several of his papers in the 19th century, means a list of consecutive numbers in the permutation that go from a maximum to a minimum, or vice versa, and do not contain any interior minima or maxima. This terminology is also repeated in Ex. 13 (pp. 260-261) by Comtet (even though he refers to the corresponding indices rather than the numbers in the permutation itself).

Some authors call these so-called "séquences" (defined by André and Comtet) "alternate runs" (or just "runs"). Here we are actually dealing with "circular runs" if we read these so-called "séquences" in ascending order in one of the two directions on a circle.

Q(n, s) is the number of circular permutations of [n] (out of the (n-1)! in total) that have exactly s of these so-called "séquences" ("alternate runs").

André (1895) proves that, in a circular permutation of [n], the number of maxima equals the number of minima and that the number of his so-called "séquences" ("alternate runs") is always even (i.e., Q(n, s) = 0 for s odd).

He also shows that, if v = floor(n/2), then the only possible values for the length of a so-called "séquence" ("alternate run") in a circular permutation of [n] are 2, 4, ..., 2*v. That is why Q(n, s) = 0 when either s is odd, or n <= 1, or s > n.

Note that Sum_{t = 1..floor(n/2)} Q_{n, 2*t} = Sum_{t = 1..floor(n/2)} T(n-1, t-1) = (n-1)! = total number of circular permutations of [n].

Since T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1, we conclude that the number of (linear) permutations of [n] with k peaks equals the number of circular permutations of [n+1] with exactly 2*(k+1) of these so-called "séquences" ("alternate runs"). (End)

From Petros Hadjicostas, Aug 08 2019: (Start)

The author of this array indirectly assumes that a "peak" of a (linear) permutation of [n] is an interior maximum of the permutation; i.e., we ignore maxima at the endpoints of a permutation.

Similarly, a "valley" of a (linear) permutation of [n] is an interior minimum of the permutation; i.e., we ignore minima at the endpoints of the permutation.

Since the complement of a permutation a_1 a_2 ... a_n (using one-line notation, not cycle notation) is (n+1-a_1) (n+1-a_2) ... (n+1-a_n), it follows that, for n >= 2 and 0 <= k <= ceiling(n/2) - 1, T(n, k) is also the number of (linear) permutations of [n] with exactly k valleys. (End)

Row n (n>=2) contains n-1 entries.

Sum of entries in row n is n! = A000142(n).

Sum_{k=0..n-2} k*T(n,k) = A005990(n-1).

The first Maple program yields (by straightforward counting) the generating polynomial of a specified row n.

Suppose a < b, c < b, and c < d. To avoid abcd means not to have four consecutive letters such that the first letter is less than the second one, the third letter is less than the second one, and the third letter is less than the last one.

T(n,k) is also the number of permutations of [n] with exactly k occurrences of the consecutive step pattern up, up, down.

From Vaclav Kotesovec, Aug 26 2014: (Start)

Column k is asymptotic to c(k) * (3*sqrt(3)/(2*Pi))^n * n! * n^k.

Conjecture: c(k) = c(0) * (c(0)-1)^k / (3^k * k!).

Verified numerically:

c(0) = 1.96650951227123825842868... = (1+exp(Pi/sqrt(3)))*sqrt(3)/(2*Pi)

c(1) = 0.63355004986067503869384...

c(2) = 0.10205535828170995196503...

c(3) = 0.01095971939528021798...

c(4) = 0.000882722753946826148...

c(5) = 0.00005687732922585807984...

c(6) = 0.000003054026651631929902...

c(7) = 0.0000001405593242634352116...

c(8) = 0.00000000566049683079281633...

c(9) = 0.0000000002026268159682390665...

c(10)= 0.00000000000652802483581788974...

c(20)= 1.172921625090753...*10^(-28)

c(30)= 1.2959323...*10^(-47)

c(40)= 5.0751...*10^(-68)

(End)

Suppose j