Uniformly at Random

Archive for February 2009

The number of ways of shuffling a cabinet

leave a comment »

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

leave a comment »

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

with 2 comments

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<j 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

leave a comment »

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:

There were formerly two pearls, the largest that had been ever seen in the whole world: Cleopatra, the last of the queens of Egypt, was in possession of them both, they having come to her by descent from the kings of the East. When Antony had been sated by her, day after day, with the most exquisite banquets, this queenly courtesan, inflated with vanity and disdainful arrogance, affected to treat all this sumptuousness and all these vast preparations with the greatest contempt; upon which Antony enquired what there was that could possibly be added to such extraordinary magnificence. To this she made answer, that on a single entertainment she would expend ten millions of sesterces. Antony was extremely desirous to learn how that could be done, but looked upon it as a thing quite impossible; and a wager was the result. On the following day, upon which the matter was to be decided, in order that she might not lose the wager, she had an entertainment set before Antony, magnificent in every respect, though no better than his usual repast. Upon this, Antony joked her, and enquired what was the amount expended upon it; to which she made answer that the banquet which he then beheld was only a trifling appendage to the real banquet, and that she alone would consume at the meal to the ascertained value of that amount, she herself would swallow the ten millions of sesterces; and so ordered the second course to be served. In obedience to her instructions, the servants placed before her a single vessel, which was filled with vinegar, a liquid, the sharpness and strength of which is able to dissolve pearls. At this moment she was wearing in her ears those choicest and most rare and unique productions of Nature; and while Antony was waiting to see what she was going to do, taking one of them from out of her ear, she threw it into the vinegar, and directly it was melted, swallowed it. Lucius Plancus, who had been named umpire in the wager, placed his hand upon the other at the very instant that she was making preparations to dissolve it in a similar manner, and declared that Antony had lost—an omen which, in the result, was fully confirmed. The fame of the second pearl is equal to that which attends its fellow. After the queen, who had thus come off victorious on so important a question, had been seized, it was cut asunder, in order that this, the other half of the entertainment, might serve as pendants for the ears of Venus, in the Pantheon at Rome.

Cleopatra testing poisons on condemned prisoners (Cabanel, 1897)

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

leave a comment »

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 ,