God Plays Dice

You can actually buy a shirt with the Calkin-Wilf tree on it. I probably should buy it, if only so I can wear it when I inevitably give a talk on this subject again, either as a stand-alone talk (I've done it twice) or when I teach it in a class.

This is an infinite binary tree of rational numbers. It has 1/1 at the root, and the children of r/s are r/(r+s) and (r+s)/s. It turns out that this tree contains every positive rational number exactly once, giving an explicit enumeration of the rational numbers.

Also -- and this is what's really surprising to me -- let f(n) be the number of ways to write n as a sum of powers of 2, where no power of 2 can be used more than twice. Then (f(0), f(1), f(2), ...) = (1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,...). The sequence of numbers f(n)/f(n+1) are the rational numbers in that tree, in the order which they appear if you traverse each level from left to right.

I learned about the shirt from this mathoverflow thread, where Richard Stanley gives the theorem of the previous paragraph as an example of a theorem with an "unexpected conclusion".

See the original paper by Calkin and Wilf. I've mentioned it before here and here. I think I first heard of this paper from Brent Yorgey's series of posts expanding upon the paper, or perhaps from Mark Dominus' blog. (Somewhat coincidentally, Yorgey and Dominus both live in Philadelphia. I claim this is coincidence, even though Wilf is at Penn, because I don't think either of them heard about the paper from Wilf.)

And can anything nice be said about the number of ways to write n as a sum of powers of 3, where no power of 3 can be used more than three times?

I'm applying for jobs. Many jobs, because that's how academic job searches work these days. So I have a spreadsheet (in OpenOffice) to keep track of them.

Among the things that I track for each job, there is a column with 0, 1, or 2 in it. 0 means that I haven't submitted anything; 1 means I've submitted something, but not everything that was asked for; 2 means the application is complete. Averaging these numbers and dividing by 2 tells me what proportion of the search is complete.

But I also wanted to know how many 0s, 1s, and 2s there were. And as far as I know the built-in functions in OpenOffice won't do that.

What they will do, however, is this. I have a column consisting of 0s, 1s, 2s, and empty cells. By doing

COUNT(J8:J1000)
SUM(J8:J1000)
SUMPRODUCT(J8:J1000;J8:J1000)

I get the number of cells in that column which are nonempty; their sum; and the sum of their squares. (The SUMPRODUCT function takes 2 arrays of the same shape and returns the sum of the products of corresponding cells.) "8" is the row that contains the first job on the list, and "1000" is just a number that is comfortably more than the number of jobs I am applying for. Call these a, b, and c respectively. Let n₀, n₁, and n₂ be the number of entries which are 0, 1, and 2 respectively. Then I have

a = n₀ + n₁ + n₂
b = n₁ + 2n₂
c = n₁ + 4n₂

which is a three-by-three linear system, and can be solved for n₀, n₁, n₂, giving

n₀ = a - 3b/2 + c/2, n₁ = 2b-c, n₂ = (c-b)/2

and so I can recover the number of applications with status 0, 1, or 2 from this. From the sums of the 0th, 1st, and 2nd powers I can recover the distribution of the values themselves. (The actual code is slightly different, but of course equivalent, because I solved the system "by inspection" and never actually explicitly wrote it out until just now.)

Believe it or not, I actually use this trick in a preprint, "The number of cycles of specified normalized length in permutations", to do some actual mathematics! There I find the expectation of X⁰, X¹, X², ..., X^k where X is a certain random variable known to take on the values 0, 1, ..., k, namely the number of cycles of length in the interval [γ n, δ n] in a permutation of [n] chosen uniformly at random where γ and δ are constants. k is the greatest integer less than or equal to 1/γ ; for example, if we're looking at cycles of length at least 0.15n in permutations of n, there can't be more than six of them. This gives a linear system like the one above which gives the probability that X takes on each value 0, 1, ..., k.

From the xkcd blog: urinal protocol vulnerability.

The basic premise here is the following: there's a long row of urinals (n of them), and a line of men who want to use them. The first man picks a urinal at the end. Each man after that picks one of the urinals which is the furthest from any of the occupied urinals. Nobody ever leaves. How many men have to show up before one of them will be forced into using a urinal adjacent to one that's already occupied? Call this number f(n).

