Posts Tagged ‘generating functions’

Previously I mentioned very briefly Granville’s The Anatomy of Integers and Permutations, which explores an analogy between prime factorizations of integers and cycle decompositions of permutations. Today’s post is a record of the observation that this analogy factors through an analogy to prime factorizations of polynomials over finite fields in the following sense.

Theorem: Let q be a prime power, let n be a positive integer, and consider the distribution of irreducible factors of degree 1, 2, ... k in a random monic polynomial of degree n over \mathbb{F}_q. Then, as q \to \infty, this distribution is asymptotically the distribution of cycles of length 1, 2, ... k in a random permutation of n elements.

One can even name what this random permutation ought to be: namely, it is the Frobenius map x \mapsto x^q acting on the roots of a random polynomial f, whose cycles of length k are precisely the factors of degree k of f.

Combined with our previous result, we conclude that as q, n \to \infty (with q tending to infinity sufficiently quickly relative to n), the distribution of irreducible factors of degree 1, 2, ... k is asymptotically independent Poisson with parameters 1, \frac{1}{2}, ... \frac{1}{k}.


Read Full Post »

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.


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.


Read Full Post »

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional ^{\dagger}-algebra \mathbb{C}[x]. Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.


Read Full Post »

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 III Algebraic Number Theory, and I will also be self-studying Part II Number Theory and Galois Theory for the Tripos.

As far as this blog goes, my current plan is to blog about interesting topics which come up in my lectures and self-study, partly as a study tool and partly because there are a few big theorems I’d like to get around to understanding this year and some of the material in my lectures will be useful for those theorems.

Today I’d like to blog about something completely different. Here is a fun trick the first half of which I learned somewhere on MO. Recall that the Abel-Ruffini theorem states that the roots of a general quintic polynomial cannot in general be written down in terms of radicals. However, it is known that it is possible to solve general quintics if in addition to radicals one allows Bring radicals. To state this result in a form which will be particularly convenient for the following post, this is equivalent to being able to solve a quintic of the form

\displaystyle y = 1 + xy^5

for y in terms of x. It just so happens that a particular branch of the above function has a particularly nice Taylor series; in fact, the branch analytic in a neighborhood of the origin is given by

\displaystyle y = \sum_{n \ge 0} \frac{1}{4n+1} {5n \choose n} x^n.

This should remind you of the well-known fact that the generating function \displaystyle y = \sum_{n \ge 0} \frac{1}{n+1} {2n \choose n} x^n for the Catalan numbers satisfies y = 1 + xy^2. In fact, there is a really nice combinatorial proof of the following general fact: the generating function \displaystyle y = \sum_{n \ge 0} \frac{1}{(k-1)n+1} {kn \choose n} x^n satisfies

y = 1 + xy^k.


Read Full Post »

Let G be a group and let

\displaystyle V = \bigoplus_{n \ge 0} V_n

be a graded representation of G, i.e. a functor from G to the category of graded vector spaces with each piece finite-dimensional. Thus G acts on each graded piece V_i individually, each of which is an ordinary finite-dimensional representation. We want to define a character associated to a graded representation, but if a character is to have any hope of uniquely describing a representation it must contain information about the character on every finite-dimensional piece simultaneously. The natural definition here is the graded trace

\displaystyle \chi_V(g) = \sum_{n \ge 0} \chi_{V_n}(g) t^n.

In particular, the graded trace of the identity is the graded dimension or Hilbert series of V.

Classically a case of particular interest is when V_n = \text{Sym}^n(W^{*}) for some fixed representation W, since V = \text{Sym}(W^{*}) is the symmetric algebra (in particular, commutative ring) of polynomial functions on W invariant under G. In the nicest cases (for example when G is finite), V is finitely generated, hence Noetherian, and \text{Spec } V is a variety which describes the quotient W/G.

In a previous post we discussed instead the case where V_n = (W^{*})^{\otimes n} for some fixed representation W, hence V is the tensor algebra of functions on W. I thought it might be interesting to discuss some generalities about these graded representations, so that’s what we’ll be doing today.


Read Full Post »

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 other applications equally endearing.

Let G be a locally finite directed acyclic graph, i.e. it has a not necessarily finite vertex set V with finitely many edges between each pair of vertices such that no collection of edges forms a cycle. For example, G could be \mathbb{Z}^2 with edges (x, y) \to (x, y + 1) and (x, y) \to (x + 1, y ), which we’ll denote the acyclic plane. Assign a weight w(e) to each edge and assign to a path the product of the weights of its edges. Given two vertices a, b let e(a, b) denote the sum of the weights of the paths from a to b. Hence even if there are infinitely many such paths this sum is well-defined formally, and if there are only finitely many paths between two vertices then setting each weight to 1 gives a well-defined non-negative integer.

Let a_1, ... a_n and b_1, ... b_n be a collection of vertices called sources and vertices called sinks. We are interested in n-tuples of paths, hereafter to be referred to as n-paths, sending each source to a distinct sink. Let \mathbf{M} be the n \times n matrix such that \mathbf{M}_{ij} = e(a_i, b_j). Then the permanent of \mathbf{M} counts the number of n-paths, but this is not interesting as permanents are hard to compute.

A n-path is called non-intersecting if none of the paths that make it up share a vertex; in particular, each a_i is sent to distinct b_i. A non-intersecting path determines a permutation \pi of the vertices; let the sign of a non-intersecting n-path be the sign of this permutation.

Lemma (Lindström, Gessel-Viennot): \det \mathbf{M} is the signed sum of the weights of all non-intersecting n-paths.

Corollary: If the only possible permutation is \pi = 1 (i.e. G is non-permutable), then \det \mathbf{M} is the sum of the weights of all non-intersecting n-paths.


Read Full Post »

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space X and a function f : X \to X, and under the assumption that f^n has a finite number of fixed points for all n, we define the dynamical zeta function to be the formal power series

\displaystyle \zeta_X(t) = \exp \sum_{n \ge 1} (\text{Fix } f^n) \frac{t^n}{n}.

What I didn’t do was motivate this definition, mostly because I hadn’t really worked out the motivation myself. Now that we have an important special case worked out, we can discuss the general case, which will give a purely combinatorial proof of the second half of the Newton-Girard identities.


Read Full Post »

Suppose you are given a bivariate generating function

\displaystyle F(x, y) = \sum_{m, n \ge 0} f(m, n) x^m y^n

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 \mathbb{Z}_{\ge 0}^2; then f(m, n) might count the number of paths from (0, 0) to (m, n). If the path is only constrained by the fact that its steps must come from some set S \subset \mathbb{Z}_{\ge 0}^2 of steps containing only up or left steps, then we have the simple identity

\displaystyle F_S(x, y) = \frac{1}{1 - \sum_{(a, b) \in S} x^a y^b}.

Question: When can we determine the generating function \displaystyle D_F(x) = \sum_{n \ge 0} f(n, n) x^n in closed form?

I’d like to discuss an analytic approach to this question that gives concrete answers in at least a few important special cases, including the generating function for the central binomial coefficients, which is our motivating example.


Read Full Post »

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

\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial C(t) with non-negative integer coefficients and C(0) = 0, let r_1, ... r_n be the reciprocals of the roots of C(t) - 1 = 0. Then

\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by C(t). Today we’ll describe this species when C(t) is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.


Read Full Post »

Older Posts »