OFFSET
1,2
COMMENTS
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.
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.
A formula for a(n) for general k is given in a submitted paper (not in closed form).
LINKS
Jin-Yi Liu, On a problem of team hiring, hal-02485153, Computer Science [cs], 2020.
FORMULA
a(n) = n*a(n-1) + s(n,2) + (n-1)! with the initial condition a(1)=0.
a(n) = s(n+1,3) + s(n+1,2) - n!, where s(n,k) is the unsigned Stirling number of the first kind.
EXAMPLE
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.
PROG
(PARI) a(n) = abs(stirling(n+1, 3, 1)) + abs(stirling(n+1, 2, 1)) - n!; \\ Michel Marcus, Jun 29 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Jin-Yi Liu, Jun 28 2019
STATUS
approved