# Uniformly at Random

## The number of ways of shuffling a cabinet

No doubt the first question on the mind of anyone reading the previous post concerning John A. Macdonald’s double shuffle is, “In how many ways could Macdonald have appointed his former cabinet members to new ministries so that no minister was appointed to the same position that he had held in the previous Macdonald government?”

Letting $n$ denote the number of ministers in Macdonald’s cabinet, the answer to this question is $d(n)$, the number of derangements of an $n$-element set. A derangement is a permutation such that no element is mapped to itself. The number of derangements of an $n$-element set is well-known to be $d(n) = n! \sum_{i=0}^n (-1)^i/i!$, which turns out to be simply the nearest integer to $n!/e$.

I am too lazy to bother writing a proof of this formula here, so instead I refer the reader to, for example, the book Concrete Mathematics by Graham, Knuth and Patashnik.

Written by uncudh

February 27, 2009 at 4:44 pm

Posted in math

Tagged with ,

## Macdonald’s double shuffle

with one comment

In 1858, Canadian Premier John A. Macdonald (later, first prime minister of the Dominion of Canada) pulled off one of the most brilliant (and underhanded) political manoeuvres in Canadian history. This feat of parliamentary trickery is known as the “double shuffle”.

It began with a debate over the proposed location of Ottawa for the new capital of the province of Canada. Previously, the capital of the province rotated every four years among Toronto, Montreal, and Quebec City. This state of affairs was clearly impractical, so it was decided that there should be a permanent capital. The town of Ottawa was proposed, ostensibly at the suggestion of Queen Victoria. However, there were many Canadian parliamentarians who opposed this location. In 1858, Brown, the leader of the opposition, passed a motion in the Canadian parliament expressing reservations regarding the choice of Ottawa as the capital. The premier, Macdonald, declared that the motion was an insult to the Queen (since Ottawa was supposedly her choice), and resigned his position along with his entire cabinet in protest. The Macdonald government thus fell.

In response, the Governor-General approached the opposition leader Brown and requested him to form a government. Unfortunately, Brown ran afoul of a constitutional technicality: at that time, any incoming cabinet minister was required to temporarily resign his seat in parliament and seek re-election in a by-election. With his cabinet temporarily absent from parliament, Brown would not have enough members to retain a majority in the house. His government was thus doomed to fall in short order.

Indeed, Brown’s goverment was promptly defeated. It was now once more up to the Governor-General to decide what would happen next. Brown requested that he dissolve parliament and call a general election, but instead the Governor-General decided that he would ask Macdonald to try to form a government once more. However, if Macdonald attempted to form a cabinet, he would find himself in the same situation as Brown: his cabinet would be forced to give up their seats and seek re-election to the house, and their temporary absence would cost Macdonald his control over parliament. His government would surely fall by the same sequence of events that led to the demise of the Brown government.

However, Macdonald found a constitutional loophole that would allow him to break this cycle: even though incoming cabinet ministers were required to resign their seats and run for re-election, there was a special exception that stated that if a minister resigned a cabinet position and took up a new cabinet position within one month’s time, he was not required to seek re-election. Clearly the intent of the provision was to allow a premier to make adjustments to his cabinet without incurring the cost of a by-election every time. Macdonald however exploited this exception in a very clever and devious manner: he swore in his old cabinet ministers, but each one was appointed to a ministry different from the one he had previously held (Macdonald appointed himself postmaster general). Since his cabinet ministers had resigned their offices just a few days earlier (certainly less than one month) and since they were now each taking up entirely different cabinet portfolios, Macdonald claimed that they were exempt from having to resign their seats and run for re-election. The very next day, Macdonald then moved all of his cabinet ministers back into their original portfolios (the ones they held during the previous Macdonald government). Macdonald thus avoided the need to have any of his cabinet ministers resign his seat.

Clearly Macdonald’s “double shuffle” was in no way in keeping with the spirit of the law, but he had technically complied with the letter of the law, and had thereby manage to completely outmanoeuvre Brown.

Written by uncudh

February 27, 2009 at 4:42 pm

Posted in history

Tagged with ,

## The Fine-Wilf Theorem

The Fine-Wilf Theorem is as follows. Supppose $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ are two infinite periodic sequences with periods $p$ and $q$ respectively. If $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ agree on their first $p+q-\gcd(p,q)$ terms then the two sequences are identical.

We present here the elegant algebraic proof given as the solution to Problem 134 in Bollobas’ book The Art of Mathematics and attributed by Bollobas to Ernst Straus.

