Feeds:
Posts
Comments

Posts Tagged ‘cycle indices’

Previously we showed that the distribution of fixed points of a random permutation of n elements behaves asymptotically (in the limit as n \to \infty) like a Poisson random variable with parameter \lambda = 1. As it turns out, this generalizes to the following.

Theorem: As n \to \infty, the number of cycles of length 1, 2, ... k of a random permutation of n elements are asymptotically independent Poisson with parameters 1, \frac{1}{2}, ... \frac{1}{k}.

This is a fairly strong statement which essentially settles the asymptotic description of short cycles in random permutations.

(more…)

Read Full Post »

The following two results are straightforward and reasonably well-known exercises in combinatorics:

  1. The number of permutations on n elements with no fixed points (derangements) is approximately \frac{n!}{e}.
  2. The expected number of fixed points of a random permutation on n elements is 1.

As it turns out, it is possible to say substantially more about the distribution of fixed points of a random permutation. In fact, the following is true.

Theorem: As n \to \infty, the distribution of the number of fixed points of a random permutation on n elements is asymptotically Poisson with rate \lambda = 1.

(more…)

Read Full Post »

The theory of symmetric functions, which generalizes some ideas that came up in the previous discussion of Polya theory, can be motivated by thinking about polynomial functions of the roots of a monic polynomial P(x) \in \mathbb{Z}[x]. Problems on high school competitions often ask for the sum of the squares or the cubes of the roots of a given polynomial, and those not familiar with symmetric functions will often be surprised that these quantities end up being integers even though the roots themselves aren’t integers. The key is that the sums being asked for are always symmetric in the roots, i.e. invariant under an arbitrary permutation. The coefficients of a monic polynomial are the elementary symmetric polynomials of its roots, which we are given are integers. It follows that any symmetric polynomial that can be written using integer coefficients in terms of the elementary symmetric polynomials must in fact be an integer, and as we will see, every symmetric polynomial with integer coefficients has this property.

These ideas lead naturally to the use of symmetric polynomials in Galois theory, but combinatorialists are interested in symmetric functions for a very different reason involving the representation theory of S_n. This post is a brief overview of the basic results of symmetric function theory relevant to combinatorialists. I’m mostly following Sagan, who recommends Macdonald as a more comprehensive reference.

(more…)

Read Full Post »

In the previous post we used the Polya enumeration theorem to give a sneaky, underhanded proof that

\displaystyle \sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right).

If you’ve never seen the exponential function used like this, you might be wondering how it can be “explained.”

To explore this question, I’d like to give three other proofs of this result, the last of which will be “direct.” Along the way I’ll be attempting to describe some basic principles of species theory in an informal way. I’ll also give some applications, including to a Putnam problem.

(more…)

Read Full Post »

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors 1, 2, ... n (represented by variables r_1, r_2, ... r_n), and we have a set of slots S with |S| = m acted on by a group G where each slot will be assigned a color. Define f_G(t_1, ... t_n) to be the number of orbits of functions S \to \{ 1, 2, ... n \} under the action of G where color i is used t_i times. (Since the action of G only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

\displaystyle F_G(r_1, r_2, ... r_n) = \sum_{t_1 + ... + t_n = m} f_G(t_1, t_2, ... t_n) r_1^{t_1} r_2^{t_2} ... r_n^{t_n}.

Note that setting r_1 = r_2 = .... = r_n = 1 we recover F_G(n), which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

\displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |(r_1, r_2, ... r_n)

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?

(more…)

Read Full Post »

Follow

Get every new post delivered to your Inbox.

Join 282 other followers