The n-Category Café

The reverse Bessel polynomials

The reverse Bessel polynomials have many properties. In particular they satisfy the recursion relation $$\theta_{i+1}(R)=R^2\theta_{i-1}(R) + (2i+1)\theta_{i}(R)$$ and $\theta_i(R)$ satisfies the differential equation $$R\theta_i^{\prime\prime}(R)-2(R+i)\theta_i^\prime(R)+2i\theta_i(R)=0.$$ There’s an explicit formula: $$\theta_i(R) = \sum_{t=0}^i \frac{(i+t)!}{(i-t)!\, t!\, 2^t}R^{i-t}.$$

I’m interested in them because they appear in my formula for the magnitude of odd dimensional balls. To be more precise, in my formula I use the associated Sheffer polynomials, $(\chi_i(R))_{i=0}^\infty$; they are related by $\chi_i(R)=R\theta_{i-1}(R)$, so the coefficients are the same, but just moved around a bit. These polynomials have a similar but slightly more complicated combinatorial interpretation.

In my paper I prove that the magnitude of the $(2p+1)$-dimensional ball of radius $R$ has the following expression:

$$\left|B^{2p+1}_R \right|= \frac{\det[\chi_{i+j+2}(R)]_{i,j=0}^p}{(2p+1)!\, R\,\det[\chi_{i+j}(R)]_{i,j=0}^p}$$

As the each polynomial $\chi_i(R)$ has a path counting interpretation, one can use the rather beautiful Lindström-Gessel-Viennot Lemma to give a path counting interpretation to the determinants in the above formula and find some explicit expression. I will probably blog about this another time. (Fellow host Qiaochu has also blogged about the LGV Lemma.)

Weighted Dyck paths

Before getting on to Bessel polynomials and weighted Schröder paths, we need to look at counting weighted Dyck paths, which are simpler and more classical.

A Dyck path is a path in the lattice $\mathbb{Z}^2$ which starts at $(0,0)$, stays in the upper half plane, ends back on the $x$-axis at $(2{i},0)$ and has steps going either diagonally right and up or right and down. The integer $2{i}$ is called the length of the path. Let $D_{i}$ be the set of length $2{i}$ Dyck paths.

For each Dyck path $\sigma$, we will weight each edge going right and down, from $(x,y)$ to $(x+1,y-1)$ by $y$ then we will take $w(\sigma)$, the weight of $\sigma$, to be the product of all the weights on its steps. Here are all five weighted Dyck paths of length six.

Famously, the number of Dyck paths of length $2{i}$ is given by the ${i}$th Catalan number; here, however, we are interested in the number of paths weighted by the weighting(!). If we sum over the weights of each of the above diagrams we get $6+4+2+2+1=15$. Note that this is $5\times 3 \times 1$. This is a pattern that holds in general.

Theorem A. (Françon and Viennot) The weighted count of length $2{i}$ Dyck paths is equal to the double factorial of $2{i} -1$: $$\begin{aligned} \sum_{\sigma\in D_{i}} w(\sigma)&= (2{i} -1)\cdot (2{i} -3)\cdot (2{i}-5)\cdot \cdots\cdot 3\cdot 1 \\ &\eqqcolon (2{i} -1)!!. \end{aligned}$$

The following is a nice combinatorial proof of this theorem that I found in a survey paper by Callan. (I was only previously aware of a high-tech proof involving continued fractions and a theorem of Gauss.)

The first thing to note is that the weight of a Dyck path is actually counting something. It is counting the ways of labelling each of the down steps in the diagram by a positive integer less than the height (i.e.~the weight) of that step. We call such a labelling a height labelling. Note that we have no choice of weighting but we often have choice of height labelling. Here’s a height labelled Dyck path.

So the weighted count of Dyck paths of length $2{i}$ is precisely the number of height labelled Dyck paths of length $2{i}$. $$\sum_{\sigma\in D_{i}} w(\sigma) = \#\{\text{height labelled paths of length }\,\,2{i}\}$$

We are going to consider marked Dyck paths, which just means we single out a specific vertex. A path of length $2{i}$ has $2{i} + 1$ vertices. Thus

$$\begin{aligned} \#\{\text{height labelled,}\,\, &\text{ MARKED paths of length }\,\,2{i}\}\\ &=(2{i}+1)\times\#\{\text{height labelled paths of length }\,\,2{i}\}. \end{aligned}$$