You might think that f(n)/n approaches some limit, but it doesn't; it oscillates between 1/3 and 1/2 based on the fractional part of log₂ n. If n = 2^k + 1 then this "greedy" algorithm for filling the urinals works and every other urinal gets filled: f(2^k + 1) = 2^k-1 + 1. If n = 3 x 2^k-1 + 1 then the worst possible thing happens and only every third urinal gets filled, and f(3 x 2^k-1 + 1) = 2^k-1 + 1. (Yes, that's the same number, and the function's constant in between.) f(5) = f(6) = f(7) = 3, f(9) = ... = f(13) = 5, and so on.) Oscillations like this -- periodic in the logarithm of the problem size -- happen a lot in problems involving binary trees counted by the number of nodes. Still, it was a bit surprising to see this, because I'd never thought about the problem in the case of "unphysically" large n.

Exercise for the reader: invent a mathematically equivalent version of this problem that doesn't involve urinals.

The Calkin-Wilf tree now has a Wikipedia page. This is an infinite binary tree with rational numbers at the nodes, such that it contains each rational number exactly once. In the sequence of rational numbers that one gets from breadth-first traversal of the tree,

1/1, 1/2,2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, ...

the denominator of each number is the numerator of the next; furthermore the sequence of denominators (or of numerators) actually counts something. Plus, there are some interesting pictures that come from plotting these sequences, and some interesting probabilistic properties (see arXiv:0801.0054 for some of the probabilistic stuff, although I actually just found it and haven't read it thoroughly) I've given a talk about this; one day I'll write down some version of it. This is one of my favorite mathematical objects.

It looks like we've got David Eppstein to thank for this. It was introduced in this article by Calkin and Wilf.

So "everybody knows" that the nth Catalan number is given by $C_n = {1 \over n+1} {2n \choose n},ドル and furthermore that they have the asymptotic form
(Okay, I'll confess: I knew the first term, and I got Maple to calculate the others just now.)

So I found myself wondering -- why this n^-3/2? Let D_n = 4^-n C_n. Then and so we get ; furthermore that sum is about -(3/2) log n, for large n, and so D_n is about n_-3/2. The replacement of 1-x with exp(-x) obviously would need to be justified (and such justification would explain the presence of the mysterious π) but I'm still amused that this simple computation got the exponent.

I have two counting sequences that I know to be the same. That is, I have objects of type A and of type B, which each have a size, and I know that the number of A-objects of size n and the number of B-objects of size n are the same. But I am struggling to find a bijection between the things they count.

Are there results of the form "sure, the two counting sequences are the same, but there's no `natural' bijection between the corresponding sets?" (Obviously bijections will always exist between sets of the same size, so this would of course depend on the definition of the word "natural" -- perhaps a meaning analogous to the category-theoretic one is what I'm looking for, perhaps not.) I've never seen any, but most of the people I know are more interested in finding the bijections than in proving there aren't any.

I recently read What Mad Pursuit: A Personal View of Scientific Discovery
, which is Francis Crick's account of the "classical period" of molecular biology, from the discovery of the double helix structure of DNA to the eventual figuring out of the genetic code. It differs from the more well-known book by James Watson, The Double Helix: A Personal Account of the Discovery of the Structure of DNA, which focuses more on the characters involved and less on the science.

Crick was trained as a physicist, and learned some mathematics as well, and every so often this pokes through. For example, back when the nature of the genetic code wasn't known, combinatorial problems arose to prove that a genetic code of a certain type was or was not possible. One idea, due to Gamow and Ycas was that since there are twenty combinations of four bases taken three at a time where order doesn't matter, perhaps each one of those corresponded to a different amino acid. This turned out to be false. Another, more interesting problem comes from asking how the cell knows where to begin reading the code. What is the largest size of a collection of triplets of four bases such that if UVW and XYZ are both in the collection, then neither VWX nor WXY is? The reason for this constraint is so that the "phase" of a genetic sequence is unambiguous; if we see the sequence UVWXYZ, we know to start reading at the U, not the V or the W. Thus the collection can't contain any triplet in which all three elements are the same, and it can contain at most one of {XYZ, YZX, ZXY} for any bases X, Y, Z, not necessarily distinct. There are sixty triplets where not all three elements are the same, thus at most twenty amino acids can be encoded in such a code. There are solutions that acheive twenty; see the paper of Crick, Griffith, and Orgel.

Note that the "20" in the two types of code here arises in different ways. If we assume a triplet code with n bases, then the first type of code can encode as many as n(n+1)(n+2)/6 amino acids, the second (n³-n)/3.

Crick says that the more general problem of enumerating the number of codes which imply their own "reading frame" was considered by Golomb and Welch, and separately Freudenthal. Based on the title and the date, I think the first of these is the paper I point to below -- but our library doesn't have that journal in electronic form, and the physical library is closed this week!

References
F. H. C. Crick, J. S. Griffith, L. E. Orgel. Codes Without Commas. Proceedings of the National Academy of Sciences of the United States of America, Vol. 43, No. 5 (May 15, 1957), pp. 416-421.

George Gamow, Martynas Ycas. Statistical Correlation of Protein and Ribonucleic Acid Composition Statistical Correlation of Protein and Ribonucleic Acid Composition. Vol. 41, No. 12 (Dec. 15, 1955), pp. 1011-1019.

Golomb, S.W., Gordon, B., and Welch, L.R., "Comma-Free Codes", The Canadian Journal of Mathematics, Vol. 10, 1958. (Citation from this list of Golomb's publications; I haven't read it.)

Ken Jennings, the 74-time Jeopardy! champion, has a blog.

Today he wrote about polyominoes, inspired by the question of how many pieces there would be in Tetris if it were played with pieces made of five or six squares instead of the canonical four. He's not a mathematician, and he finds it surprising that there's no nice formula for the number of polyominoes with n cells. I suppose it is kind of surprising to someone with no mathematical training; by this point in my life I've gotten used to the fact that things just don't work that way.

Weak security in our daily lives (in English): basically, you can use a de Bruijn sequence to break into a car with keyless entry in what might be a non-ridiculous amount of time. I'm referring to the sort which have five buttons marked 1/2, 3/4, 5/6, 7/8, and 9/0, and a five-digit PIN that has to be entered. This trick takes advantage of the fact that the circuitry only remembers the last five buttons pressed, so if you press, say, 157393, then the car will open if the correct code is either 15739 or 57393. It is in fact possible to arrange things so that each key you press, starting with the fifth, completes a five-digit sequence that hasn't been seen before.

Of course, you shouldn't do this.

Via microsiervos (in Spanish).

Charlie Siegel, whose office is just down the hall from mine, had for a while the following statement on the blackboard in his office (paraphrased and renotated a bit): Let g(n) be the number of lines on the generic hypersurface of degree 2n-1 in complex projective (n+1)-space. Then where the notation $[z^n] f(z)$ means "the coefficient of zⁿ in f(z)". For example, g(2) is the coefficient of z² in (1-z)(3)(2+z)(1+2z)(3z), which turns out to be 27; this means that the number of lines on the generic hypersurface of degree 3 in complex projective 3-space is 27. Informally, "there are 27 lines on the cubic". Want to know why? For the cubic case, see this post by Charlie or go to his talk last week.

The first few values of g(n) are 1, 27, 2875, 698005, 305093061, 210480374951, 210776836330775, 289139638632755625... -- so this sequence grows pretty quickly. How quickly? I couldn't tell at first, but it kept nagging at me every time I was in Charlie's office. The sequence is A027363 in the Encyclopedia of Integer Sequences. It turns out that it's in an appendix of the paper that the Encyclopedia links to (arXiv:math/0610286, specifically its appendix by Zagier) but the derivation there is long and involved and it was more fun with the formula myself. There are a few gaps, but here it is.

We can deal easily with the 1-z factor out front, and we want where
We can already see it's going to be kind of tricky; the coefficients of f_n(z) are probably going to be pretty big and not that far apart.

Now, we can pull out a 2n-1 from each factor in the expression for f_n(z), and we get

Call the product p_n(z). Now this is where, out of nowhere, I start having Fun With Probability. (It's kind of amusing because there is nothing probabilistic about the original question.) The term corresponding to j in that product is the probability generating function of a random variable which is 1 with probability (j/(2n-1)) and 0 otherwise. The product is thus the p.g.f. of the sum of such random variables for j = 0, 1, ..., 2n-1.

Now, this sum has mean which is the sum of the means of those random variables, that is,
and variance which is the sum of their variances, which is approximately n²/3. Furthermore, since the sum is a sum of a bunch of small contributions, it's approximately normal. So p_n(z) is the probability generating function of a random variable which is roughly normal with mean n and variance n²/3, but integer-valued, and its kth coefficient is the probability that such a random variable is equal to k.

Therefore [z^k] p_n(z) is approximately
which is the density of such a normal random variable. We want to know [zⁿ] p_n(z) - [zⁿ] p_n-1}(z), and this is approximately q_n(n) - q_n(n-1). You'd think this would be q_n'(n), but q_n(n) is actually zero -- the fact that the coefficients were "close to each other" is even more troublesome than you'd expect. Still, we can make a Taylor series for q_n at n, and the linear term is zero, so we get And g(n) = [zⁿ] f_n(z) - [zⁿ] f_n-1(z) = (2n-1)²ⁿ ([zⁿ] p_n(z) - [zⁿ] p_n-1(z)); using the approximation we get
and now note that
Therefore which matches (with a bit of computation) the result given by Zagier in the arXiv, and the terms reported in the OEIS. I wouldn't have trusted it otherwise; that "take the second derivative" step is particularly sketchy, although it can probably be justified as there are results on the rate of convergence of the central limit theorem. But asymptotic analysis is nice in this way; if it's easy to compute the terms of some sequence, then we can often be confident in results like this even without

Besides, I'd never seen the trick of using the second derivative to approximate a difference before. At least not that I can remember.

From the wrapping a univeral remote I recently bought: "Controls VCR/DVD combos, TV/VCR combos, and TV/DVD combos!"

This is because it controls two devices, and those are the three types of device that people have. But I guess "controls two devices" doesn't work from a marketing standpoint, so they have to list all 3-choose-2 subsets. (And I also find elsewhere on the packaging "manage up to 8 separate devices with one remote control". Something doesn't add up here.)

I'm currently attempting to organize a paper out of a bunch of notes I've built up recently; a possibly useful suggestion I received is to write each theorem, definition, etc. on an index card, so that I can physically move them around to figure out how the paper should be organized.

Of course, definitions have to come before the theorems that use them, some theorems use other theorems in their proofs, and so on -- so to the extent that I'm remembering to do so, I'm indicating these sorts of dependencies on the index cards as well.

It occurs to me that what I am doing here is trying to extend a partial order (the ordering that comes from the dependency) to a total order. There are of course constraints on this order; certain results, although not logically related, are related in some philosophical sense and should perhaps be kept near each other. It's actually an interesting optimization problem.

Now if only I were writing a paper about extending partial orders to total orders...

(But my paper does talk quite a bit about permutations. And a total order will end up being a permutation of my index cards.)

On Friday I wrote about the mutilated chessboard problem.

I'll give the solution now. The reason this problem is usually phrased in terms of a "chessboard" is that a chessboard has its squares alternately colored white and black. (I'm going to call the colors white and black even if that's not actually what they are.) A chessboard has the same number of squares of each color, and any domino covers one white square and one black square. So if we remove two squares of the same color, such as the opposite corners, then tiling is impossible.

It turns out that if you remove any two squares of different color, leaving 31 squares of each color, the board can be tiled with dominoes. Drini gave the solution; draw any tour that goes through all the squares exactly once and finishes where it began. Removing two squares of opposite colors breaks this into two subpaths of even length, which are easily tiled.

As for the other problem I asked, when can you remove four squared and have there be a tiling: clearly we need to begin by removing two squares of each color. There is another necessary condition for there to be a tiling -- the squares removed can't block off a single corner square from the rest of the board. (You might worry that they could disconnect the board in some other way, but the only other way possible under the tiling constraints is that they disconnect a domino-shaped region.) But then the tour argument above doesn't work; in particular, a tour is broken up into four subpaths of even lengths if and only if the removed squares occur on it in the order black-white-black-white. Furthermore, it appears that there are ways to remove four squares from the four-by-four board such that the remaining twelve are tileable, but there is no tour that they break up into even-length subpaths. There aren't that many tours of the four-by-four board, so it's easy to check this by brute force with a simple program; in fact there are six according to Sloane's encyclopedia. (It says twelve there, but Sloane refers to directed tours.)

However, that cuts down the number of cases one has to deal with, and in the end it looks like a four-by-four chessboard, with four squares removed, is tileable if and only if the removed squares are of opposite color and do not include both of the squares adjacent to any corner.

My method (which I realize I haven't fully explained here; if anybody wants to seriously tackle this problem for some reason I'll be happy to explain in more detail) requires a bunch of nasty case analysis, though. And in the case of the 8-by-8 board there are millions of tours, so it doesn't generalize well.

A problem that recently was posted on Nate Silver's FiveThirtyEight was this one, which I've mentioned before:

How many unique ways are there to acquire at least 270 electoral votes without any excess?

Somewhat more rigorously, Michael Walsh (who might be someone I know from MIT; I'm not sure, though, because it's a fairly common name) defined a minimal winning set as a subset S of all the states such that the sum of the number of electoral votes of those states is at least 270, but that sum minus the minimum number of electoral votes of any state in the set is less than 270.

I'm going to give my solution, and also attempt to summarize the other solutions that have been given, to the extent that I can. (I am not fluent in the programming languages in which some of the solutions are written, so I can't guarantee perfection.)

The number, as I stated in my solution there, is 51,199,463,116,367. (I'm including this number in the post -- and as the title of the post -- because if you have reasonable Google skills and are looking for more information on this, you'll probably Google that number.) I gave a quick sketch of the solution there, but I want to explain it more fully.

As is usual in combinatorics, it's best to count the minimal winning sets by some parameter, and then sum over that parameter. In this case the natural parameter is the minimum number of electoral votes of an element of S. So I'll begin by counting the number of ways we can pick a set of states S, where:

• the smallest state in the set has three electoral votes;


• together all the states have 270 or more electoral votes;


• upon removing the smaller state, we're left with 269 or less electoral votes.

Thus our set must contain at least one state with three electoral votes, and a total of 270, 271, or 272 electoral votes. We can start by counting all the sets which have 270, 271, or 272 electoral votes, and then remove those which contain no 3-EV states.

So, how to count those sets? Generating functions. I'll illustrate with a smaller example. Say we live in a nation with three states, which have 3, 4, and 5 electoral votes respectively. I will call these states Wyoming, Idaho, and Utah. Now, consider the polynomial

(1 + x³)(1 + x⁴)(1 + x⁵).

Here we have a factor (1 + x^k) corresponding to a state with k electoral votes. When we expand this polynomial, the result is

1 + x³ + x⁴ + x⁵ + x⁷ + x⁸ + x⁹ + x¹².

Each term here corresponds to one of the subsets of the set {Wyoming, Idaho, Utah}; for example the x⁸ term corresponds to the set {Wyoming, Utah}. We can read off from the coefficients of the polynomial that there is one way each to receive 0, 3, 4, 5, 7, 8, 9, or 12 electoral votes in this nation; no other numbers are possible.

Of course, in reality there are many ways to get each number of electoral votes, because there are 2⁵¹ possible sets S and only 435 electoral votes. To give a simple example of this repetition, in the above example replace Utah (5 EV) with Oregon (7 EV), and then we get

(1 + x³)(1 + x⁴)(1 + x⁷)

which expands to

1 + x³ + x⁴ + 2x⁷ + x¹⁰ + x¹¹ + x¹⁴.

In this hypothetical mini-nation there are 2 ways to get seven electoral votes -- Wyoming and Idaho together, or Oregon by itself. That explains the 2 in front of x⁷.

So now how many ways are there to get 270, 271, or 272 electoral votes in the actual nation? We consider the much larger polynomial

f₃(x) = (1 + x⁵⁵) (1 + x³⁴) (1 + x³¹) ... (1 + x⁴)⁵ (1 + x³)⁸)

