federico ardila . matemático
associate professor . san francisco state university

. català . español . english .

. . . . . . . . . . . . . . . . . . . .

CATALAN NUMBERS
. . . . . . . . . . . . . . . . . . . .

San Francisco, California
December 29, 2015

Yesterday I returned to San Francisco after a week of being disconnected from the world. Today Luis, the owner of the corner café, treated me to a coffee and told me a news story about Catalonian politics, that leads to a math problem which I'd like to share with you. (I am no expert in Catalonian politics, and I welcome any comments, corrections, and updates. I might decide to publish this somewhere.)

1 - ¿CATALUNYA LLIURE?

Catalonia has spent decades debating whether to separate from Spain, and in recent years, the independentist movement has gained a lot of momentum. In an effort to stay in power, president Artur Mas, a moderate conservative, formed an alliance with sectors of the Catalonian left in favor of independence. However, they fell a few seats short of gaining control of the parliament. To obtain these seats, they need a very unusual alliance with the CUP, a small, anti-capitalist party.

Suddenly, the CUP found itself in an unexpected position of power. After using this power to obtain several political concessions, the party called for an internal vote to decide whether they will support Mas.

Two days ago, 3030 members of the CUP Assembly cast their votes. The result: 1515 in favor of Mas, 1515 against him.

Today the match is still tied. In the meantime, Catalonians are asking themselves (not without some suspicion):
What are the odds?!?!

The problem is an interesting one, and the answer is even better.

2 - THE MATHEMATICAL PROBLEM

Let's suppose that $2m$ people vote SÍ or NO(*) in an election.
The probability that the final result is a tie is approximately $1/{\sqrt{m \pi}}$.
Yes, that's a pi: $\pi = 3.14159\ldots$
In the CUP Assembly there were $2m=3030$ voters.
The chances of a tie were about 1 in 69.

Why $2m$?
. . . . . . . .
Luis told me, laughing: "Imagine a member of the CUP who woke up too late to cast his vote. He could have decided the fate of Catalonia himself!" For a tie to be possible, the number of voters must be even, say $2m$.

Why $1/\sqrt{m \pi}$?
. . . . . . . . . . .
Imagine we register the $2m$ votes, in the order they came in: SÍ, SÍ, NO, SÍ, NO, . . . etc .
Each voter had two options (SÍ or NO), for a total of $2 \times 2 \times \cdots \times 2 = 2^{2m}$ possible votings.

The votings that give rise to ties are those with $m$ SÍs and $m$ NOs. They correspond to the choices of $m$ (out of $2m$ people) who will vote SÍ. There is a name for this: ${2m \choose m}$ = "2m choose m". There is a formula for this, which I could explain to you if we had a bit more time: the number of ties is ${2m \choose m} = \frac{(2m)!}{m!m!}$, where $n!$ denotes the number "n factorial", $n! = 1 \times 2 \times 3 \times \cdots \times (n-1) \times n$. Therefore the probability of a tie is:
$\frac{(\# \textrm{ of ties})}{(\# \textrm{ of possible votings})} = \frac{(2m)!}{m! m! 2^{2m}}$
In the case of Catalonia, if one had a computer within reach, one could ask it to compute this number for $2m=3030$; the result is $1.44938\ldots$%. But I had just returned from a week away from technology, and I had left my phone at home, so I had to use a napkin. (I had to earn the free coffee, no?)

Fortunately, Stirling discovered a very useful approximation: $n! = 1 \times 2 \times 3 \times \ldots \times n \textrm{ is almost equal to } \left(\frac{n}{e}\right)^n \sqrt{2 n \pi}$ We use calculus to derive this. I've proved this formula to my students many times, but it never ceases to amaze me. What are $e = 2.71828\ldots$ and $\pi = 3.14159\ldots$, mathematicians' two favorite numbers, doing there?!

We can use Stirling's formula to simplify the formula above. (My wife May-Li was at the cafe with me and she took the opportunity to dust off her algebra. You should do the algebra too, especially if you are one of those people who enjoy tidying up your desk when it's messy: throwing out everything you don't need, and putting everything else in its right place.) We get:
$\frac{(\# \textrm{ of ties})}{(\# \textrm{ of possible votings})} \approx \frac1{\sqrt{m \pi}},$ and this we can estimate by hand for $2m=3030$, with a bit of effort; ${\sqrt{1515 \pi}}$ is very close to 69.

How good is Stirling's approximation? For $2m=3030$, the real probability of a tie is $\approx 1.44938\ldots$% and Stirling's approximation is $\approx 1.44950\ldots$%. Pretty good!

In any case, the match is even until 2016, when the members of the CUP will decide how to break the tie.

3 - (*) THE FINE PRINT

What does it mean to say that the probability of a tie is 1 in 69?

We can't very well ask the CUP to vote 69 times, and see if they tie exactly once. The only way of making sense of this statement is to choose a model of how people vote. In this case, the model we use is that each person independently chooses to vote SÍ with probability 1/2 or NO with probability 1/2.

Of course this model is not exactly correct -- even if the final outcome was 1515 SÍs and 1515 NOs. But it is probably the most accurate model that allows for a relatively simple analysis, and for this reason, it is the most commonly used.

4 - CATALAN NUMBERS

Allow me a bit of mathematical-poetic license. Let's imagine a delegate of the electoral commission, an unwavering independentist. Following the feminist policy of the CUP, we will use the feminine to include all possible genders. Her deception was enormous when she found out that the final result was a tie. As she was counting the votes one by one she had noticed, with secret optimism, that the SÍ vote was *never* behind!

Now she's asking herself, what are the odds?

5 - THE MATHEMATICAL PROBLEM FOR THE DIE-HARD INDEPENDENTIST.

Let's suppose that $2m$ people vote SÍ or NO(*) in an election, and the end result was a tie. The probability that, as the votes were counted one by one, the SÍ vote was never losing, is exactly $1/(m+1)$. In the case of the CUP vote, where there were 1515 SÍs and 1515 NOs, this probability is exactly 1 in 1516.

In fact, the number of votings which end in a tie, and never favor NO as the votes are counted, is known as the "Catalan number". (No relation to Catalunya). If we had a bit more time, I would explain to you why this number equals $\frac1{m+1}{2m \choose m}$.

The Catalan numbers were discovered by Ming'antu in Mongolia and Euler in Prussia in the 18th century; they are named after the Belgian mathematician Eugène Catalan. These numbers appear all over the place. Richard Stanley collects problems whose solution are the Catalan numbers; he already has more than 200.

In the last 20 years, thanks to the work of experts such as Anna de Mier, Sergi Elizalde and Marc Noy -- and to our hypothetical independentist delegate -- Catalanians have had fascinating stories to tell about Catalan numbers.