# Rational generating function and recursion

Let $\lambda$ denote a hook of size $d$ and $c(\Box)$ the content of $\Box \in \lambda$. Let $\text{Hooks}(d)$ be the set of hooks with $d$ boxes. Define \begin{align} B(d)&= \frac{1}{d!} \sum_{\lambda\in \text{Hooks}(d)} (-1)^{ht(\lambda)-1} \, \dim \lambda \,\color{red}{\prod_{\Box \in \lambda}(1-c(\Box)h)^2}\\ &= \frac{1}{dd!}\sum_{\ell=1}^{d} (-1)^{(\ell+1)}\binom{d-1}{\ell-1}\prod_{i=1}^{d}(1-(\ell-i)h)^2 \end{align} So $B(d)$ is a polynomial in $h$

I have noticed the following recursion for $B(d)$. \begin{align} d(d+1)B(d)=(d-1)(4d-2)B(d-1)+h^2(d-1)^2(d-2)^2B(d-2) \end{align} I am now trying to prove the recursion by comparing the coefficient of $h^k$ on the R.H.S and L.H.S. I have a combinatorial interpretation for the leading coefficient for a fixed $d$ and can prove that they are equal. I still do not have a combinatorial interpretation for other powers of $h^k$. Also proving the recursion in this way cannot be generalised.
For example if I replace the $\color{red} {red \, part}$ of my equation with $\prod_{i=1}^{d} (1-(\ell-1)h)^m$ then it would be a different with differential combinatorial interpreation to prove it.

I have seen theorems involving rational generating function in chapter 4 volume 1 of Enumerative combinatorics. Theorem 4.1.1 states that if the generating function is rational, then, there is a recurrence among the coefficient. Note that my $B(d)$ are not complex numbers but polynomial in $h$. Showing that $\sum_{d \geqslant 0} B(d) X^d$ is a rational function in $X$ would thus prove the existence of a recurrence, which is what I am looking for.

Also, I have noticed that my recursion is a three-term recursion between polynomials in $h$, so I was wondering if there is a known technique from the theory of orthogonal polynomial that would prove such things? Of course, this is not a typical three-term relationship since it does not involve any multiplication by $h$.

Any ideas would be very helpful.

• What does this have to do with computability theory? Aug 25, 2017 at 1:36
• I removed the tag. Aug 25, 2017 at 9:23

$\textit{Lemma :}$ We have
\begin{align*}%\frac{1}{d!} \sum_{\lambda\in \text{Hooks}(d)} (-1)^{\ell(\lambda)-1} \, \dim \lambda \prod_{\Box \in \lambda}(x + c(\Box) )(y + c(\Box) ) = [c_d]\prod_{k = 1}^d (x + J_k) (y + J_k) \end{align*} where \begin{align*}% J_1 = 0 \, ; J_2 = (1, 2) \, ; \qquad J_k = (1, k) + \cdots + (k - 1, k) \end{align*} are the Jucys-Murphy elements of the symmetric group $\mathfrak{S}_d$, i.e. particular elements of the group algebra $\mathbb{C}\mathfrak{S}_d$ that commute with each other and that generate the centre $Z(\mathbb{C}\mathfrak{S}_d)$ in a certain way (symmetric functions in the JM elements generate it). Here we have noted $[\sigma]f$ the coefficient of $\sigma$ in $f \in \mathbb{C}\mathfrak{S}_d$, namely, if $f = \sum_{ \sigma \in \mathfrak{S}_d } f_\sigma \sigma$, then $[\sigma]f = f_\sigma$. Last, $c_d$ is any $d$-cycle, for instance $(1, 2, \dots, d)$.



$\textit{Proof.}$ We prove this last formula using the dual orthogonality of the characters of $\mathfrak{S}_d$ : denote by $\chi^\lambda$ such a character. Then, for all $\sigma, \tau \in \mathfrak{S}_d$ \begin{align*}%\frac{1}{d!} \sum_{ \lambda \vdash d } \chi^\lambda(\sigma) \chi^\lambda(\tau) = \delta_{\sigma, \tau} \end{align*} We have used the fact that \chi^\lambda(\sigma) \in \mathbb{Z} to avoid writing a conjugation on one of the characters. The next step is the formula (that one can prove with the Murnaghan-Nakayama formula) \begin{align*}% \chi^\lambda(c_d) =: \chi^\lambda_{(d)} = (-1)^{\ell(\lambda) + 1} \mathbb{1}_{ \{ \lambda \in \mathrm{Hooks}(d) \} } \end{align*}

We thus have \begin{align*}%\delta_{\sigma, c_d} & = \frac{1}{d!} \sum_{ \lambda \vdash d } \chi^\lambda(\sigma) \chi^\lambda(c_d) \\ & = \frac{1}{d!} \sum_{ \lambda \in \mathrm{Hooks}(d) } (-1)^{\ell(\lambda) + 1} \dim(\lambda) \frac{\chi^\lambda(\sigma) }{\dim(\lambda)} \end{align*} Defining the normalised character by \begin{align*}% \widehat{\chi}^\lambda := \frac{\chi^\lambda }{\dim(\lambda)} = \frac{\chi^\lambda }{ \chi^\lambda(id_d) } \end{align*} we then use the following (fundamental) formula that links content alphabets with Jucys-Murphy elements : for all symmetric function $F$ in $d$ variables, for all $\lambda \vdash d$ \begin{align*}%\widehat{\chi}^\lambda( F(J_1, \dots, J_d) ) = F(\mathcal{A}^\lambda) \end{align*} where \mathcal{A}^\lambda $is the$\textit{content alphabet}defined by \begin{align*}% \mathcal{A}^\lambda = \{ c(\square), \square \in \lambda \} \end{align*} My personal reference for this machinery is some articles of Biane (a priori probability theory...), but the people on this forum certainly know some better (more recent) exposition.