which has a factor of 1 + x⁵⁵ for California (55 EV), 1 + x³⁴ for Texas (34 EV), and so on down to the five states with 4 EV and the eight states with 3 EV. Expanding this out gives

f₃(x) = x⁵³⁸ + 8x⁵³⁵ + 5x⁵³⁴ + ... + 17032469851307x²⁷²+17046339123934x²⁷¹+17054665123395x²⁷⁰ + ... + 8x³ + 1

and we see that in our actual nation, there is one way to get 538 EV (winning all the states), eight ways to get 535 (winning all the states but one of the 3-EV states), and so on. The coefficients of x²⁷², x²⁷¹, x²⁷⁰ in the middle are the number of ways to win 270, 271, or 272 EV.

So we just add those up, right? Not so fast. Remember that we wanted the number of ways to get 270, 271, or 272 EV including at least one 3-EV state. So we construct a similar polynomial which excludes the 3-EV states, namely

f₄(x) = (1 + x⁵⁵) (1 + x³⁴) (1 + x³¹) ... (1 + x⁴)⁵

and the coefficient of xⁿ here is the number of ways to get n electoral votes using only states with 4 EV or more. Expanding, the terms we care about are

f₄(x) = ... + 64405297719 x²⁷² + 64713359463 x²⁷¹ + 65001219892 x²⁷⁰ + ...

