Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #44 May 14 2020 21:21:20
%S 0,2,11,61,379,2668,21160,187388,1836396,19753416,231545016,
%T 2939000832,40172455296,588444153984,9197306248320,152803737342720,
%U 2689320607107840,49986863946616320,978529776749959680,20123805782225664000,433785771471677184000,9780622725328777728000
%N a(n)/n! is the expected number of left-to-right maxima in the lexicographical or colexicographical ordering of all the 2-subsets of [n] under a random permutation of [n], when the 2-subsets hold the worst order of ranks.
%C This is a special case (k=2) 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.
%C In the case k=1, a(n) = n!*H(n) = s(n+1,2) = A000254(n), with H(n) being the n-th harmonic number, and s(n,k) being the unsigned Stirling number of the first kind.
%C A formula for a(n) for general k is given in a submitted paper (not in closed form).
%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) + s(n,2) + (n-1)! with the initial condition a(1)=0.
%F a(n) = s(n+1,3) + s(n+1,2) - n!, where s(n,k) is the unsigned Stirling number of the first kind.
%e For n=4, the lexical ordering of all the 2-subsets of [4] is 12,13,14,23,24,34. If we choose the order of ranks to be 12<13<14<23<24<34, then under the permutation 2314, the sequence of 2-subsets becomes 23,12,13,24,34,14, in which there are 3 left-to-right maxima 23,24,and 34. Summarizing over all permutations of [4], we can obtain that the total number of left-to-right maxima is 61, which is the largest over all possible orders of ranks on these 6 2-sebsets.
%o (PARI) a(n) = abs(stirling(n+1, 3, 1)) + abs(stirling(n+1, 2, 1)) - n!; \\ _Michel Marcus_, Jun 29 2019
%Y Cf. A000254 (k=1), A308860 (k=3).
%K nonn
%O 1,2
%A _Jin-Yi Liu_, Jun 28 2019