login
A308729
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.
1
0, 2, 11, 61, 379, 2668, 21160, 187388, 1836396, 19753416, 231545016, 2939000832, 40172455296, 588444153984, 9197306248320, 152803737342720, 2689320607107840, 49986863946616320, 978529776749959680, 20123805782225664000, 433785771471677184000, 9780622725328777728000
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
Cf. A000254 (k=1), A308860 (k=3).
Sequence in context: A275229 A074615 A126034 * A034726 A256933 A162274
KEYWORD
nonn
AUTHOR
Jin-Yi Liu, Jun 28 2019
STATUS
approved