The number of ways to get 270, 271, or 272 EV is thus 17032469851307 +たす 17046339123934 +たす 17054665123395 =わ 51133474098636. The number of ways to do that without using any 3-EV states is 64405297719 +たす 64713359463 +たす 65001219892 =わ 194119877074. The difference, 50939354221562, is the number of ways to get 270, 271, or 272 EV using at least one 3-EV state, and therefore the number of minimal winning sets which contain at least one 3-EV state.

Now we can proceed in the same way to get the number of minimal winning sets with smallest state having 4, 5, ..., 15 EV. There are 250611676072 with smallest state having 4 EV, for example, all the way down to 1 with the smallest state having 15 EV. (The states having at least 15 EV together have 271 EV, so you have to include all of them.)

Adding the numbers you get in this way gives the answer 51,199,463,116,367. The proportion of minimal winning sets which don't use at least one 3-EV state is one in 197; it's not surprising that this is quite low, because there are eight 3-EV states and so it's hard to avoid all of them!

A lot of the commenters at FiveThirtyEight used the technique of "dynamic programming" to get the same answer. This basically amounts to multiplying out the polynomials term by term and keeping track of just the coefficients, not writing down all the x's and the exponents. (Of course, the people that went that route would probably say that my approach via generating functions is just dynamic programming with a bunch of extra symbols floating around for no good reason.)

