## August 28, 2017

### Schröder Paths and Reverse Bessel Polynomials

#### Posted by Simon Willerton

I want to show you a combinatorial interpretation of the reverse Bessel polynomials which I learnt from Alan Sokal. The sequence of reverse Bessel polynomials begins as follows.

\begin{aligned} \theta_0(R)&=1\\ \theta_1(R)&=R+1\\ \theta_2(R)&=R^2+3R+3\\ \theta_3(R)&= R^3 +6R^2+15R+15 \end{aligned}

To give you a flavour of the combinatorial interpretation we will prove, you can see that the second reverse Bessel polynomial can be read off the following set of ‘weighted Schröder paths’: multiply the weights together on each path and add up the resulting monomials.

In this post I’ll explain how to prove the general result, using a certain result about weighted Dyck paths that I’ll also prove. At the end I’ll leave some further questions for the budding enumerative combinatorialists amongst you.

These reverse Bessel polynomials have their origins in the theory of Bessel functions, but which I’ve encountered in the theory of magnitude, and they are key to a formula I give for the magnitude of an odd dimensional ball which I have just posted on the arxiv.

In that paper I use the combinatorial expression for these Bessel polynomials to prove facts about the magnitude.

Here, to simplify things slightly, I have used the standard reverse Bessel polynomials whereas in my paper I use a minor variant (see below).

I should add that a very similar expression can be given for the ordinary, unreversed Bessel polynomials; you just need a minor modification to the way the weights on the Schröder paths are defined. I will leave that as an exercise.

## 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.

Posted at August 28, 2017 1:09 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2980

### Re: Schröder Paths and Reverse Bessel Polynomials

Interesting post! One thing that comes to mind: have you tried considering the reverse Bessel polynomials in terms of involutions, or equivalently in terms of rooted chord diagrams? There is a simple bijection between height labelled Dyck paths and fixed point free involutions, which I think is easiest to visualize using the representation of involutions by diagrams: scanning a labelled Dyck path from left to right, every NE step introduces a rising arc, while every SE($i$) step introduces a falling arc that closes the $i$th unattached arc. For example, the height labelled Dyck path NE NE NE SE(1) SE(2) SE(1) from your example corresponds to the rooted chord diagram

and to the fixed point free involution (1 4)(2 6)(3 5).

This interpretation extends to weighted Schröder paths by allowing rooted chord diagrams with unattached marked points, hence fixed points of the corresponding involution. For example, under this interpretation the weighted Schröder path NE EE SE(1) corresponds to the involution (1 3)(2), while the path EE NE SE(1) corresponds to the involution (1) (2 3).

I don’t quite see how to interpret the recursion relation for $\theta_i(R)$ in terms of involutions/chord diagrams. However, consider the formal power series which gathers together all of the reverse Bessel polynomials: $\theta(z,x) = \sum_i \theta_i(x) z^i$ Reinterpreting weighted Schröder paths as involutions, Theorem B implies that $\theta(z,x)$ can be seen as the bivariate generating function counting involutions by total number of cycles ($z$) and number of 1-cycles/fixed points ($x$). I wonder whether it might potentially be useful to consider the reparameterization $\theta(z,x) = \kappa(z x,x)$ where $\kappa(z,x)$ is the bivariate generating function counting involutions by number of 2-cycles ($z$) and 1-cycles ($x$) (or equivalently, rooted chord diagrams by number of chords and number of marked points)? In particular, $\kappa(z,x)$ satisfies the functional-differential equation $\kappa(z,x) = 1 + x\kappa(z,x) + z\frac{\partial \kappa(z,x)}{\partial x}$ which has the following simple interpretation: starting from the empty rooted chord diagram (1), we can build a larger diagram either by adding an unattached point at the end of a smaller diagram ($x\kappa(z,x)$), or by picking an unattached point of the smaller diagram and closing it with a chord ($z\frac{\partial \kappa(z,x)}{\partial x}$).

Posted by: Noam Zeilberger on August 30, 2017 1:16 PM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

Ah, interesting. As you know, because you seem to have written the nLab page on chord diagrams, I have had quite an interest in chord diagrams in the past in relation to Vassiliev knot invariants.

Anyway, what you’re saying then, is if we let $I_i$ be the set of involutions consisting of $i$ cycles then the $i$th reverse Bessel polynomial has the following interpretation:

