## Archive for **February 2009**

## 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 denote the number of ministers in Macdonald’s cabinet, the answer to this question is , the number of derangements of an -element set. A *derangement* is a permutation such that no element is mapped to itself. The number of derangements of an -element set is well-known to be , which turns out to be simply the nearest integer to .

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.

## Macdonald’s double shuffle

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.

## The Fine-Wilf Theorem

The Fine-Wilf Theorem is as follows. Supppose and are two infinite periodic sequences with periods and respectively. If and agree on their first 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 and . By the periodicity hypothesis, we have and for some polynomials of maximum degrees and respectively. However, since divides each of and , we also have

where is some polynomial of degree at most . If the first coefficients of and coincide, then the first coefficients of are zero, whence the polynomial is the zero polynomial. It follows that is identically zero, so that and and hence and 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.

- Cauchy-Davenport is Problem 96.
- Erdos-Ginzburg-Ziv is Problem 97.
- Bollobas’ Cross-Intersecting Pairs Theorem is a weaker version of a result of Frankl given as Problem 113.
- Problem 115 is a consequence of the two families result discussed here.

## Enumerating permutations by number of inversions

We have previously given a proof of the identity

,

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 elements with inversions. Let be a permutation of , written in the so-called “one line” notation. An inversion of is a pair such that and . Let denote the number of inversions of . Then we claim that the generating function of is

.

We prove this by induction on . For , we have one permutation with no inversions and one with one inversion, whence we obtain the generating function , as claimed.

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

,

as claimed. This completes the proof.

Let denote the coefficient of in ; i.e., is the number of permutations of elements with inversions. We wish to deduce a formula for . Since is the coefficient of in , it must also equal the coefficient of in the infinite product . By Euler’s Pentagonal Number Theorem, we have

.

Thus, is the coefficient of in . By the binomial theorem, we have

(recall that ). Thus, letting denote the pentagonal numbers, we obtain a term in by multiplying a term from by a term from . The coefficient of in is , and the coefficient of in is . Thus, the coefficient of is given by

,

where the sum is over all for which . This is the desired formula for the number of permutations of elements with inversions.

## 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 ; squares, of the form ; pentagonal numbers, of the form ; and -gonal numbers in general, of the form .

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.

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

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.

## Another intersecting families result

We have previously discussed the following result of Kleitman concerning intersecting families of sets: if are monotone decreasing families of subsets of , then . Suppose that instead of the hypothesis that are monotone decreasing, we instead have that is even for every , . In this case we have the following result of Ahlswede, El Gamal, and Pang (1984).

**Theorem**. If are families of subsets of such that is even for every , , then .

*Proof*. Let and be the vector spaces over GF(2) generated by the sets of characteristic vectors of the sets in and respectively. The assumption that is even for every , means that the inner product is 0 over GF(2) for every , . In other words is contained in the orthogonal complement of . Since , we have , as required.