Integral Representations of Catalan and Related Numbers

K.A.Penson J.-M. Sixdeniers

Université Pierre et Marie Curie Laboratoire de Physique Théorique des Liquides Tour 16, 5^{ième} étage, 4, place Jussieu, 75252 Paris Cedex 05, France

Email addresses: penson@lptl.jussieu.fr and sixdeniers@lptl.jussieu.fr

Abstract

We derive integral representations for the Catalan numbers C(n), shifted Catalan numbers C(n + p), and the numbers n! · C(n) and C(n) · B(n), where B(n) are the Bell numbers, for n = 0, 1 . . .. Our method is to use inverse Mellin transform. All these numbers are power moments of positive functions, and their representations turn out to be unique.

The Catalan numbers C(n), n = 0, 1, 2, …, defined by

C(n) = \frac{( \begin{matrix}2n \\ n \end{matrix} )}{n + 1}  ,  (1)

are among the most ubiquitous sequences in enumerative combinatorics. Stanley [13] cites no less than 66 different combinatorial settings where these numbers appear. The first few Catalan numbers are

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

for n = 0 … 9. A plethora of information about the C(n)’s can be found in [11], under sequence no. A000108.

In this note we derive an integral representation of C(n) as the n-th power moment of a certain nonnegative function W_{C}(x) on the positive half-axis. We also study the ramifications of this representation for other integer sequences involving C(n).

To this end we seek a function W_{C}(x) such that

∫_{0}^{∞} x^{n}W_{C}(x)dx = C(n)  (2)

= \frac{4^{n}Γ(n + 1/2)}{\sqrt{π}Γ(n + 2)}  ,  n = 0, 1, ….  (3)

Replacing n by a complex variable s − 1, we rewrite Eq.(3) as

∫_{0}^{∞} x^{s−1}W_{C}(x)dx = \frac{4^{s−1}Γ(s − 1/2)}{\sqrt{π}Γ(s + 1)} , Re s > 1 ,  (4)

which implies that

W_{C}(x) = M^{−1} [\frac{4^{s−1}Γ(s − 1/2)}{\sqrt{π}Γ(s + 1)}; x] ,  (5)

where M^{−1} [f^{∗}(s); x] = f(x) is the inverse Mellin transform [12], with f^{∗}(s) = M [f(x); s] = ∫_{0}^{∞} x^{s−1}f(x)dx the Mellin transform of f(x). We note the following property of M [12] :

M [x^{b}f(ax^{h}); s] = \frac{1}{h}a^{− \frac{s+b}{h}} f^{∗} (\frac{s + b}{h}) ,  b ∈ R, h > 0,  (6)

which, when specialized to a = \frac{1}{4}, b = −\frac{1}{2} and h = 1, implies that

M [x^{− \frac{1}{2}} f (\frac{x}{4}); s] = 4^{s}f^{∗}(s − 1/2)/2 .  (7)

Adopting the standard notation (y)_{+}^{α} = y^{α} if y > 0, (y)_{+}^{α} = 0 otherwise, and using the formula 2.2(1), p.151 of [5] :

M [(1 − x)_{+}^{α−1}; s] = Γ(α)\frac{Γ(s)}{Γ(α + s)} ,  α > 0, s > 0,  (8)

we can apply Eq.(7) with f(x) = (1 − x)_{+}^{α−1} and α = \frac{3}{2}. This yields

W_{C}(x) = \frac{x^{− \frac{1}{2}}}{π} (1 − \frac{x}{4})+^{\frac{1}{2}} .  (9)

The function W_{C}(x) is displayed on Fig.(1). The desired integral representation of C(n) is then

C(n) = ∫_{0}^{4} x^{n} (\frac{\sqrt{\frac{4−x}{x}}}{2π} ) dx .  (10)

This is the solution of the Hausdorff moment problem on [0, 4], which is always unique [1], and so the representation of Eq.(10) is also unique.

By the same token we can find the solution of

∫_{0}^{∞} x^{n}W_{C,p}(x)dx = C(n + p), n = 0, 1, 2 …, p = 1, 2, …,  (11)

i.e. the unique representation of the shifted Catalan numbers C(n + p), as the Hausdorff moments of

W_{C,p}(x) = \frac{x^{p− \frac{1}{2}}}{π} (1 − \frac{x}{4})+^{\frac{1}{2}} .  (12)

