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,2

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)

Links

Table of n, a(n) for n=1..45.

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)

Example

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;
...

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 *)

Crossrefs

Cf. A054255, A008277, A028246.

Sequence in context: A228175 A118980 A351385 * A347952 A376674 A361198

Adjacent sequences: A090662 A090663 A090664 * A090666 A090667 A090668

Keyword

nonn,tabl

Author

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

Extensions

Corrected by Alois P. Heinz, Dec 08 2014

Name clarified by Vincent Jackson, May 01 2023

Status

approved