\begin{aligned} \theta_i(R) &= \sum_{\sigma\in I_i} R^{\# fix(\sigma)}\\ &=\sum_{k=0}^{i}\#\{\text{involutions with}\,\,i\,\,\text{cycles and}\,\,k\,\, \text{fixed points}\}\,R^k \end{aligned}

This seems a little odd in some sense that we’re not saying what set the involution is acting on. Indeed, I can’t think of a good way of saying it without it sounding artificial.

I had a play, but I couldn’t make the recursion work.

Posted by: Simon Willerton on August 30, 2017 11:28 PM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

Well, to be formal we should probably take $I_i$ to be the set of isomorphism classes of linearly ordered sets $(X,\le)$ equipped with an involution $\sigma : X \to X$ with $i$ cycles, or equivalently, isomorphism classes of rooted chord diagrams with some number $k$ of marked points and $i-k$ chords.

I’m not sure whether the reparameterization and the differential equation I suggested above are actually useful (also, there was a small bug: that should be $\theta(z,x) = \kappa(z,z x)$), but I did find an abstract for a paper by Serge Dulucq and Luc Favreau on A combinatorial model for Bessel polynomials “based upon weighted involutions” that looks encouraging. Sadly, that paper does not seem to be available online, but there is another short followup paper by Dulucq that at least gives a hint of what they did. There, Dulucq defines a q-analogue of the (ordinary, rather than reverse) Bessel polynomials by $y_n(x;q) = \sum_{k=0}^n \sum_{\alpha \in I_{n,k}} q^{s(\alpha)} x^k$ where $I_{n,k}$ is the set of involutions with $n$ cycles and $k$ 2-cycles, and $s(-)$ is a certain weighting function on involutions. He states q-analogues of the explicit formula and the recurrence relation for the $y_n$ as theorems, but sadly there are no proofs.

Posted by: Noam Zeilberger on August 31, 2017 4:01 AM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

Oh, the proofs are in Chapter 4 of Favreau’s thesis! It’s in French, but with lots of illustrations…in particular, Figure 4.3 on p.78 gives a graphical bijection (using rooted chord diagrams!) to account for the recurrence relation defining the Bessel polynomials. The text refers to the ordinary Bessel polynomials, but the same exact bijection also works for the reverse Bessel polynomials – here is a sketch of Favreau’s argument, translated in reverse:

Consider an involution $\sigma$ with $n+1$ cycles and $k$ fixed points on a linearly ordered set, represented as a rooted chord diagram. We examine the rightmost point $x$ of the diagram (i.e., the greatest element of the underlying set). There are two possiblities:

• $\sigma(x) = x$: In this case we remove $x$ to obtain a smaller diagram $\sigma'$ with $n$ cycles and $k-1$ fixed points. Then we repeat the process on $\sigma'$, considering its rightmost point $x'$:
• $\sigma'(x') = x'$: In this case we remove $x'$ to obtain a smaller diagram $\tau_1$ with $n-1$ cycles and $k-2$ fixed points.
• $\sigma'(x') \ne x'$: In this case we remove $x'$ but keep its left end, obtaining a smaller diagram $\tau_2$ with $n$ cycles and $k$ fixed points, equipped with a marked fixed point.
• $\sigma(x) \ne x$: In this case we remove the chord (i.e., 2-cycle) $\{x, \sigma(x)\}$ while remembering the location of its left end $\sigma(x)$, obtaining a diagram $\tau_3$ with $n$ cycles and $k$ fixed points, equipped with a marked interval.

Let $I_{n,k}$ denote the set of (isomorphism classes of) involutions with $n$ cycles and $k$ fixed points. Noting that the number of intervals in a diagram is equal to one plus the number of points, the above argument establishes a bijection $I_{n+1,k} \cong I_{n-1,k-2} \uplus [k] \times I_{n,k} \uplus [2(n-k) + k + 1] \times I_{n,k} \cong I_{n-1,k-2} \uplus [2n + 1] \times I_{n,k}$ thus proving the recurrence $\theta_{i+1}(R) = R^2 \theta_{i-1}(R) + 2(i+1) \theta_i(R)$.

Nice! Favreau also gives bijective proofs of some differential equations that I think are related to yours, but I haven’t tried to read that part.

Posted by: Noam Zeilberger on August 31, 2017 11:15 AM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

Splendid! That’s very much the kind of bijection that I expected, but I didn’t know how to find it…

The differential equation is the unreversed counterpart of the differential equation I gave. So the proof should translate to a proof of the one I gave.

Posted by: Simon Willerton on August 31, 2017 12:15 PM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

For completeness, I’ll record here the translation of Favreau’s result into Schröder paths. This way I’ll be able to find the explicit answer to my question when I forget it.

