login
a(n)/n! is the expected number of left-to-right maxima in the lexicographical or colexicographical ordering of all the 3-subsets of [n] under a random permutation of [n], when the 3-subsets hold the worst order of ranks.
1

%I #23 May 14 2020 21:21:26

%S 0,0,6,50,379,3023,26193,248092,2565080,28836332,350847628,4598548392,

%T 64645657608,970762440048,15514297672464,262985728086144,

%U 4713910512720768,89097880064868864,1771270259515278336,36950742840576268800,807153610378856716800,18426068050750227993600

%N a(n)/n! is the expected number of left-to-right maxima in the lexicographical or colexicographical ordering of all the 3-subsets of [n] under a random permutation of [n], when the 3-subsets hold the worst order of ranks.

%C This is a special case (k=3) of a general (n,k)-team-hiring-problem, which is an extension to the assistant-hiring problem in Section 5.1 of the textbook Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.

%H Jin-Yi Liu, <a href="https://hal.archives-ouvertes.fr/hal-02485153">On a problem of team hiring</a>, hal-02485153, Computer Science [cs], 2020.

%F a(n) = n*a(n-1) + (n-1)*s(n-1,3) + (2n-1)*s(n-1,2) + (n-2)!, with the initial condition a(3)=6, and with s(n,k) being the unsigned Stirling number of the first kind.

%o (PARI) a(n) = if (n<=2, 0, if (n==3, 6, n*a(n-1) + (n-1)*abs(stirling(n-1,3,1)) + (2*n-1)*abs(stirling(n-1,2,1)) + (n-2)!)); \\ _Michel Marcus_, Jun 30 2019

%Y Cf. A000254 (k=1), A308729 (k=2).

%K nonn

%O 1,3

%A _Jin-Yi Liu_, Jun 28 2019

%E More terms from _Michel Marcus_, Jun 30 2019