A couple of particularly good estimates also occurred. One person (Brian, 4:43 pm) simulated a million random outcomes, found that 22,790 of them gave minimal winning sets, and therefore gave a 95% confidence interval of (0.02249, 0.02309) for the probability that a set chosen uniformly at random is a minimal winning set; there are 2⁵¹ minimal winning sets, so a 95% confidence interval for their number was (50.6 trillion - 52.0 trillion). The actual answer is about 51.2 trillion, and falls in that interval.

Someone signing himself as "ray" had a clever solution as well. If we assume that the states each vote independently and each have probability 1/2 of voting for our candidate, then the number of electoral votes our candidate gets is itself a random variable. Since it's a sum of a bunch of smaller independent random variables, we can assume it's close to being normal; this is a heuristic application of the Central Limit Theorem. The mean is clearly 269 (half the total number of electoral votes). The variance of the number of electoral votes received from a state with k electoral votes is k²/4, and variances add, so the variance is one-fourth of the sum of the squares of the numbers of electoral votes. This is 2466.5; the standard deviation is the square root of this, 49.66. The probability that a normally distributed random variable with mean 269 and standard deviation 49.66 falls between 269.5 and 272.5 (that is, that its value rounded to the nearest integer is 270, 271, or 272) is 0.0241. This is the approximate probability of getting 270, 271, or 272 EV; that's pretty close to the event we want. We can approximate the answer as 2⁵¹ times this, or 5.42 · 10¹³, which is high by a few percent -- but not bad for a solution that totally ignores the combinatorics!