Hence the theorem will follow by induction if we find a bijection

$$\begin{aligned} \{\text{height labelled,}\,\,&\text{ paths of length }\,\,2{i} \}\\ &\cong \{\text{height labelled, MARKED paths of length }\,\,2{i}-2 \}. \end{aligned}$$

Such a bijection can be constructed in the following way. Given a height labelled Dyck path, remove the left-hand step and the first step that has a label of one on it. On each down step between these two deleted steps decrease the label by one. Now join the two separated parts of the path together and mark the vertex at which they are joined. Here is an example of the process.

Working backwards it is easy to describe the inverse map. And so the theorem is proved.

Schröder paths and reverse Bessel polynomials

In order to give a path theoretic interpretation of reverse Bessel polynomials we will need to use Schröder paths. These are like Dyck paths except we allow a certain kind of flat step.

A Schröder path is a path in the lattice $\mathbb{Z}^2$ which starts at $(0,0)$, stays in the upper half plane, ends back on the $x$-axis at $(2{i},0)$ and has steps going either diagonally right and up, diagonally right and down, or horizontally two units to the right. The integer $2{i}$ is called the length of the path. Let $S_{i}$ be the set of all length $2{i}$ Schröder paths.

For each Schröder path $\sigma$, we will weight each edge going right and down, from $(x,y)$ to $(x+1,y-1)$ by $y$ and we will weight each flat edge by the indeterminate $R$. Then we will take $w(\sigma)$, the weight of $\sigma$, to be the product of all the weights on its steps.

Here is the picture of all six length four weighted Schröder paths again.

You were asked at the top of this post to check that the sum of the weights equals the second reverse Bessel polynomial. Of course that result generalizes!

The following theorem was shown to me by Alan Sokal, he proved it using continued fractions methods, but these essentially amount to the combinatorial proof I’m about to give.

Theorem B. The weighted count of length $2{i}$ Schröder paths is equal to the ${i}$th reverse Bessel polynomial: $$\sum_{\sigma\in S_{i}} w(\sigma)= \theta_{i}(R).$$

The idea is to observe that you can remove the flat steps from a weighted Schröder path to obtain a weighted Dyck path. If a Schröder path has length $2{i}$ and $t$ upward steps then it has $t$ downward steps and ${i}-t$ flat steps, so it has a total of ${i}+t$ steps. This means that there are $\binom{{i}+t}{{i}-t}$ length $2{i}$ Schröder paths with the same underlying length $2t$ Dyck path (we just choose were to insert the flat steps). Let’s write $S^t_{i}$ for the set of Schröder paths of length $2{i}$ with $t$ upward steps. $$\begin{aligned} \sum_{\sigma\in S_{i}} w(\sigma) &= \sum_{t=0}^{i} \sum_{\sigma\in S^t_{i}} w(\sigma) = \sum_{t=0}^{i} \binom{{i}+t}{{i}-t}\sum_{\sigma'\in D_t} w(\sigma')R^{{i}-t}\\ &= \sum_{t=0}^{i} \binom{{i}+t}{{i}-t}(2t-1)!!\,R^{{i}-t}\\ &= \sum_{t=0}^{i} \frac{({i}+t)!}{({i}-t)!\,(2t)!}\frac{(2t)!}{2^t t!}R^{{i}-t}\\ &= \theta_{i}(R), \end{aligned}$$ where the last equality comes from the formula for $\theta_{i}(R)$ given at the beginning of the post.

Thus we have the required combinatorial interpretation of the reverse Bessel polynomials.

Further questions

The first question that springs to mind for me is if it is possible to give a bijective proof of Theorem B, similar in style, perhaps (or perhaps not), to the proof given of Theorem A, basically using the recursion relation $$\theta_{i+1}(R)=R^2\theta_{i-1}(R) + (2i+1)\theta_{i}(R)$$ rather than the explicit formular for them.

The second question would be whether the differential equation $$R\theta_i^{\prime\prime}(R)-2(R+i)\theta_i^\prime(R)+2i\theta_i(R)=0.$$ has some sort of combinatorial interpretation in terms of paths.

I’m interested to hear if anyone has any thoughts.