Misplaced Priorities - Part 4 [Solution]

Solution for the week of 1/26/25

Our problem from 1/26/25 was

Let’s assume that we are boarding a rather strange and simplified plane with only one seat per row. Passengers are ordered randomly and each requires a fixed amount of time Δ_t to stow their luggage. Passengers can move between rows quickly enough that we can ignore the time it takes for them to move in the aisle. However, as we have all experienced, the aisles of planes are never large enough for you to get around someone who is stowing their luggage so if the person in front of you is in the middle of stowing, you must wait until they are done before you can proceed. The question is, how long does it take for a plane with 10 seats and 10 randomly ordered passengers to board. What about n seats and n passengers?

For those that tried this problem is was a tough one but it introduced some very interesting combinatorial concepts! To be clear, I did not—nor would I expect any but the most brilliant readers—to get this without doing some research and looking up how to do this problem. Personally, I got stuck when I got to the point of having to try and count the number of longest decreasing subsequences. But let’s not get ahead of ourselves.

The first challenge with this problem is making sense of how much time a given permutation takes to board. It’s easy enough to determine by hand when you’re given a specific permutation, but it’s not completely obvious how to generalize this. After playing around with the permutations on 3 elements and 4 elements, you may notice a pattern. To start, let’s get a little notation set up. We’ll write order of people boarding as

\(\sigma= v_1, v_2, \ldots, v_n\)

Where v_i is assigned seat number of the i-th person in line. We will assume that the seats are numbered 1 through n with 1 being at the back of the plane and n at the front. Hopefully, after the last 3 puzzles in this series, it should be clear that this line can be represented as a permutation.

If we examine the blocking condition, a block occurs when we have two people v_i and v_j where v_i > v_j and i < j. Basically, the j-th person in line has a seat that’s farther back on the plane than the i-th person but i-th person is before the j-th in the line. Similarly if there is another k for which v_i > v_j > v_k and i < j < k the we will have two blockages, so on and so forth. What this hopefully illustrates is that, to determine the amount of time needed to board the plane, we must fine the longest possible sequence of passengers such that v_i > v_j > v_k > … and i < j < k < … If we assume that this sequence has m passengers then it will take m*Δ_t time to board.

Turns out this problem has a name is is well-studied. It’s called the longest increasing subsequence (LIS). In our case we’re concerned about the longest decreasing subsequence (LDS) but given that we’re computing probabilities over all possible permutations of passenger orderings, we know by symmetry that these two types of sequences will have the same statistics.

Cool! we have a robust way of determining the amount of time needed to board for a given permutation. Now we just need a way of counting all the permutations that result in a LDS of length i so that we can compute

\(\mathbb{E}[T] = \Delta_t \sum_{i=1}^n i (\text{num permutations with |LDS|=i})\)

One thing we can observe pretty easily is that the entire permutation can be decomposed into disjoint decreasing subsequences. As long as we ensure that the largest possible LDS is one of these subsequences, we can organize the rest of the elements into their own smaller decreasing subsequences. In this way, the LDS of n elements is related to the integer partition of n where each integer of the partition represents the length of one of the disjoint decreasing subsequences [see below].

This illustrates how any permutation can be decomposed into disjoint sets of decreasing subsequences. The color of the elements represent which decreasing subsequence it belongs to.

One simple way we can construct this partition is by finding the LDS of a permutation, moving these element into their own set, and repeating this process on the remaining elements until all elements are grouped. Let’s call this sizes of the decreasing subsets the LDSD (longest decreasing subsequence decomposition). Of course, counting partitions isn’t exactly the most elegant method but it’s certainly better than computing the LDS for every possible permutation. Now in order to take advantage of this observation, we need a way to calculate the number of permutations whose LDSD equals a particular partition. And how do we do that? That is where I got stuck!

After consulting the literature a bit, I quickly came across the Young’s Tableau. The Young’s Tableau is constructed from a Young’s diagram, which is effectively just a graphical representation of a partition with the partition sizes organized into rows of squares in descending order.

Young diagram of the partition (5,4,1)

To construct a Young’s Tableau, you fill in the boxes with the elements you are considering such that each row and each column is increasing (strictly increasing in our case). Given the increasing structure, we can begin to intuit that the Young’s Tableau encodes LDSD. The exact relationship is given by the Robinson–Schensted correspondence

\({\displaystyle \sum _{\lambda \in {\mathcal {P}}_{n}}(f^{\lambda })^{2}=n!}\)

which lets us know that if there are k Young’s Tableau for a given partition, there are k² permutations that construct that Young’s Tableau. Of course, then we need to know how compute the number of Young’s Tableau we can construct for a given partition/Young’s diagram. Here again I had to do a bit of research which revealed the hook length formula which computes exactly this quantity

\({\displaystyle f^{\lambda }={\frac {n!}{\prod h_{\lambda }(i,j)}}}\)

where h(i,j) is the number of boxes to the right and below the box at (i,j) including itself.

We shouldn’t bad if you couldn’t derive this ourselves. Turns out the combinatorial proof (the approach I image most people would attempt) is very involved and took 30 years to discover after the hook length formula was originally discovered. There is a simple inductive proof of the equation’s validity but you need to already know the function :/

And that’s pretty much it! Putting this all together, we can follow the following steps to get our answer:

1. Generate all integer partitions of n.

2. For each integer partition, compute the number of Young’s Tableau using the hook length formula. The size of the LDS is simply the largest part of the partition

3. For each integer partition, multiply the the size of the LDS by the square of the number of Young’s Tableau

4. Sum all these values and divide by all the permutations n!

\(\mathbb{E}[T] = \frac{ \Delta_t \displaystyle \sum_{\lambda \in P_n} \max(\lambda) \left( \frac{n!}{\prod h_{\lambda }(i,j)} \right)^2 }{n!}\)

Where P_n is the set of all partitions of n and max(λ) is the largest part of the partition λ.

For anyone interested more generally in the longest increasing subsequence and its associated statistics, here are some resources I enjoyed reading to learn more.