Convolution of Narayana polynomials

197 Views Asked by At

I would like to find a reference for the following result:

Let $C_n(t)=\sum\limits_{k = 0}^{n-1} {\binom{n-1}{k}\binom{n+1}{k+1}\frac{1}{n+1}t^k}$ for $n>0$ and $C_0(t)=1$ be Narayana polynomials. Then the $m-$fold convolution $C^{(m)}_n(t)$ is given by $C^{(m)}_n(t)=\sum\limits_{k = 0}^{n-1} {\binom{n-1}{k}\binom{n+m}{k+m}\frac{m}{n+m}t^k}$ for $n>0.$

Edit: I In the mean time I have seen that this convolution identity follows rather trivially from the generating function $C(t,z)=\sum{ C_n(t) z^n}$, which satisfies $tzC(t,z)^2=C(t,z)-1-zC(t,z)+tzC(t,z)$. It suffices to multiply this identity with $C(t,z)^{m-2}$ and compare coefficients.

Nevertheless I would be interested if the above identity occurs in the literature.

1

There are 1 best solutions below

1
On BEST ANSWER

Suppose we define

$$C_0^{(1)}(t) = 1 \quad\text{and}\quad C_n^{(1)}(t) = \sum_{k=0}^{n-1} {n-1\choose k} {n+1\choose k+1} \frac{1}{n+1} t^k$$

and let for $m\ge 2$

$$C_n^{(m)}(t) = \sum_{q=0}^n C_q^{(m-1)}(t) C_{n-q}^{(1)}(t).$$

This definition is equivalent to introducing

$$G(w) = \sum_{n\ge 1} C_n^{(1)}(t) w^n$$ and letting

$$C_n^{(m)}(t) = [w^n] (1+G(w))^m = [w^n] \sum_{p=0}^m {m\choose p} G(w)^p.$$

We seek to show that

$$C_0^{(m)}(t) = 1 \quad\text{and}\quad C_n^{(m)}(t) = \sum_{k=0}^{n-1} {n-1\choose k} {n+m\choose k+m} \frac{m}{n+m} t^k.$$

The proof will consist in doing a coefficient extraction operation from the powers of $G(w)$ and showing that these match the proposed formula. We require an alternate representation of $C_n^{(1)}(t)$ and observe that

$${n-1\choose k} {n+1\choose k+1} \frac{1}{n+1} = {n\choose k+1} \frac{k+1}{n} {n\choose k} \frac{n+1}{k+1} \frac{1}{n+1} \\ = \frac{1}{n} {n\choose k+1} {n\choose k}.$$

and introduce

$${n\choose k+1} = {n\choose n-k-1} = \frac{1}{2\pi i} \int_{|z|=1} \frac{1}{z^{n-k}} (1+z)^{n} \; dz$$

which conveniently vanishes for $k\ge n.$ We get for $n\ge 1$

$$C_n^{(1)}(t) = \frac{1}{n} \frac{1}{2\pi i} \int_{|z|=1} \frac{1}{z^{n}} (1+z)^{n} \sum_{k\ge 0} {n\choose k} z^k t^k \; dz \\ = \frac{1}{n} \frac{1}{2\pi i} \int_{|z|=1} \frac{1}{z^{n}} (1+z)^{n} (1+tz)^{n} \; dz.$$

We re-write this as

$$\frac{1}{n} \frac{1}{2\pi i} \int_{|z|=1} \frac{1}{z^{n}} (1+z(1+t+tz))^{n} \; dz.$$

Extracting the coefficient yields

$$\frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} [z^{n-1-q}] (1+t+tz)^{q} \\ = \frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} {q\choose n-1-q} (1+t)^{q-(n-1-q)} t^{n-1-q} \\ = \frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} {q\choose n-1-q} (1+t)^{2q+1-n} t^{n-1-q} \\ = \frac{1}{n} \sum_{q=0}^{n-1} {n\choose n-1-q} {n-1-q\choose q} (1+t)^{n-1-2q} t^{q}.$$

Now we have

$$\frac{1}{n} {n\choose n-1-q}{n-1-q\choose q} = \frac{1}{n} \frac{n!}{(q+1)! q! (n-1-2q)!} \\ = \frac{1}{n} {2q+1\choose q} {n\choose 2q+1} = \frac{1}{2q+1} {2q+1\choose q} {n-1\choose 2q} \\ = \frac{1}{2q+1} {2q+1\choose q+1} {n-1\choose 2q} = \frac{1}{q+1} {2q\choose q} {n-1\choose 2q}$$

where $$C_q = \frac{1}{q+1} {2q\choose q}$$

is a Catalan number. We thus obtain for $G(w)$

$$\sum_{n\ge 1} w^n \sum_{q=0}^{n-1} C_q {n-1\choose 2q} (1+t)^{n-1-2q} t^q \\ = w \sum_{n\ge 0} w^n \sum_{q=0}^{n} C_q {n\choose 2q} (1+t)^{n-2q} t^q \\ = w \sum_{q\ge 0} C_q (1+t)^{-2q} t^q \sum_{n\ge q} {n\choose 2q} w^n (1+t)^n \\ = w \sum_{q\ge 0} C_q (1+t)^{-2q} t^q \sum_{n\ge 2q} {n\choose 2q} w^n (1+t)^n \\ = w \sum_{q\ge 0} C_q (1+t)^{-2q} t^q w^{2q} (1+t)^{2q} \sum_{n\ge 0} {n+2q\choose 2q} w^n (1+t)^n \\ = w \sum_{q\ge 0} C_q t^q w^{2q} \frac{1}{(1-w(1+t))^{2q+1}} \\ = \frac{w}{(1-w(1+t))} \sum_{q\ge 0} C_q t^q w^{2q} \frac{1}{(1-w(1+t))^{2q}}.$$

