Can Your Team Self-Organize?

In a team-building game, everyone writes down a distinct number, then independently places their name at a random spot on a line. The team’s score is the length of the longest increasing subsequence of the revealed numbers, read left to right. With four people placing themselves at random, what score do you expect on average?

The Fiddler, Zach Wissner-Gross, September 19, 2025(original post)

Solution

The positions make a uniformly random permutation of the four distinct values, and the score is its longest increasing subsequence (LIS). By the Robinson–Schensted correspondence the LIS equals the length $\lambda_1$ of the first row of the associated Young diagram, and the number of permutations of $n$ with a given shape $\lambda$ is $(f^\lambda)^2$, where $f^\lambda$ is the number of standard tableaux. For $n=4$: $$\begin{array}{c|ccccc} \lambda & (4) & (3,1) & (2,2) & (2,1,1) & (1^4)\\\hline (f^\lambda)^2 & 1 & 9 & 4 & 9 & 1\\ \lambda_1 & 4 & 3 & 2 & 2 & 1 \end{array}$$ so the LIS distribution is $\{4\!:\!1,\,3\!:\!9,\,2\!:\!13,\,1\!:\!1\}$ over $24$ permutations and $$E[\text{LIS}]=\frac{4\cdot1+3\cdot9+2\cdot13+1\cdot1}{24}=\frac{58}{24}=\frac{29}{12}\approx\boxed{2.417}.$$

The computation

With four players the orderings are just the $24$ permutations: compute each one’s longest increasing subsequence by patience sorting and average.

import bisect, itertools as it
from fractions import Fraction as F
def lis(p):
    t = []
    for x in p:
        i = bisect.bisect_left(t, x); t[i:i+1] = [x]
    return len(t)
print(F(sum(lis(p) for p in it.permutations(range(4))), 24))   # 29/12

Extra Credit

Now ten people play instead of four. What is the expected score?

Solution

The same identity gives $E[\text{LIS}]=\dfrac1{n!}\sum_{\lambda\vdash n}\lambda_1\,(f^\lambda)^2$, with $f^\lambda$ from the hook-length formula. Summed over all partitions of $10$, $$E[\text{LIS}]=\frac{3146141}{725760}\approx\boxed{4.335}.$$ (The source’s value is paywalled; this exact figure is my own.)

The computation

Ten players make $10!$ a touch much to sweep, so sample instead: draw a million random orderings of ten, take the longest increasing subsequence of each, and average. It lands on $4.335$.

import numpy as np
rng = np.random.default_rng(0); M = 1_000_000; total = 0
for _ in range(M):
    total += lis(rng.permutation(10))
print(round(total / M, 4))               # ~4.335