The Mellin convolution property for products of Mellin transforms, in its simplest incarnation, states ([12], [5]) that if M [W_{1,2}(x); s] = ρ_{1,2}(s) then

M^{−1} [ρ_{1}(s)ρ_{2}(s); x] = W_{12}(x) ≡ ∫_{0}^{∞} \frac{1}{t}W_{1} (\frac{x}{t}) W_{2}(t)dt .  (13)

Observe that W_{1,2}(x) > 0 implies W_{12}(x) > 0.

Figure 1: : The function W_{C}(x), s. Eq.(9). This function diverges at x = 0.

As an application of Eq.(13) we look for an integral representation of the sequence n! · C(n) whose initial terms are 1, 1, 4, 30, 336, 5040, 95040, 2162160, 57657600, 1764322560, for n = 0 … 9; compare [11], no. A001761. Using Eq.(9) and performing the Mellin convolution in Eq.(13) with W_{1}(x) = e^{−x} and W_{2}(x) = W_{C}(x), one ends up with the following Stieltjes moment problem :

∫_{0}^{∞} x^{n}W_{1C}(x)dx = n! · C(n) = \frac{(2n)!}{(n + 1)!} , n = 0, 1, …,  (14)

with the solution

W_{1C}(x) = \frac{1}{2π\sqrt{x}} ∫ ∞_{\frac{x}{4}} e^{−t} \frac{\sqrt{4t − x}}{t}dt  (15)
= −\frac{1}{2} + \frac{1}{\sqrt{πx}}e^{− \frac{x}{4}} + \frac{1}{2}erf (\frac{\sqrt{x}}{2}) ,  (16)

where erf(y) is the error function. The function W_{1C}(x) is shown in Fig.(2). As W_{1C}(x) > 0, the (sufficient) Carleman condition (∑_{n=1}^{∞}(\frac{(2n)!}{(n+1)!})^{− \frac{1}{2n}} = ∞) (cf. Ref.[1]) indicates that the solution W_{1C}(x) of Eq.(16) is also unique. Similar results are obtained by using W_{C,p}(x) instead of W_{C}(x) in Eq.(13).

Another use of Eq.(13) is illustrated by considering the sequence C(n) · B(n), where B(n) are the Bell numbers ( see [11], no. A000110, and [2] ). The initial terms of this sequence are 1, 1, 4, 25, 210, 2184, 26796, 376233, 5920200, 102816714, for n = 0 … 9. For this last sequence see [11], no. A064299. The weight function whose n-th moment is equal to B(n) is

W_{B}(x) = \frac{1}{e} ∑_{k=1}^{∞} \frac{δ(x − k)}{k!}  ,  (17)

which is a consequence of Dobiński formula, B(n) = \frac{1}{e} ∑_{k=1}^{∞} \frac{k^{n}}{k!} , see [2]. In Eq.(17), δ(y) is Dirac’s delta function. By Mellin convolution of W_{B}(x) with W_{C}(x) one obtains

W_{BC}(x) = \frac{1}{2πe} ∑_{k=1}^{∞} \frac{1}{kk!}\sqrt{\frac{4k − x}{x}}H (4 − \frac{x}{k})  ,  (18)

Figure 2: : The function W_{1C}(x), s. Eq.(16). This function diverges at x = 0.

which, via Carleman’s criterion, is the only positive function such that its n-th moment is equal to C(n)·B(n). In Eq.(18) H(y) is the Heaviside function. The function W_{BC}(x) is displayed on Fig.(3).

Figure 3: : The function W_{BC}(x), s. Eq.(18). This function diverges at x = 0.

The last sequence that will concern us here is (n!)^{2}C(n) = \frac{(2n)!}{n+1}. Its initial terms are

1, 1, 8, 180, 8064, 604800, 68428800, 10897286400, 2324754432000

for n = 0 … 9; compare [11], no. A060593. Proceeding as in Eqs.(3) and (4), we are looking for W_{3}(x) satisfying

∫_{0}^{∞} x^{s−1}W_{3}(x)dx = \frac{4^{s−1}Γ(s − 1/2)Γ^{2}(s)}{\sqrt{π}Γ(s + 1)}  , Re s > 1 .  (19)

It appears that when studying Eq.(19) it is possible to avoid using W_{C}(x). As the first step we observe from

