Best bad math joke ever

One of my favorite bad math jokes ever is now in Wikipedia, and no, I didn't add it.

Namely, exercise 6.24 of Richard Stanley's Enumerative Combinatorics, Volume 2 asks the reader to

"Explain the significance of the following sequence: un, dos, tres, quatre, cinc, sis, set, vuit, nou, deu..."

The answer is that these are the "Catalan numbers", i. e. the numbers in the Catalan language. If this seems random, note that exercise 6.21 is the famous exercise in 66 parts (169 in the extended online version, labelled (a) through (m⁷)), which asks the reader to prove that 66 (or 169) different sets are counted by the Catalan numbers.

I'm telling you about this joke because the Wikipedia article on Catalan numbers begins with a link to the list of numbers in various languages.

An alternative version of this joke (American Mathematical Monthly, vol. 103 (1996), pages 538 and 577) asks you to identify the sequence "una, dues, cinc, catorze, quaranta-dues, cent trenta-dues, quatre-cent vint-i-nou,...", which are the Catalan numbers 1, 2, 5, 14, 42, 132, 429... in the Catalan language. (I'm reporting the spellings as I found them in my sources; the first series is in the masculine and the second is in the feminine, as Juan Miguel pointed out in the comments.)

Richard Stanley tells a joke

In the graduate course Richard Stanley is currently teaching, on symmetric functions (also known as "the chapter of Stanley that I haven't really read that carefully", which is indeed the text he's using), students have two options for an end-of-term paper. They can either hand in "a treatise of at least 200 pages on some area of symmetric functions, consisting primarily of original work" which "must contain (correct) proofs of at least two important, longstanding open problems" or an eight-page expository paper.

Somehow I think nobody will choose the first option. (Although if they do, that would be an instant PhD thesis.)

Possibly also of interest: Stanley is working on a second edition of Enumerative Combinatorics, Volume 1, and a draft version of Chapter 1 is available (198-page PDF) This appears to be a substantial extension of Chapter 1 of the original.

Zeros of some polynomials arising from sums

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)

Pattern avoidance

Here's a paper I found while Googling for something else a while ago: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, by Richard Arratia, from the Electronic Journal of Combinatorics, Volume 6(1) (1999), note N1.

Pattern avoidance in permutations is a beautiful little subject, about which I don't know that much -- but not that much is known. For example, see Bridget Tenner's remarkably short database of permutation pattern avoidance; okay, so the state of knowledge isn't quite as bad as this makes it look, but it's not that good either. (A good introduction to the area seems to be Miklos Bona's Combinatorics of Permutations, which has a couple chapters on the area. However, if you're at Penn I don't recommend Bona's book, because I have the library copy and I don't want to give it up.

Let p₁ p₂ ... p_n be a permutation of the integers from 1 to n. We say a permutation is, for example, 231-avoiding if there is no i < j < k such that p_k < p_i < p_j. That is, a 231-pattern in a permutation is a set of three letters in the word representing it which, when read from left to right, fall in the same order as the numbers 2, 3, 1; a permutation is 231-avoiding if it has no 231-patterns. So, for example, 26415837 is not a 231-avoiding permutation of [8], because 2, 6, 1 form a 231-pattern. A similar definition can be made of a σ-avoiding permutation for any permutation (called a "pattern") σ. Rather surprisingly, the number of patterns avoiding any permutation of length 3 is the same, and this can be proven bijectively. But some permutations of length 4, for example, are "easier" to avoid than others; what makes a pattern easy or difficult to avoid isn't totally clear. The Stanley-Wilf conjecture (now proven, by Gabor Tardos and Adam Marcus) states that if we let F(n, σ) be the number of permutations of [n] which avoid the pattern σ, then

exists and is finite. For example, 231-avoiding permutations are in bijection with Catalan trees of size n, so F(n, 231) is the nth Catalan number. Thus

and so we get the constant 4 for the limit above. The Stanley-Wilf conjecture thus associates a constant with each permutation, but not too many of these constants are known. (I won't attempt to tabulate the known constants; I suspect someone out there has already done it. At the very least, there are a fair number of results scattered throughout the applicable chapters of Bona's textbook.)

Anyway, a natural question to ask is "how many σ-patterns does a permutation of [n] have, on average?" This is fairly obviously

since there are possible sites for such patterns, and each site actually contains such a pattern with probability 1/k!; from playing around with a few small cases it looks like the variance of the number of σ-patterns is asymptotically c_σn^2k-1, where the constants c_σ don't appear to be anything nice in general. (The only way I know how to compute these variances basically comes down to considering all the ways in which two instances of the same pattern in the same permutation can intersect and enumerating a large number of cases; it's not surprising the results are ugly. I've only done it in a couple simple cases, and I don't want to quote the results here because I haven't had the patience to check my computations.) In the case of inversions, which are just 21-patterns, these are the classical results that the average number of inversions of an n-permutation is asymptotically n²/4, with variance n³/36. I have a faint hope that there might be some relation between the constant "1/36" there and the fact that the number of 21-avoiding permutations of n is just 1ⁿ (that is, 1 -- this is the simplest case of the Stanley-Wilf conjecture, that there is only one inversion-free permutation) but I don't actually know enough of these constants to see what's going on.

Anyway, what I want to bring attention to is the conjecture of Alon at the end of this note:
Conjecture (Alon): The threshold length t(k), for a random permutation to contain all k-permutations with substantial probability, has t(k) ~ k^2/4.
Why should this be true? The note by Arratia gives some idea -- it relates this problem to the longest common subsequence problem -- but I want an argument that stays purely within the pattern avoidance realm. I'm working on it.

Asymptotics of partition polynomials

I've previously mentioned Richard Stanley's page of interesting zeros of polynomials. For an example of this in action, you can see a couple papers which were justed posted to the arXiv, by Robert P. Boyer and William M. Y. Goh:

Partition Polynomials: Asymptotics and Zeros

Polynomials associated with Partitions: Their Asymptotics and Zeros

In the first paper, we take the polynomial which counts the partitions of n by number of parts; when n = 200 the zeroes of this polynomial are plotted at Richard Stanley's web site. What's surprising is that the zeroes are actually a good bit more subtle than they'd look from that picture; they come in three families, the third of which doesn't appear until n = 13,000.

The second paper makes a similar conjecture for the zeroes of the "rank polynomial" and "crank polynomial" of high degree, where partitions are counted by their rank (the difference between the largest part and the number of parts) or the crank (see p. 11 for definition). (In the rank case, at least, Boyer and Goh actually just count partitions with positive rank; by conjugation one can get those with negative rank.) The zeroes of the rank polynomial appear to lie approximately on the unit circle, and are spread out uniformly.

By the way, I've previously credited this idea of looking at the zeros of combinatorially defined polynomials to Stanley. Apparently it's actually due to Rota, who once said:

The one contribution of mine that I hope will be remembered has consisted in just pointing out that all sorts of problems of combinatorics can be viewed as problems of location of the zeros of certain polynomials and in giving these zeros a combinatorial interpretation. This is now called the critical problem. Over the years people have added examples of critical problems, though we still haven't gotten any idea of how to solve it in general. I'd like to see someone get such an idea before I die. The four-color conjecture-that with only four colors you can color every planar map so that no two adjacent regions have the same color-is one of these critical problems.

Rota was Stanley's thesis advisor.

Polynomials with interesting sets of zeros

Polynomials with interesting sets of zeros, from Richard Stanley.

There are certain polynomials which are naturally defined in terms of combinatorial objects, which have interesting sets of zeros. For example, consider the polynomials

F₁(x) = x
F₂(x) = x + x²
F₃(x) = x + x² + x³
F₄(x) = x + 2x² + x³ + x⁴
F₅(x) = x + 2x² + 2x³ + x⁴ + x⁵

where the x^k coefficient of F_n(x) is the number of partitions of n into k parts, that is, the number of ways to write n as a sum of k integers where order doesn't matter. For example, the partitions of 5 are

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

which have 1, 2, 2, 3, 3, 4, and 5 parts respectively; that's where F₅ comes from. It turns out that if you take F_n for large n and plot its zeros in the complex plane, you get a nice-looking figure; see this PDF file. This is true of other combinatorially defined families of polynomials as well. The zeroes of this particular set of polynomials are given in some recent work of Robert Boyer and William Goh. (Boyer gave a talk today at Temple which I went to, hence why this is on my mind lately; I'd actually heard about this phenomenon when I took a class from Stanley as an undergrad.)

At least in the case of the partitions, it seems noteworthy that if we sum yⁿ F_n(x) over all n, getting the generating function of all partitions by size and number of parts, we have something nice, namely

and a lot of the other sets of polynomials described by Stanley can probably be described similarly. (Boyer and Goh allude to this at the end of their expository paper.) I don't know enough analytic number theory to say something intelligent about this, though; the proof that the pictures keep looking "like that" (in the case of partition) apparently uses some very heavy machinery.