We first define formal power series $F(X) = \sum_{n \geq 0} a_n X^n$ and $G(X) = \sum_{n \geq 0} b_n X^n$. By the periodicity hypothesis, we have $F(X) = P(X)/(1-X^p)$ and $G(X) = Q(X)/(1-X^q)$ for some polynomials $P,Q$ of maximum degrees $p-1$ and $q-1$ respectively. However, since $(1-X^{\gcd(p,q)})$ divides each of $(1-X^p)$ and $(1-X^q)$, we also have

$F(X) - G(X) = [(1-X^q)P(X) - (1-X^p)Q(X)](1-X^p)^{-1}(1-X^q)^{-1} = (1-X^{\gcd(p,q)})R(X)(1-X^p)^{-1}(1-X^q)^{-1}$

where $R(X)$ is some polynomial of degree at most $p+q-\gcd(p,q)-1$. If the first $p+q-\gcd(p,q)$ coefficients of $F$ and $G$ coincide, then the first $p+q-\gcd(p,q)$ coefficients of $F(X) - G(X)$ are zero, whence the polynomial $R$ is the zero polynomial. It follows that $F(X) - G(X)$ is identically zero, so that $F$ and $G$ and hence $(a_n)_{n \geq 0}$ and $(b_n)_{n \geq 0}$ are identical, as claimed.

We should point out that several other results that we have discussed in previous posts appear as problems in the previously mentioned book by Bollobas.

Written by uncudh

February 19, 2009 at 5:56 pm

Posted in math

Tagged with

## Enumerating permutations by number of inversions

We have previously given a proof of the identity

$\prod_{i \geq 1}(1-q^i) = \sum_{n=-\infty}^\infty (-1)^n q^{(3n^2+n)/2}$,

which is Euler’s Pentagonal Number Theorem. We now describe how to apply this formula to derive a formula for the number of permutations of $n$ elements with $k$ inversions. Let $p = p_1p_2 \cdots p_n$ be a permutation of $1,2,\ldots,n$, written in the so-called “one line” notation. An inversion of $p$ is a pair $(p_i,p_j)$ such that $i and $p_i>p_j$. Let $i(p)$ denote the number of inversions of $p$. Then we claim that the generating function $I_n$ of $i(p)$ is

$I_n(q) = \sum_{p \in S_n} q^{i(p)} = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1}) = \prod_{i=1}^n\frac{1-q^i}{1-q}$.

We prove this by induction on $n$. For $n=2$, we have one permutation with no inversions and one with one inversion, whence we obtain the generating function $I_2(q) = 1+q$, as claimed.

Suppose the claim holds for $n-1$ and let $p$ be a permutation of $1,2,\ldots,n-1$. We create a new permutation $q$ by inserting $n$ into $p$. If we insert $n$ after all elements of $p$ we have created no new inversions; if we insert $n$ after all but one element of $p$ we have created one new inversion; and in general, if we insert $n$ after all but $i$ elements of $p$ we create $i$ new inversions. Thus the number of permutations so created is enumerated by the generating function

$I_{n-1}(q)\cdot(1+q+\cdots+q^{n-1}) = (1+q)(1+q+q^2)\cdots(1+q+\cdots+q^{n-1})$,

as claimed. This completes the proof.

Let $b(n,k)$ denote the coefficient of $q^k$ in $I_n(q)$; i.e., $b(n,k)$ is the number of permutations of $n$ elements with $k$ inversions. We wish to deduce a formula for $b(n,k)$. Since $b(n,k)$ is the coefficient of $q^k$ in $\prod_{i=1}^n\frac{1-q^i}{1-q} = (1-q)^{-n}\prod_{i=1}^n (1-q^i)$, it must also equal the coefficient of $q^k$ in the infinite product $(1-q)^{-n}\prod_{i \geq 1}(1-q^i)$. By Euler’s Pentagonal Number Theorem, we have

$(1-q)^{-n}\prod_{i \geq 1}(1-q^i) = (1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}$.