Figure 4: : The function W_{3}(x), s. Eq.(24). This function diverges at x = 0.

Eq.(6) that

M^{−1} [Γ (s − \frac{1}{2}); x] = \frac{e^{−x}}{\sqrt{x}}  .  (20)

In addition, the following relation holds :

M^{−1} [\frac{Γ^{2}(s)}{Γ(s + 1)}; x] = −Ei(−x)  ,  (21)

which is the formula 8.1(1), p.182 of [5]. In Eq.(21) Ei(y) is the exponential integral function. Combining Eqs.(20) and (21) in the Mellin convolution we obtain

M^{−1} [\frac{Γ(s − 1/2)Γ^{2}(s)}{Γ(s + 1)}; x] = −\frac{1}{\sqrt{x}} ∫_{0}^{∞} t^{− \frac{1}{2}} t^{− \frac{x}{t}} Ei(−t)dt  (22)
= 2\sqrt{\frac{π}{x}} e^{−2\sqrt{x}} + 4\sqrt{π}Ei(−2\sqrt{x})  , x > 0 .  (23)

In writing Eq.(23) we have used the formula 2.5.4.2, p.72 of [6]. Finally, we use Eq.(6) again (with a = \frac{1}{4}, b = 0 and h = 1) and from Eq.(19) we get the solution

W_{3}(x) = \frac{1}{\sqrt{x}}e^{−\sqrt{x}} + Ei(−\sqrt{x})  ,  (24)

which is plotted in Fig.(4). As W_{3}(x) > 0, by Carleman’s criterion the solution is again unique.

Remark: E. P.Wigner [14] has demonstrated that Eq.(10), under a suitable parametrization, describes the distribution function of eigenvalues of an ensemble of random, symmetric, real matrices.

Integral representations of other combinatorial numbers can be found in [3]. For further applications of Mellin convolution formula Eq.(13), one may consult [5], [10], [7], [8] , [4] and [9].

References

[1] N. I. Akhiezer, The Classical Moment Problem and Some Related Questions in Analysis, (Oliver and Boyd, London, 1965)

[2] L. Comtet, Advanced Combinatorics, (D. Reidel, Boston, 1984)

[3] G. P. Egorychev, Integral Representation and the Computation of Combinatorial Sums, Translations of Mathematical Monographs, Vol. 59, (American Mathematical Society, Rhode Island, 1984)

[4] J. R. Klauder, K. A. Penson and J. M. Sixdeniers, Constructing coherent states through solutions of Stieltjes and Hausdorff moment problems, Phys. Rev. A64, 013817 (2001)

[5] O. I. Marichev, Handbook of Integral Transforms of Higher Transcendental Functions, Theory and Algorithmic Tables, (Ellis Horwood Ltd, Chichester, 1983)

[6] A. P. Prudnikov, Yu. A. Brychkov and O. I. Marichev, Integrals and Series, vol. 2: Special Functions, (Gordon and Breach, New York, 1998)

[7] J. M. Sixdeniers and K. A. Penson, On the completeness of coherent states generated by binomial distribution, J. Phys. A33, 2907 (2000)

[8] J. M. Sixdeniers and K. A. Penson, On the completeness of photon-added coherent states, J. Phys. A34, 2859 (2001)

[9] J. M. Sixdeniers, K. A. Penson and J. R. Klauder, Tricomi coherent states, Int. J. Mod. Phys. B 15, 4231 (2001)

[10] J. M. Sixdeniers, K. A. Penson and A. I. Solomon, Mittag-Leffler coherent states, J. Phys. A32, 7543 (1999)

[11] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, published electronically at: http://www.research.att.com/∼/njas/sequences/

[12] I. N. Sneddon, The Use of Integral Transforms, (McGraw-Hill, New York, 1974)

[13] R. P. Stanley, Enumerative Combinatorics, Vol. 2, (Cambridge University Press, 1999)

[14] E. P. Wigner, Characteristic vectors of bordered matrices with infinite dimensions, Ann.Math.62, 548 (1955)

(Concerned with sequences A000108, A000110, A001761, A060593, A064299.)

Received Sep 7, 2001; revised version received Oct 29, 2001. Published in Journal of Integer Sequences, Feb 7, 2002.

Return to Journal of Integer Sequences home page.