Posts Tagged ‘Catalan numbers’

There are, roughly speaking, two kinds of algebras that can be functorially constructed from a group G. The kind which is covariantly functorial is some variation on the group algebra k[G], which is the free k-module on G with multiplication inherited from the multiplication on G. The kind which is contravariantly functorial is some variation on the algebra k^G of functions G \to k with pointwise multiplication.

When k = \mathbb{C} and when G is respectively either a discrete group or a compact (Hausdorff) group, both of these algebras can naturally be endowed with the structure of a random algebra. In the case of \mathbb{C}[G], the corresponding state is a noncommutative refinement of Plancherel measure on the irreducible representations of G, while in the case of \mathbb{C}^G, the corresponding state is by definition integration with respect to normalized Haar measure on G.

In general, some nontrivial analysis is necessary to show that the normalized Haar measure exists, but for compact groups equipped with a faithful finite-dimensional unitary representation V it is possible to at least describe integration against Haar measure for a dense subalgebra of the algebra of class functions on G using representation theory. This construction will in some sense explain why the category \text{Rep}(G) of (finite-dimensional continuous unitary) representations of G behaves like an inner product space (with \text{Hom}(V, W) being analogous to the inner product); what it actually behaves like is a random algebra, namely the random algebra of class functions on G.


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 »

Recently I asked a question on MO about some computations I’d done with Catalan numbers awhile ago on this blog, and Scott Morrison gave a beautiful answer explaining them in terms of quantum groups. Now, I don’t exactly know how quantum groups work, but along the way he described a useful connection between walks on graphs and tensor products of representations which at least partially explains one of the results I’d been wondering about and also unites several other related computations that have been on my mind recently.

Let G be a compact group and let \text{Rep}(G) denote the category of finite-dimensional unitary representations of G. As in the finite case, due to the existence of Haar measure, \text{Rep}(G) is semisimple (i.e. every unitary representation decomposes uniquely into a sum of irreducible representations), and via the diagonal action it comes equipped with a tensor product with the property that the character of the tensor product is the product of the characters of the factors.

Question: Fix a representation V \in \text{Rep}(G). What is the multiplicity of the trivial representation in V^{\otimes n}?


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 »

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time.

Let C(x) = \sum_{n \ge 0} C_n x^n be the ordinary generating function for the ordered rooted trees on n+1 vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the Catalan numbers. From a species perspective, ordered rooted trees are defined by the functional equation

\displaystyle C(x) = \frac{1}{1 - xC(x)}.

The generating function \frac{1}{1 - x} = 1 + x^2 + ... describes the species \textsc{Seq} of sequences. So what this definition means is that, after tossing out the root, an ordered rooted tree is equivalent to a sequence of ordered rooted trees (counting their roots) in the obvious way; the roots of these trees are precisely the neighbors of the original root. Multiplying out gets us a quadratic equation we can use to find the usual closed form of C(x), but we can instead recursively apply the above to obtain the beautiful continued fraction

\displaystyle C(x) = \frac{1}{1 - \frac{x}{1 - \frac{x}{1 - ...}}}.

Today’s discussion will center around this identity and some of its consequences.


Read Full Post »