Update, and the combinatorics of quintic equations

A brief update. I’ve been at Cambridge for the last week or so now, and lectures have finally started. I am, tentatively, taking the following Part II classes: Riemann Surfaces Topics in Analysis Probability and Measure Graph Theory Linear Analysis (Functional Analysis) Logic and Set Theory I will also attempt to sit in on Part [...]

Read Full Post »

Graded representation theory

Let be a group and let be a graded representation of , i.e. a functor from to the category of graded vector spaces with each piece finite-dimensional. Thus acts on each graded piece individually, each of which is an ordinary finite-dimensional representation. We want to define a character associated to a graded representation, but if [...]

Read Full Post »

The Lindstrom-Gessel-Viennot lemma

One of my favorite results in algebraic combinatorics is a surprisingly useful lemma which allows a combinatorial interpretation of the determinant of certain integer matrices. One of its more popular uses is to prove an equivalence between three other definitions of the Schur functions (none of which I have given yet), but I find its [...]

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions II

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space and a function , and under the assumption that has a finite number of fixed points for all , we define the dynamical zeta function to be the formal power series . What I didn’t do was [...]

Read Full Post »

Extracting the diagonal

Needless to say, I have been very, very busy. But enough about me. Suppose you are given a bivariate generating function in “closed form,” where I’ll be vague about what that means. Such a generating function may arise, for example, from counting lattice paths in ; then might count the number of paths from to [...]

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that . One way to motivate a combinatorial proof is to [...]

Read Full Post »

Kraft’s inequality for prefix codes

Kraft’s inequality: Let be a prefix code on an alphabet of size , and let denote the number of codewords of length . Then . In lieu of reposting my old blog posts I thought I’d revisit some of their topics instead. In an old post of mine I set this inequality as a practice [...]

Read Full Post »

GILA VI: The cycle index polynomials of the symmetric groups

In the previous post we used the Polya enumeration theorem to give a sneaky, underhanded proof that . 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 [...]

Read Full Post »

GILA V: The Polya enumeration theorem and applications

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 (represented by variables [...]

Read Full Post »

GILA IV: The unreasonable effectiveness of generating functions in the combinatorial sciences

We’ve got everything we need to prove the Polya enumeration theorem. To state the theorem, however, requires the language of generating functions, so I thought I’d take the time to establish some of the important ideas. It isn’t possible to do justice to the subject in one post, so I’ll start with some references. Many [...]

Read Full Post »