Now the classic generating function of the Catalan numbers is

$$Q(x) = \frac{1-\sqrt{1-4x}}{2x}.$$

We have computed the closed form of $G(w)$ which is

$$G(w) = \frac{w}{(1-w(1+t))} \frac{1-\sqrt{1-4tw^2/(1-w(1+t))^2}}{2tw^2/(1-w(1+t))^2} \\ = w \frac{1-\sqrt{1-4tw^2/(1-w(1+t))^2}}{2tw^2/(1-w(1+t))} \\ = w \frac{1-w(1+t)-\sqrt{(1-w(1+t))^2-4tw^2}}{2tw^2} \\ = \frac{1-w(1+t)-\sqrt{(1-w(1+t))^2-4tw^2}}{2tw}.$$

Recall the functional equation of the Catalan number generating function which is

$$Q(x) = 1 + x Q(x)^2.$$

We thus obtain

$$Q\left(\frac{tw^2}{(1-w(1+t))^2}\right) = 1 + \frac{tw^2}{(1-w(1+t))^2} Q\left(\frac{tw^2}{(1-w(1+t))^2}\right)^2$$

or

$$\frac{1-w(1+t)}{w} G(w) = 1 + t G(w)^2.$$

Solving for $w$ we get

$$G(w) - w(1+t) G(w) = w(1+tG(w)^2)$$

or $$G(w) = w(1+(1+t)G(w)+tG(w)^2)$$

which is

$$w = \frac{G(w)}{1+(1+t)G(w)+tG(w)^2}.$$

Recall that we seek $$[t^k] \sum_{p=0}^m {m\choose p} [w^n] G(w)^p.$$

We establish the coefficient extraction integral (Lagrange inversion)

$$[w^n] G(w)^p = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{n+1}} G(w)^p \; dw.$$

Setting $v=G(w)$ and observing that $w=0$ is mapped to $v=0$ we get

$$\frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+(1+t)v+tv^2)^{n+1}}{v^{n+1}} \\ \times v^p \times \left(\frac{1}{1+(1+t)v+tv^2} - \frac{v(1+t+2tv)}{(1+(1+t)v+tv^2)^2}\right) \; dv.$$

This is

$$\frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+(1+t)v+tv^2)^{n-1}}{v^{n-p+1}} (1+(1+t)v+tv^2-v(1+t+2tv)) \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n-1} (1+tv)^{n-1}}{v^{n-p+1}} (1-tv^2) \; dv.$$

Now substituting this into the target formula yields

$$C_n^{(m)}(t) = \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n-1} (1+tv)^{n-1}}{v^{n+1}} (1-tv^2) \sum_{p=0}^m {m\choose p} v^p \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n+m-1} (1+tv)^{n-1}}{v^{n+1}} (1-tv^2)\; dv.$$

To conclude the proof we must treat the case of $n=0$ which is different from the case $n\ge 1$ and extract coefficients on $[t^k]$ in the latter case. With $n=0$ we get

$$\frac{1}{2\pi i} \int_{|v|=\gamma} (1+v)^{m-1} \frac{1}{v} \frac{1}{1+tv} (1-tv^2)\; dv.$$

This is the constant coefficient and is equal to

$$\left.(1+v)^{m-1} \frac{1}{1+tv} (1-tv^2)\right|_{v=0} = 1,$$

as required. For the case of $n\ge 1$ we have two subcases, $k=0$ and $k\ge 1.$ For $k=0$ the second term in $1-tv^2$ does not contribute and we have just

$$\frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n+m-1}}{v^{n+1}} \; dv \\ = {n+m-1\choose n} = {n+m-1\choose m-1} = {n+m\choose m} \frac{m}{n+m}.$$

This is again the required value. Finally when $n\ge 1$ and $k\ge 1$ we get two pieces, namely

$${n-1\choose k}\frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n+m-1}}{v^{n-k+1}} \; dv = {n-1\choose k} {n+m-1\choose n-k}$$

and

$$-{n-1\choose k-1} \frac{1}{2\pi i} \int_{|v|=\gamma} \frac{(1+v)^{n+m-1}}{v^{n-k}} \; dv = -{n-1\choose k-1} {n+m-1\choose n-k-1}.$$

Note that when $k=n$ the first of these integrals never appears in the first place because $[t^k] (1+tv)^{n-1} = 0$ and the second vanishes due to the residue. When $k\gt n$ we have $[t^k] (1+tv)^{n-1} (1-tv^2) = 0$ and everything vanishes. This is the required behavior. We get for the non-zero cases

$${n-1\choose k} {n+m-1\choose k+m-1} - {n-1\choose k-1} {n+m-1\choose k+m} \\ = {n-1\choose k} {n+m\choose k+m} \frac{k+m}{n+m} - {n-1\choose k} \frac{k}{n-k} {n+m\choose k+m} \frac{n-k}{n+m} \\ = {n-1\choose k} {n+m\choose k+m} \frac{m}{n+m}.$$

We have the required value as was to be shown and may end the computation.