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

%I #25 May 15 2023 08:43:26

%S 1,2,1,6,5,2,26,25,18,6,150,149,134,84,24,1082,1081,1050,870,480,120,

%T 9366,9365,9302,8700,6600,3240,720,94586,94585,94458,92526,82320,

%U 57120,25200,5040,1091670,1091669,1091414,1085364,1038744,871920,554400,221760,40320

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

%C The rows are the reverses of the rows of A054255.

%C Row sums give A000670.

%C Column 1 is A000629. - _Joerg Arndt_, Dec 08 2014

%C From _Vincent Jackson_, May 01 2023: (Start)

%C The formula

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

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

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

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

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

%C 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.

%C 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.

%C 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)

%F From _Vincent Jackson_, May 01 2023: (Start)

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

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

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

%e Triangle starts:

%e 01: 1;

%e 02: 2, 1;

%e 03: 6, 5, 2;

%e 04: 26, 25, 18, 6;

%e 05: 150, 149, 134, 84, 24;

%e 06: 1082, 1081, 1050, 870, 480, 120;

%e 07: 9366, 9365, 9302, 8700, 6600, 3240, 720;

%e 08: 94586, 94585, 94458, 92526, 82320, 57120, 25200, 5040;

%e 09: 1091670, 1091669, 1091414, 1085364, 1038744, 871920, 554400, 221760, 40320;

%e 10: 14174522, 14174521, 14174010, 14155350, 13950720, 12930120, 10190880, 5957280, 2177280, 362880;

%e ...

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

%Y Cf. A054255, A008277, A028246.

%K nonn,tabl

%O 1,2

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

%E Corrected by _Alois P. Heinz_, Dec 08 2014

%E Name clarified by _Vincent Jackson_, May 01 2023