cp's OEIS Frontend

For n >= 1 a(n) is the size of the centralizer of a transposition in the symmetric group S_(n+1). - Ahmed Fares (ahmedfares(AT)my-deja.com), May 12 2001

For n > 0, a(n) = n! - A062119(n-1) = number of permutations of length n that have two specified elements adjacent. For example, a(4) = 12 as of the 24 permutations, 12 have say 1 and 2 adjacent: 1234, 2134, 1243, 2143, 3124, 3214, 4123, 4213, 3412, 3421, 4312, 4321. - Jon Perry, Jun 08 2003

With different offset, denominators of certain sums computed by Ramanujan.

From Michael Somos, Mar 04 2004: (Start)

Stirling transform of a(n) = [2, 4, 12, 48, 240, ...] is A000629(n) = [2, 6, 26, 150, 1082, ...].

Stirling transform of a(n-1) = [1, 2, 4, 12, 48, ...] is A007047(n-1) = [1, 3, 11, 51, 299, ...].

Stirling transform of a(n) = [1, 4, 12, 48, 240, ...] is A002050(n) = [1, 5, 25, 149, 1081, ...].

Stirling transform of 2*A006252(n) = [2, 2, 4, 8, 28, ...] is a(n) = [2, 4, 12, 48, 240, ...].

Stirling transform of a(n+1) = [4, 12, 48, 240, ...] is 2*A005649(n) = [4, 16, 88, 616, ...].

Stirling transform of a(n+1) = [4, 12, 48, 240, ...] is 4*A083410(n) = [4, 16, 88, 616, ...]. (End)

Number of {12, 12*, 21, 21*}-avoiding signed permutations in the hyperoctahedral group.

Permanent of the (0, 1)-matrices with (i, j)-th entry equal to 0 if and only if it is in the border but not the corners. The border of a matrix is defined the be the first and the last row, together with the first and the last column. The corners of a matrix are the entries (i = 1, j = 1), (i = 1, j = n), (i = n, j = 1) and (i = n, j = n). - Simone Severini, Oct 17 2004

Let M(p, n) denote the n-th central moment of the geometric distribution p(1-p)^x. The sums of the polynomial coefficients of M(p, n)*p^n, ( {}, {1, -1}, {2, -3, 1}, {9, -18, 10, -1}, {44, -110, 90, -25}, ... ), are zero and the sum of their absolute values is 2*a(n). - Federico Provvedi, Sep 09 2020

Let [n] denote the ordered set {1,2,...,n}. The symmetric group S_n consists of the injective mappings p:[n] -> [n]. Such a permutation p has an excedance at position i, 1 <= i < n, if p(i) > i. One well-known interpretation of the Eulerian numbers A(n,k) is that they count the permutations in the symmetric group S_n with k excedances. The triangle of Eulerian numbers is A008292 (but with an offset of 1 in the column numbering). We generalize this definition to restricted permutations as follows.

Let r be a nonnegative integer and let Permute(n,n-r) denote the set of injective maps p:[n-r] -> [n], which we think of as permutations of n numbers taken n-r at a time. Clearly, |Permute(n,n-r)| = n!/r!. We say that p has an excedance at position i, 1 <= i <= n-r, if p(i) > i. Then the r-Eulerian number, denoted by A(r;n,k), is defined as the number of permutations in Permute(n,n-r) having k excedances. Thus the current array of 2-Eulerian numbers gives the number of permutations in Permute(n,n-2) with k excedances. See the example section below for some numerical examples.

Clearly A(0;n,k) = A(n,k). The case r = 1 also produces the ordinary Eulerian numbers A(n,k). There is an obvious bijection from Permute(n,n) to Permute(n,n-1) that preserves the number of excedances of a permutation. Consequently, the 1-Eulerian numbers are equal to the 0-Eulerian numbers: A(1;n,k) = A(0;n,k) = A(n,k).

