A090665 Triangle read by rows: T(n,k) = number of preferential arrangements of n things where the first object has rank k.

1, 2, 1, 6, 5, 2, 26, 25, 18, 6, 150, 149, 134, 84, 24, 1082, 1081, 1050, 870, 480, 120, 9366, 9365, 9302, 8700, 6600, 3240, 720, 94586, 94585, 94458, 92526, 82320, 57120, 25200, 5040, 1091670, 1091669, 1091414, 1085364, 1038744, 871920, 554400, 221760, 40320

Offset: 1

Author

Eugene McDonnell (eemcd(AT)mac.com), Dec 16 2003

Keywords

• nonn
• tabl

Comments

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)

Examples

			Triangle starts:
01: 1;
02: 2, 1;
03: 6, 5, 2;
04: 26, 25, 18, 6;
05: 150, 149, 134, 84, 24;
06: 1082, 1081, 1050, 870, 480, 120;
07: 9366, 9365, 9302, 8700, 6600, 3240, 720;
08: 94586, 94585, 94458, 92526, 82320, 57120, 25200, 5040;
09: 1091670, 1091669, 1091414, 1085364, 1038744, 871920, 554400, 221760, 40320;
10: 14174522, 14174521, 14174010, 14155350, 13950720, 12930120, 10190880, 5957280, 2177280, 362880;
...
		

Crossrefs

Cf. A054255, A008277, A028246, A083410.

Programs

Mathematica

T = {n, k} |-> 2*Sum[i!*StirlingS2[n-1, i], {i, k, n-1}] + (k-1)i!*StirlingS2[n-1, k-1]  (* Vincent Jackson, May 01 2023 *)

Formula

From Vincent Jackson, May 01 2023: (Start)

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

T(n, k) = 2*A084416(n-1,k) + (k-1)!*StirlingS2(n-1,k-1).

T(n, k) = A084416(n-1,k) + A084416(n-1,k-1). (End)

Sum_{k=1..n} k * T(n,k) = A083410(n). - Alois P. Heinz, Feb 20 2025

Extensions

Corrected by Alois P. Heinz, Dec 08 2014

Name clarified by Vincent Jackson, May 01 2023