Let’s define $T_{i,k}\coloneqq\{\text{height labelled Schr\"oder paths of length}\,\,2i\,\,\text{with}\,\,k\,\,\text{flat steps}\}$ where height labelled means that the downward steps are labelled with a positive integer less than or equal to the height of the step; flat steps are unlabelled.

Also, define $T^{\text{flat marked}}_{i,k}\coloneqq\{\text{paths in}\,\,T_{i,k}\,\,\text{with one of the flat steps marked}\}$ and $T^{\text{vertex marked}}_{i,k}\coloneqq\{\text{paths in}\,\,T_{i,k}\,\,\text{with one of the vertices marked}\}.$

Note that a path in $T_{i,k}$ has $i-k$ up steps, $i-k$ down steps and $k$ flat steps, so $2i-k$ steps in total, which means $2i-k+1$ vertices.

The key combinatorial lemma then is the following.

Lemma. For $i\ge 2$, there is a bijection of sets $T_{i,k}\cong T_{i-2,k-2} \sqcup T^{\text{flat marked}}_{i-1,k} \sqcup T^{\text{vertex marked}}_{i-1,k}.$

I’ll give a map out of each of the sets on the right hand side into the set on the left hand side. It’s easy to check that they assemble to an isomorphism.

• For the map $T_{i-2,k-2}\to T_{i,k}$ just prepend two flat steps to the beginning of the path.

• For the map $T^{\text{flat marked}}_{i-1,k}\to T_{i,k}$, raise by one unit everything to the left of the marked flat step and increase by one all the labels that are raised. Change the marked flat step into a down step labelled by $1$ and prepend a flat step followed by an up step to the beginning of the path.

• For the map $T^{\text{vertex marked}}_{i-1,k}\to T_{i,k}$, raise by one unit everything to the left of the marked vertex and increase by one all the labels that are raised. At the marked vertex insert a down step labelled by $1$ and prepend an up step to the beginning of the path.

(For the inverse map you look at what the first one or two steps in your Schröder path are, and then you might need to find the first down step marked with a $1$.)

Taking cardinality we immediately get the following.

Corollary. For $i\ge 2$, we have \begin{aligned} \# T_{i,k} &= \#T_{i-2,k-2} + k \# T_{i-1,k} +(2i- k+1) \#T_{i-1,k} \\ &= \#T_{i-2,k-2} + (2i-1) \# T_{i-1,k}. \end{aligned}

Defining $\theta_i(R):=\sum_{k=0}^i \#T_{i,k} R^k$, we see from the corollary that these satisfy the required recursion formula.

I have to say that this feels a little less satisfying than I’d hoped, as the constructed bijection does feel somewhat more ad hoc than I might have liked. But I ought not grumble too much…

Posted by: Simon Willerton on September 3, 2017 5:11 PM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

First he wants a bijective proof. Then he wants a charming bijective proof.

Posted by: John Baez on September 7, 2017 1:23 AM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

I wonder if there’s a categorical definition of “charming”?

For instance, we could all write down a bijective proof that the number of total orderings on a finite set is equal to the number of permutations of it. But I don’t think any of us could write down one that’s charming. That’s because of the fact, I guess due to Joyal, that the corresponding pair of functors from [finite sets and bijections] to Set are not naturally isomorphic.

By the way, John, I’m still enjoying the moment in Sapporo when you asked me if I knew what a ring species, and for a moment I thought you meant a ring-theoretic version of a combinatorial species. It seemed plausible at the time.

Posted by: Tom Leinster on September 8, 2017 9:33 PM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

It does seem there are some natural bijections between pairs of Minimal-length Well-Orders and pairs of permutations. If your Sets believe in minimal-length well-orders, that is…

Posted by: Jesse C. McKeown on September 11, 2017 2:27 AM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

No, I’m sorry… that’s wrong…

Posted by: Jesse C. McKeown on September 11, 2017 2:29 AM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

“Ring species” and “combinatorial species” — I love it! The natural follow-up would be to devise a biological meaning for the term “combinatorial species”. For example, since how a gene gets expressed depends upon its position, it is conceivable that two populations could have the same genomes, up to permutations, and yet be unable to interbreed.

And a sequence of populations arranged in space, such that any two adjacent populations can interbreed but the populations at the two ends of the chain cannot, with the genomes of all the populations related by permutations, would be a combinatorial ring species.

If this occurred near the equator, the spatial distribution of these remarkable organisms would be studied using tropical geometry.

Posted by: Blake Stacey on September 10, 2017 11:44 PM | Permalink | Reply to this

### Re: Schröder Paths and Reverse Bessel Polynomials

So, what has all this to do with the Quantum Harmonic Oscilator?

Posted by: Jesse C. McKeown on September 8, 2017 7:36 PM | Permalink | Reply to this

Post a New Comment