For other cases of r-Eulerian numbers see A144697 (r = 3), A144698 (r = 4) and A144699 (r = 5). There is also a concept of r-Stirling numbers of the first and second kinds - see A143491 and A143494. If we multiply the entries of the current array by a factor of 2 and then reverse the rows we obtain A120434.

An alternative interpretation of the current array due to [Strosser] involves the 2-excedance statistic of a permutation (see also [Foata & Schutzenberger, Chapitre 4, Section 3]). We define a permutation p in Permute(n,n-2) to have a 2-excedance at position i (1 <=i <= n-2) if p(i) >= i + 2.

Given a permutation p in Permute(n,n-2), define ~p to be the permutation in Permute(n,n-2) that takes i to n+1 - p(n-i-1). The map ~ is a bijection of Permute(n,n-2) with the property that if p has (resp. does not have) an excedance in position i then ~p does not have (resp. has) a 2-excedance at position n-i-1. Hence ~ gives a bijection between the set of permutations with k excedances and the set of permutations with (n-k) 2-excedances. Thus reading the rows of this array in reverse order gives a triangle whose entries count the permutations in Permute(n,n-2) with k 2-excedances.

Example: Represent a permutation p:[n-2] -> [n] in Permute(n,n-2) by its image vector (p(1),...,p(n-2)). In Permute(10,8) the permutation p = (1,2,4,7,10,6,5,8) does not have an excedance in the first two positions (i = 1 and 2) or in the final three positions (i = 6, 7 and 8). The permutation ~p = (3,6,5,1,4,7,9,10) has 2-excedances only in the first three positions and the final two positions.

From Peter Bala, Dec 27 2019: (Start)

This is the array A(1,1,3) in the notation of Hwang et al. (p. 25), where the authors remark that the r-Eulerian numbers were first studied by Shanlan Li (Duoji Bilei, Ch. 4), who gave the summation formulas

Sum_{i = 2..n+1} (i-1)*C(i,2) = C(n+3,4) + 2*C(n+2,4)

Sum_{i = 2..n+1} (i-1)^2*C(i,2) = C(n+4,5) + 7*C(n+3,5) + 4*C(n+2,5)

Sum_{i = 2..n+1} (i-1)^3*C(i,2) = C(n+5,6) + 18*C(n+4,6) + 33*C(n+3,6) + 8*C(n+2,6). (End)

The rows are the reverses of the rows of A054255.

Row sums give A000670.

Column 1 is A000629. - Joerg Arndt, Dec 08 2014

From Vincent Jackson, May 01 2023: (Start)

The formula

T(n, k) = Sum_{i=k..n-1} i!*StirlingS2(n-1, i) + (k-1)!*StirlingS2(n-1,k-1)

can be derived by splitting the weak orders with the first object at rank k into three categories:

1. weak orders where another object (of the n-1 other objects) has rank k,

2. weak orders where all other objects have rank strictly less than k, and

3. weak orders where no other object is at rank k, but some object has rank greater than k.

The number of weak orders in the first category is Sum_{i=k..n-1} i!*StirlingS2(n-1, i), the number of weak orders of length n-1 with number of ranks between k and n-1 (i.e. A084416(n-1,k)). Given a weak order of length n-1 and number of ranks i >= k, the corresponding weak order of length n with the specified object at rank k is formed by inserting the new object into the appropriate rank.

The number of weak orders in the second category is (k-1)!*StirlingS2(n-1,k-1), the number of weak orders of length n-1 with number of ranks k-1. Given a weak order of length n-1 and number of ranks k-1, the corresponding weak order is formed by appending the new object in its own rank.

Lastly, the number of weak orders in the third category is (again) Sum_{i=k..n-1} i!*StirlingS2(n-1, i). Given a weak order of length n-1 and number of ranks k-1, the corresponding weak order is formed by inserting the new object in its own rank after the rank k-1, thereby shifting by one the ranks originally greater than or equal to k. (End)