The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an explanation.
For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following:
//Given array a[1], ... a[n]
for i = 1 to n:
for j = i+1 to n:
if a[i] > a[j]:
swap(a[i],a[j])
It looks like bubble sort, but is closer to selection sort. It is easy to see why it works: in each iteration of the outer loop, a[i]
is set to be the smallest element of a[i…n]
.
In a programming contest many years ago, one of the problems essentially boiled down to sorting:
Given a list of distinct values $W_1, W_2, \dots, W_n$, find the indices when it is sorted in ascending order. In other words, find the permutation $(S_1, S_2, \dots, S_n)$ for which $W_{S_1} < W_{S_2} < \dots < W_{S_n}$.
This is simply a matter of operating on the indices rather than on the array directly, so the correct code would be:
//Given arrays S[1], ..., S[n] (initially S[i]=i ∀i) and W[1], ..., W[n]
for i = 1 to n:
for j = i+1 to n:
if W[S[i]] > W[S[j]]:
swap(S[i],S[j])
But in the heat of the contest, I instead coded a program that did, incorrectly:
for i = 1 to n:
for j = i+1 to n:
if W[i] > W[j]:
swap(S[i],S[j])
I realised the mistake after the contest ended, and later while awaiting the results, with desperate optimism I tried to figure out the odds that for some inputs, my program would accidentally give the right answer anyway. Specifically, I counted the number of permutations of an arbitrary list $W_1, \dots, W_n$ with distinct values (since only their order matters, not their actual values) for which the incorrect algorithm above gives the correct answer, for each n:
n Number of "lucky" permutations
0 1
1 1
2 2
3 5
4 14
5 42
6 132
7 429
8 1430
9 4862
10 16796
11 58786
12 208012
These are the Catalan numbers! But why? I've tried to prove this occasionally in my free time, but never succeeded.
What I've tried:
The (pseudo)algorithm can be represented in more formal notation as the product of all inversions in a permutation. That is, we want to prove that the number of permutations $\sigma \in S_n$ such that $$\prod_{i=1}^{n}\prod_{\substack{j \in \left\{i+1,i+2,\ldots,n\right\}; \\ \sigma_i > \sigma_j}}(i,j) = \sigma^{-1}$$ (with the convention that multiplication is done left to right) is $C_n$. This change of notation does not make the problem any simpler.
I briefly skimmed through Stanley's famous list of Catalan problems, but this does not seem to be (directly) in the list. :-)
Some computer experimentation suggests that the lucky permutations are those that avoid the pattern 312, the number of which is apparently the Catalan numbers. But I have no idea how to prove this, and it may not be the best approach...