8

2

The Catalan numbers are the moments of the Wigner semicircle distribution.
$$ \frac{1}{2\pi} \int_{-2}^2 x^{2n} \sqrt{4 - x^2} dx = \frac{1}{n+1} \binom{2n}{n} $$ Motzkin numbers enumerate the number of paths from (0,0) to (0,n) in steps of (1,1),(1,-1),(1,0) remaining above the x-axis.

For this particular sequence of numbers 1, 1, 2, 4, 9, 21, 51, 127... satisfying the recursion $$ M_n = \frac{3(n-1)M_{n-2} +(2n+1)M_{n-1}}{n+2} $$ Is it possible to reconstruct a measure $\rho(x)$ whose moments $\langle x^n \rangle$ follow that sequence?

flag
mathworld.wolfram.com/CharacteristicFunction.html – Steve Huntsman Sep 10 2011 at 1:53
Yeah, I think you just take the Laplace transform of the generating function of the moments. $M(t)=m_0+m_1t+m_2 t^2/2+\dots$ then $ρ(x)=\int_0^\infty e^{-xt} M(t) \, dt$. – John Mangual 0 secs ago – John Mangual Sep 10 2011 at 2:09
I think that the left-hand side of the formula for the Catalan numbers should be multiplied by 4^n. – Johann Cigler Sep 10 2011 at 9:23
I agree with Johann. Alternatively, the $n$th Catalan number is ${1 \over 2\Pi} \int_{-2}^2 x^{2n} \sqrt{4-x^2} \: dx$ -- that is, make the semicircle bigger. – Michael Lugo Sep 10 2011 at 16:31
@Steve, the Laplace transform might not work on an interval like [-2,2]. I guess whichever interval we use should return rescaled and translated semicircles. – John Mangual Sep 11 2011 at 2:11

2 Answers

16

Motzkin numbers are a very popular sequence. A lot of identities and formulas are already recorded at OEIS. The analogous integral representation for Motzkin numbers is $$M_n=\frac{1}{2\pi} \int_{-1}^3 x^n\sqrt{(3-x)(1+x)}dx.$$

A few words about the general picture. There is a well known combinatorial theory of orthogonal polynomials and continued fraction which is closely related to Motzkin paths.

By Favard's theorem we know that a sequence of polynomials is a system of orthogonal polynomials with respect to some measure if and only if they satisfy a recurrence for all $n$ $$P_n=(x-a_n)P_{n-1}-b_nP_{n-2}$$ Now the generating functions of moments $\sum \mu_ix^i$ when written as a continued fraction tells us the coefficients $a_n,b_n$ and therefore the sequence of orthogonal polynomials. One can also interpret these continued fractions as generating functions for weighted Motzkin paths. This is a theorem of Viennot

The moments of a sequence of orthogonal polynomials are sums of Motzkin paths of length $n$ where horizontal steps at height $k$ are weighted by $a_k$ and down steps at height $k$ are weighted by $b_k$.

As a special case the numbers $M_n$ appear as moments of the sequence of polynomials which satisfies $P_n=(x-1)P_{n-1}-P_{n-2}$ which are shifted and scaled Chebyshev polynomials of second kind, and the identity above holds. However one can give such a combinatorial context to most known families of orthogonal polynomials.

For the relation between orthogonal polynomials and continued fractions, I would recommend "Orthogonal polynomials and random matrices: a Riemann-Hilbert approach" by P. Deift, it is short and a very enjoyable read. For the combinatorial theory see for example "Combinatorial aspects of continued fractions" by P. Flajolet or Viennot's works on orthogonal polynomials which you can find here.

link|flag
1 
 An integral from $-1$ to $3$. Cute :) – Mariano Suárez-Alvarez Sep 10 2011 at 3:25
stunning. it is also a semicircle. – John Mangual Sep 10 2011 at 15:26
@Gjergji: You are of course right. But the question is how to find the measure whose moments coincide with the given sequence. For $a_n = c$ and $b_n = d^2 $ the moment generating function is the function $f(z)$ of my answer and the corresponding orthogonal polynomials are the Fibonacci polynomials $F_{n + 1} (x - c, - d^2 )$ (cf. e.g. Section 2 of my paper arXiv:1109.1449 ). From this fact and the known measure for the Catalan numbers the formula for the measure immediately follows. – Johann Cigler Sep 12 2011 at 7:07
@Johann: I don't think I'm contradicting your claim. I pointed out that one can easily obtain the orthogonal polynomials from the moments and from there one needs to be lucky and recognise the polynomial family (we are lucky here since we get the fibonacci polynomials) and obtain the measure. In more generality one can encounter other orthogonal polynomials for other appropriate sequences of moments. However in the most general case one needs to solve the moment problem which is a bit more delicate and goes a bit beyond the combinatorics involved here. – Gjergji Zaimi Sep 12 2011 at 7:50
$[-1,3]$ is the interval where the trace of an element of $SO_3(\mathbb R)$ is. I wonder what the connection is... – Mariano Suárez-Alvarez Sep 14 2011 at 6:33
10

The formula for the measure of the Motzkin numbers as stated by Gjergij follows from the formula for the Catalan numbers if we write the formula for the Catalan numbers in the form $\frac{1}{{2\pi }}\int_{ - 2}^2 {x^{2n} \sqrt {4 - x^2 } } dx = C_n $ and observe that the corresponding orthogonal polynomials are the Fibonacci polynomials $F_{n + 1} (x, - 1)$ defined by $F_n (x, - 1) = xF_{n - 1} (x, - 1) - F_{n - 2} (x, - 1)$ with initial values $F_0 (x, - 1) = 0$ and $F_1 (x, - 1) = 1.$ For the Motzkin numbers the corresponding orthogonal polynomials are $F_{n + 1} (x - 1, - 1).$ Therefore a simple transformation of the integral gives the result.

Edit: More generally (as answer to the comments by Gjergji and Brendan): Let $f(z) = \sum {r(n,c,d)z^n } $ satisfy $f(z) = 1 + czf(z) + d^2 z^2 f(z)^2. $ Then $r(n,c,d) = \frac{1}{{2\pi d^2 }}\int_{c – 2d}^{c + 2d} {x^n \sqrt {4d^2 - (x - c)^2 } } dx.$

link|flag
This special case of Fibonacci polynomials are actually Chebyshev polynomials (of second kind, scaled by a factor of 2). Similar recurrences hold for $\int x^n \sqrt{(a-x)(b+x)} dx$. – Gjergji Zaimi Sep 11 2011 at 1:48
For integer $a,b$, it seems that the moments are all integer iff $b-a$ is divisible by 4. I wonder if any other standard sequences are included. – Brendan McKay Sep 11 2011 at 4:42

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.