A "homework assignment" from FiveThirtyEight.com: Electoral Projections Done Right: in a US presidential election, "[h]ow many unique ways are there to acquire at least 270 electoral votes without any excess?" That is, how many sets of states with at least 270 electoral votes, such that when any state is removed less than 270 electoral votes remain?

For the most part the comments so far are:

• people misunderstanding the problem (which is not surprising; it's the sort of problem mathematicians are better at understanding than the general population, and the audience there is not necessarily mathematicians);
• programmer types whining "waah, this problem is in NP, I can't do it!". Is it in NP? I don't feel like thinking about that -- but I did it in a few minutes, and more importantly with a couple seconds of computation time. NP doesn't stand for "not possible";
• people saying "who cares, most of those combinations are politically unrealistic!" (which I have to admit is true);
• a few estimates of the answer based on some quick and dirty statistical assumptions, which look basically right;
• and a couple people (me included) who have gotten a numerical answer.

I'd explain my solution here, but I think some of you might want to try out this problem. If you poke around in the comments at FiveThirtyEight.com you can find my solution.

What's interesting to see is that a lot of people seem to believe you have to actually generate the sets in order to count them. That would of course be hopeless. The explanation of combinatorics as "counting without counting" comes to mind.

Optimizing your wife. From MathPages, via reddit. (This is apparently also known as the secretary problem or the sultan's dowry problem.)

The following is a semi-standard bit of mathematical folklore. Say you expect to meet N possible suitors in your life. You want to maximize your chances of picking the best one, given that you expect to meet these people in a random order, and once you say no to one of them you can never see them again, and that you can say for any two of them either "X is better than Y" or "Y is better than X". (There are no ties, and everybody's comparable.)

My readers who are not mathematicians are probably thinking that these are ridiculous assumptions. This is true. In particular, the first one seems silly to me -- we don't meet people at random, but through other people we know, so I suspect that the longer one spends living the more one tends to find people one likes. This certainly is true in my experience when seeking out friends -- people who I like spending time with tend to know other people I'd like spending time with. The inability to go back to previous suitors seems to be not a horrible approximation. The fact that everyone is rankable seems at first like a bad assumption -- but we manage to do it for economic goods all the time. For example, houses have prices which are scalars, despite the fact that there are multiple dimensions along which houses can be compared. The fourth assumption, that you know how many potential suitors there are, seems the most wrong to me. But combined with the assumption that you meet suitors at a constant rate, this converts strategies which talk about numbers of suitors to strategies which talk about time.

My readers who are mathematicians probably didn't read the previous paragraph.

Anyway, the optimal strategy is to reject the first N/e of the people you meet, and then pick the first person you meet who's better than everyone you'd met previously. The probability of this strategy succeeding -- in that you pick the very best person -- is close to 1/e when N is large.

I'm pretty sure I first heard this around fifteen years ago, and have probably heard it at least once a year since then -- but I didn't know a proof until now. (Strictly speaking, there's some hand-waving in the argument given there, as there always is whenever someone says "X is approximately equal to Y" without giving any sort of bound on X-Y or X/Y -- but I don't plan to use this to prove anything else, so I'm convinced.)

The number of permutations of [n] of odd order (or equivalently, the number with all cycle lengths odd) is given by (n-1)²(n-3)²...1² if n is even, and n(n-2)²(n-4)²...1² if n is odd. The sequence begins 1, 1, 1, 3, 9, 45, 225, 1575, ..., which is A000246 in Sloane's encyclopedia.

How fast does this grow? Well, it's not hard to show (from Stirling's formula) that if a(n) is the number of permutations of [n], then a(n)/n! is asymptotic to (2/πn)^1/2. Since there are n! permutations of [n], that's the asymptotic probability that a randomly chosen permutation is of odd order. Alternatively, a(n) is asymptotic to 2(n/e)ⁿ. So log a(n) ~ log 2 + n(log n - 1).

And you can quickly "graph" log a(n) by just looking at the table of the first 100 values. The length of a(n), when written in base 10, is proportional to log n (precisely, it's log n / log 10). So the length of a(n) when written in decimal should grow a bit faster than linearly.

Indeed, if you zoom out from that table, that's exactly what you see -- the table's not quite a triangle, but it's close. Of course this trick isn't really so useful -- how often is one going to have a sequence that we can compute exactly but don't have any idea how large the logarithm is? -- but I think it's kind of cute.

Who proved the rationals are countable? (No fair looking this up.) If you're not sure, guess.

I'm wondering if people know the answer to this one; via some informal surveying it seems less well known that I'd expect. Then again, I didn't know it.

On a related note, the usual proof that N × N is countable (where N = {1, 2, 3, 4, ...} is the natural numbers) goes by giving an explicit enumeration of the pairs of natural numbers, namely,

(1,1), (2,1), (1,2), (3,1), (2,2), (1,3), (4,1), (3,2), (2,3), (1,4), ...

where we list all pairs of integers summing to 2, then to 3, then to 4, then to 5, ... Thus we list pairs of integers in order of their "size". Alternatively, we're enumerating pairs of sets in order of their "size", where sets are only distinguished up to cardinality.

Combinatorialists are often concerned with classes of objects where there are a finite number of objects of size n for any integer n... of course this means that any such class is in fact countable. I don't think I'd heard this stated explicitly, probably because it's not particularly important for doing combinatorics.

For the answer to the question: see the comments.

Here's a little thing I thought of a few days ago. Consider the following identities for the sums of powers:

(okay, that's kind of stupid, but you have to start somewhere...),


(the right-hand side might be more familiar as n(n+1)(2n+1)/6), and

(the right-hand side here is,coincidentally the square of (1+2+...+k). For each choice of exponent we get a different polynomial in the numerator. They all factor into linear terms... that doesn't keep up, though. For example,

Still, one wonders -- what are the roots of these polynomials? (The first thought is that they're always in the interval [-1, 0], but that's pretty quickly disproven by considering the sum of 5th powers.)

Some computation shows that the patterns of zeroes in the complex plane are both symmetric around the real axis (no surprise there; zeroes come in complex conjugate pairs!) and around the line y = -1/2 (a bit more surprising). So you think to plot them, and you get something that looks like this plot for the polynomial you obtain when you sum 300th powers. (I didn't make that plot; it's from Richard Stanley's web page on interesting zeros of polynomials.)

It turns out that they're the Bernoulli polynomials; for very large n Veselov and Ward showed that the real zeroes are very near 0, ± 1/2, ± 1, ... if n is odd, and ± 1/4, ± 3/4, ± 5/4, ... if n is even; furthermore, in the limit, the nth Bernoulli polynomial has 2/(πe)n real zeros. (2/πe is about .235; thus in the 300th Bernoulli polynomial we expect about 70 real zeros, taking up an interval of length 35 or so centered at -1/2 on the real line; that's what you see in that plot.)

Goh and Boyer (who I've mentioned before for similar work on partition polynomials) have found the "zero attractor" of the Euler polynomials, and state in their paper that the methods there also give a similar result for the Bernoulli polynomials -- basically, what this means is that if we shrink down the plot of the zeros of the nth Bernoulli polynomial by a factor of n, then the zeroes fall very close to some limiting curves and are arranged with a certain density along those curves. (Along the portion of the real axis in question, the density is constant; along the other branches it doesn't seem to be.)

References:
William M. Y. Goh, Robert Boyer. On the Zero Attractor of the Euler Polynomials. arXiv: math.CO/0409062. (2004)
Alexander Veselov and Joseph Ward, On the real zeroes of the Hurwitz zeta-function and Bernoulli polynomials, arXiv: math.GM/0205183. (2002)

Consider a combinatorial class (in the sense of Flajolet and Sedgewick) or combinatorial species (in the sense of Bergeron, Labelle, and Leroux). There are certain generating functions associated with combinatorial classes/species (I'm conflating the two for the moment because the difference between the two theories aren't important here), and the operations of sum and product have nice "combinatorial" interpretations -- addition of generating functions corresponds to disjoint unions of classes/species and multiplication of generating functions what I'll call here "combinatorial product", i. e. for two species F and G, an FG-structure on the set [n] is a pair which consists of an F-structure on some subset S of [n] and a G-structure on [n]-S. Then the generating function of the FG-structures is the product of the generating function of the F-structures and that of the G-structures.

Other natural operations on functions have combinatorial interpretations: composition of functions, taking exponentials or logarithms, differentiation, integration, etc. Even subtraction has an interpretation, although one has to be careful: this is the "virtual species". (A virtual species is a pair of ordinary species (F, G), written as F-G, where (F, G) = (H, K) if F + K = G + H. Replacing species with integers and addition with multiplication, this looks like the construction of the rational numbers from the integers.)

But is there a natural quotient operation? If there is, I can't find a mention of it in Flajolet and Sedgewick, and Marko Petkovsek (who I was just talking about this with) tells me it's not in Bergeron et al. either; this is one of the sources he's using for our current topics course in combinatorics. Let F be a species with 1 structure on the set of size 0, and let F_n be its restriction to size n. Let F₊ be its restriction to all positive sizes. Then

where 1 is the multiplicative identity species (hence the name); it has one structure on a set of size 0. We can of course write this as

and we collect the "positive" and "negative" terms to get

So the inverse of the species F exists, and it's a virtual species in which the positive part is even-length tuples of nonempty F-structures, and the negative part is odd-length tuples of nonempty F-structures. This doesn't quite seem like a "combinatorially natural" operation -- but on the other hand I was able to describe it in a single sentence, so it seems plausible that it could be a natural thing to occur somewhere.

Notice that this also proves that if

and F(z)G(z) = 1, f₀ = 1, then all the g_n are integers, since the generating function G(z) actually counts something! (Well, a virtual something -- but that's close enough. It won't surprise you to learn that for two species H and K, the generating function corresponding to the virtual species H-K is H(z) - K(z). G here is a virtual species, so the g_n are (possibly negative) integers. Of course, there are other ways to prove this, but I think this is a cute "combinatorial proof".