Thus, $b(n,k)$ is the coefficient of $q^k$ in $(1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{(3j^2+j)/2}$. By the binomial theorem, we have

$(1-q)^{-n} = \sum_{h \geq 0} {n+h-1 \choose h}q^h$

(recall that ${-n \choose h} = (-1)^h {n+h-1 \choose h}$). Thus, letting $d_j = (3j^2+j)/2$ denote the pentagonal numbers, we obtain a term $q^k$ in $(1-q)^{-n}\sum_{j=-\infty}^\infty (-1)^j q^{d_j}$ by multiplying a term $q^{k-d_j}$ from $(1-q)^{-n}$ by a term $q^{d_j}$ from $\sum_{j=-\infty}^\infty (-1)^j q^{d_j}$. The coefficient of $q^{k-d_j}$ in $(1-q)^{-n}$ is ${n+k-d_j-1 \choose k-d_j}$, and the coefficient of $q^{d_j}$ in $\sum_{j=-\infty}^\infty (-1)^j q^{d_j}$ is $(-1)^j$. Thus, the coefficient $b(n,k)$ of $q^k$ is given by

$b(n,k) = \sum_j (-1)^j {n+k-d_j-1 \choose k-d_j}$,

where the sum is over all $j$ for which $d_j \leq k$. This is the desired formula for the number of permutations of $n$ elements with $k$ inversions.

Written by uncudh

February 17, 2009 at 2:48 am

Posted in math

Tagged with , ,

## The diverse and abstruse mysteries of numbers

The epigraph to Chapter 1 of Melvyn Nathanson’s Additive Number Theory is from one of Pierre de Fermat’s notorious scribblings in the margins of his copy of Diophantus’ Arithmetica.  In English translation, it reads:

I have discovered a most beautiful theorem of the greatest generality: Every number is a triangular number or the sum of two or three triangular numbers; every number is a square or the sum of two, three, or four squares; every number is a pentagonal number or the sum of two, three, four, or five pentagonal numbers; and so on for hexagonal numbers, heptagonal numbers, and all other polygonal numbers.  The precise statement of this very beautiful and general theorem depends on the number of the angles.  The theorem is based on the most diverse and abstruse mysteries of numbers, but I am not able to include the proof here….

One wonders to what “diverse and abstruse mysteries of numbers” was Fermat referring, but of course Fermat was also notorious for not providing proofs of his claims.  Triangular numbers are numbers of the form $n(n+1)/2$; squares, of the form $n^2$; pentagonal numbers, of the form $n(3n-1)/2$; and $m$-gonal numbers in general, of the form $(m-2)k(k-1)/2 + k$.

The claim regarding squares is the famous Four Squares Theorem of Lagrange; the claim regarding triangular numbers was proved by Gauss; and the claim in general was proved by Cauchy.  The proofs of all of these results can be found in Chapter 1 of Nathanson’s book.

Written by uncudh

February 17, 2009 at 12:12 am

Posted in math

Tagged with

## How Cleopatra spent 10 million sesterces on a single meal

with one comment

The following anecdote is from Pliny’s Natural History:

Cleopatra testing poisons on condemned prisoners (Cabanel, 1897)

Written by uncudh

February 12, 2009 at 6:05 pm

Posted in history

Tagged with ,

## Another intersecting families result

We have previously discussed the following result of Kleitman concerning intersecting families of sets: if ${\cal A,B}$ are monotone decreasing families of subsets of $\{1,\ldots,n\}$, then ${\cal |A||B|} \leq 2^n {\cal |A \cap B|}$. Suppose that instead of the hypothesis that ${\cal A,B}$ are monotone decreasing, we instead have that $|A \cap B|$ is even for every $A\in{\cal A}$, $B\in{\cal B}$. In this case we have the following result of Ahlswede, El Gamal, and Pang (1984).

Theorem. If ${\cal A,B}$ are families of subsets of $\{1,\ldots,n\}$ such that $|A \cap B|$ is even for every $A\in{\cal A}$, $B\in{\cal B}$, then ${\cal |A||B|} \leq 2^n$.

Proof. Let $U$ and $V$ be the vector spaces over GF(2) generated by the sets of characteristic vectors of the sets in ${\cal A}$ and ${\cal B}$ respectively. The assumption that $|A \cap B|$ is even for every $A\in{\cal A}$, $B\in{\cal B}$ means that the inner product $\langle u,v \rangle$ is 0 over GF(2) for every $u \in U$, $v \in V$. In other words $V$ is contained in the orthogonal complement $U^\perp$ of $U$. Since $\dim U + \dim U^\perp = n$, we have $|{\cal A}||{\cal B}| \leq |U||V| \leq 2^{\dim U + \dim U^\perp} = 2^n$, as required.

Written by uncudh

February 12, 2009 at 4:50 am

Posted in math

Tagged with ,