cp's OEIS Frontend

A big descent in a permutation (x_1,x_2,...,x_n) is a position i such that x_i - x_(i+1) >= 2. T(n,k) is the number of permutations on [n] with k big descents. The mean number of big descents in permutations on [n] is (n-1)(n-2)/(2n). For S(n,k):=number of permutations on [n] with k small descents, that is, indices i such that x_i - x_(i+1) = 1, the gf Sum_{n>=0,k>=0} S(n+1,k) x^n/n! y^k is 1/(E^(x(1 - y))*(1 - x)^2).

T(n,k) is also the number of recursive trees with n+1 vertices and k+2 leaves. (A recursive tree on n vertices is a rooted tree with the vertices labeled 1, 2, ... n, such that the root is labeled 1 and every path starting at the root is increasing with respect to the labels.) - Taral Guldahl Seierstad (seiersta(AT)informatik.hu-berlin.de), Oct 12 2006

In the comment by T. G. Seierstad, the term "leaf" means "vertex incident with exactly one edge." Thus if the root has only one child, the root is a leaf. T(n,k) is the number of trees rooted at 0 on vertex set {0,1,2,...,n} that contain k+1 leaves (here a leaf is a vertex with no children) and such that, for i = 0,1,...,n-1, there is exactly one vertex larger than i incident with i. For example, T(3,0) = 4 counts {0->1->2->3}, {0->1->3->2}, {0->2->3->1}, {0->3->2->1} and T(3,1) = 2 counts {0->2->1,2->3}, {0->3->1,3->2} (the arrows indicate edges directed away from the root). - David Callan, Feb 01 2007

From Peter Bala, Sep 19 2008: (Start)

If we divide the entries of this array by 2 and then read the rows in reverse order we obtain the array of 2-Eulerian numbers A144696.

Two equivalent interpretations of this array are:

A) Define a permutation p in the symmetric group S_n to have an r-excedance at position i, 1 <= i <= n-1, if p(i) >= i+r. This array gives the number of permutations in the symmetric group S_n having k 2-excedances (see the last chapter of [Riordan]). For example, in the symmetric group S_3, the two permutations (3,1,2) and (3,2,1) have a single 2-excedance, while the remaining four permutations have no 2-excedances. Hence T(3,0) = 4 and T(3,1) = 2. The triangle of Eulerian numbers A008292 enumerates permutations by 1-excedances (with an offset of 1 in the column indexing).

B) T(n,k) gives the number of permutations in the group S_(n+1) starting with a 2 and having k+1 descents [Conger]. For example, in the symmetric group S_4, the permutations (2,1,4,3) and (2,4,3,1) start with a 2 and have two descents so T(3,1) = 2, while the four permutations (2,1,3,4), (2,3,1,4), (2,3,4,1) and (2,4,1,3) start with a 2 and have a single descent giving T(3,0) = 4. (End)

Appears to be mirror image of A199335. - Dale Gerdemann, Apr 18 2015

T(n,k) gives the number of permutations in the group S_n with k+1 special descents, where a special descent is defined as either a normal descent or if the permutation starts with 1. For example, in the symmetric group S_3, the permutations (1,3,2) and (3,2,1) have 2 special descents so T(3,1)=2, while the permutations (1,2,3), (2,1,3), (2,3,1), and (3,1,2) have one special descent, giving T(3,0)=4. - Tanya Khovanova and Rich Wang, Jan 31 2023

Binomial transform of A001339.

Polynomials in A010027 evaluated at 3. - Ralf Stephan, Dec 15 2004

From Dennis P. Walsh, Sep 18 2013: (Start)

a(n) is the number of rooted labeled forests that satisfy the following conditions:

(i) there are 4 roots labeled 1, 2, 3, and 4;

(ii) there are n non-root vertices labeled 5,..., n+4;

(iii) the trees with roots 1 and 2 have width one;

(iv) the trees with roots 3 and 4 have height at most one.

To construct such a forest, for k=0,...,n, we take the following steps:

(1) choose k non-root vertices for trees with roots 1 and 2;

(2) construct width-one trees on roots 1 and 2 with the k non-root vertices;

(3) with the n-k remaining non-root vertices construct trees of height at most one on roots 3 and 4.

Thus a(n) is the sum (over k) of the product of the number of ways to do each step: a(n)=sum(k=0..n, binomial(n,k)*(k+1)!*2^(n-k)). (End)

Riordan array (1/(1-x), x^2/(1-x)^2).

A skewed version of triangular array A085478.

Mirror image of triangle in A098158.

Sum_{k, 0<=k<=n} T(n,k)*x^k = A138229(n), A006495(n), A138230(n),A087455(n), A146559(n), A000012(n), A011782(n), A001333(n),A026150(n), A046717(n), A084057(n), A002533(n), A083098(n),A084058(n), A003665(n), A002535(n), A133294(n), A090042(n),A125816(n), A133343(n), A133345(n), A120612(n), A133356(n), A125818(n) for x = -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 respectively.

Sum_{k, 0<=k<=n} T(n,k)*x^(n-k) = A009116(n), A000007(n), A011782(n), A006012(n), A083881(n), A081335(n), A090139(n), A145301(n), A145302(n), A145303(n), A143079(n) for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 respectively.

From Gus Wiseman, Jul 08 2025: (Start)

After the first row this is also the number of subsets of {1..n-1} with k maximal runs (sequences of consecutive elements increasing by 1) for k = 0..n. For example, row n = 5 counts the following subsets:

{} {1} {1,3} . . .

{2} {1,4}

{3} {2,4}

{4} {1,2,4}

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

{2,3}

{3,4}

{1,2,3}

{2,3,4}

{1,2,3,4}

Requiring n-1 gives A202064.

For anti-runs instead of runs we have A384893.

(End)