Using this and the fact that we have extended characters by linearity in the group algebra, i.e. $\chi^\lambda(f) = \sum_{\sigma \in \mathfrak{S}_d} f_\sigma \chi^\lambda(\sigma)$ for $f$ previously defined, one gets \begin{align*}%[c_d]f & = \sum_{\sigma \in \mathfrak{S}_d} f_\sigma \delta_{\sigma, c_d} \\ & = \sum_{\sigma \in \mathfrak{S}_d} f_\sigma \frac{1}{d!} \sum_{ \lambda \vdash d } \chi^\lambda(\sigma) \chi^\lambda(c_d) \\ & = \frac{1}{d!} \sum_{ \lambda \vdash d } \chi^\lambda(f) \chi^\lambda(c_d) \\ & = \frac{1}{d!} \sum_{ \lambda \in \mathrm{Hooks}(d) } (-1)^{\ell(\lambda) + 1} \dim(\lambda) \widehat{\chi}^\lambda(f) \end{align*} The lemma is thus proven for the following particular element of the (centre of the) symmetric group algebra \begin{align*}% F_{x, y}(J_1, \dots, J_d) := \prod_{k = 1}^d (x + J_k)(y + J_k) \end{align*} $\square$



Now, to come back to your initial problem, we use the following Jucys-Murphy identity (or chinese restaurant theorem for the Ewens measure in probability theory) \begin{align*}%\prod_{k = 1}^d (x + J_k) = \sum_{\sigma \in \mathfrak{S}_d} x^{C(\sigma)}\sigma \end{align*} with C(\sigma) $the total number of cycles of$ \sigma . Taking the product in the group algebra, namely, the convolution product, one gets \begin{align*}% \prod_{k = 1}^d (x + J_k)(y + J_k) & = \sum_{\sigma \in \mathfrak{S}_d} x^{C(\sigma)}\sigma \sum_{\tau \in \mathfrak{S}_d} y^{C(\tau)}\tau \\ & = \sum_{\sigma \in \mathfrak{S}_d} \left( \sum_{ \tau \in \mathfrak{S}_d } x^{ C(\tau) } y^{C(\sigma\tau^{-1})} \right) \sigma \end{align*}

Taking the coefficient $[c_d]$, we thus have \begin{align*}%[c_d]\prod_{k = 1}^d (x + J_k)(y + J_k) = \sum_{ \tau \in \mathfrak{S}_d } x^{ C(\tau) } y^{C(c_d\tau^{-1})} \end{align*} You are concerned with the case x = y , which gives \begin{align*}% \frac{1}{d!} \sum_{\lambda\in \text{Hooks}(d)} (-1)^{\ell(\lambda)-1} \, \dim \lambda \prod_{\Box \in \lambda}(x + c(\Box) )^2 = \sum_{ \sigma \in \mathfrak{S}_d } x^{ C(\sigma) + C(c_d^{-1}\sigma) } \end{align*}

If you want the coefficients of your polynomial, you get \begin{align*}%\sum_{ \sigma \in \mathfrak{S}_d } x^{ C(\sigma) + C(c_d^{-1}\sigma) } = \sum_{k = 2}^{2d} a_{k, d} x^k, \qquad a_{k, d} := \#\{ \sigma \in \mathfrak{S}_d \, / \, C(\sigma) + C(c_d^{-1}\sigma) = k \} \end{align*} I personally doubt that this is simple to express. Maybe with some Hurwitz numbers or some free probability (the set defining a_{d + 1, d} $defines the non-crossing permutations). You can try your recurrence relation with this new expression. • There are already some nice applications of the Jucys-Murphy elements on this forum, for instance : mathoverflow.net/questions/157577/… The answer to this question proves in fact that$ \chi^\lambda_{(d)} = (-1)^{\ell(\lambda) + 1} \mathbb{1}_{ \{ \lambda \in \mathrm{Hooks}(d) \} } $due to$ p_\mu = \sum_{\lambda \vdash |\mu|} \chi^\lambda_\mu s_\lambda $for$ \mu = (d)$. Aug 25, 2017 at 0:51 • Thanks a lot for the answer. I guess you are answering the question about the post mathoverflow.net/questions/278621/hook-content-polynomial-2 – GGT Aug 25, 2017 at 4:48 • Sure I will try to put that in the programme don't know how. I use maple. – GGT Aug 25, 2017 at 4:49 • I haven't checked properly but with the form of$B(d)= \sum_{k = 2}^{2d} a_{k, d} x^k$may be showing that it's generating function$G(y)=\sum B(d)y^d$is rational looks hopeful. – GGT Aug 25, 2017 at 4:56 • Ah, yes, the two questions are indeed closely related. Your intuition on the previous question was right, there is a link with the identity$ \sum_{\sigma \in \mathfrak{S}_d} x^{C(\sigma)} = \sum_\lambda \dim(\lambda) \prod_{\square \in \lambda} (x + c(\square) ) = x(x + 1)\cdots (x + d - 1) $. For the generating function, I have not tried (I would rather try to find the recurrence directly, with the structure of permutations between$ \mathfrak{S}_d $and$ \mathfrak{S}_{d-1} $in the same way you prove$ \sum_{\sigma \in \mathfrak{S}_d} x^{C(\sigma)} = x(x + 1)\cdots (x + d - 1) \$). Aug 25, 2017 at 9:18