|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
