A Generating Function for the Diagonal T_{2n,n} in Triangles

Dmitry V. Kruchinin

Tomsk State University of Control Systems and Radioelectronics

and National Research Tomsk Polytechnic University Tomsk Russian Federation

                KruchininDm@gmail.com

Vladimir V. Kruchinin

Tomsk State University of Control Systems and Radioelectronics

Tomsk Russian Federation

                   kru@2i.tusur.ru

Abstract

We present techniques for obtaining a generating function for the diagonal T_{2n,n} of the triangle formed from the coefficients of a generating function G(x) raised to the power k. We obtain some relations between central coefficients and coefficients of the diagonal T_{2n,n}, and we also give some examples.

1 Introduction

A triangle is a classic object of research in combinatorics. For instance, the Pascal triangle, the Bernoulli-Euler triangle, the Catalan triangle, and the Motzkin triangle are discussed in many papers and books [3, 10, 7].

Let G(x) be an ordinary power series without a constant term, i.e., G(x) = ∑_{n>0} g_{n} x^{n},

where g_{0} = 0 and g_{1} ≠ 0. In this paper we deal with the triangle T_{n,k} defined as follows:

[G(x)]^{k} = ∑_{n≥k} T_{n,k}x^{n}.

Here we assume that G(x)^{0} = T_{0,0} = 1.

Then the generating function G(x) raised to the power k gives the following triangle T_{n,k}

T_{1,1}
T_{2,1}  T_{2,2}
T_{3,1}  T_{3,2}  T_{3,3}
T_{4,1}  T_{4,2}  T_{4,3}  T_{4,4}
⋮  ⋮  ⋮  ⋮  ⋮
T_{n,1} T_{n,2}  …  …  T_{n,n−1} T_{n,n}

The following notation will be used throughout this paper. The authors [4, 5] introduced the notion of the composita of a given ordinary generating function G(x) = ∑_{n>0} g(n)x^{n}.

Definition 1. The composita is the function of two variables defined by

G^{Δ}(n, k) = ∑_{π_{k}∈C_{n}} g(λ_{1})g(λ_{2}) ⋯ g(λ_{k}),  (1)

where n, k,λ_{i} are integers that are greater than 0, C_{n} is the set of all compositions of n, and π_{k} is the composition into k parts exactly (∑_{i=1}^{k} λ_{i} = n).

The generating function of the composita is equal to

[G(x)]^{k} = ∑_{n⩾k} G^{Δ}(n, k)x^{n} = ∑_{n≥k} T_{n,k}x^{n}.  (2)

This notation coincides with the concept of Riordan array (1, G(x)) or (\frac{G(x)}{x}, G(x)), which was given by Shapiro, Getu, Woan, and Woodson [8].

Recently, in [6], we have shown how to find a generating function of the central elements of such triangles

C(x) = ∑_{n>0} T_{2n−1,n}x^{n−1} = F′(x),  (3)

where F (x) is the solution of the equation

F (x) = xS(F (x))  (4)

and

x S(x) = G(x).

For solving (4), one uses the Lagrange inversion formula (LIF), which was proved by Stanley [10]. In [6], we applied the LIF for the generating functions raised to the k power:

[G(x)]^{k} = ∑_{n≥k} G^{Δ}(n, k) x^{n}

and

[F (x)]^{k} = ∑_{n≥k} F^{Δ}(n, k) x^{n}.

We obtained the following relation between two triangles:

F^{Δ}(n, k) = \frac{k}{n}T_{2n−k,n}.

In this paper we present a method for obtaining the generating function for the diagonal T_{2n,n} of a triangle T_{n,k}. The triangle is given by the following expression

[G(x)]^{k} = ∑_{n≥k} T_{n,k} x^{n}.

2 Main results

The main result of this paper is given in the following theorem.

Theorem 2. Suppose we have the generating function G(x) = ∑_{n>0} g_{n} x^{n} that forms a triangle

T_{n,k}:

[G(x)]^{k} = ∑_{n≥k} T_{n,k}x^{n}.

Then the generating function A(x) = ∑_{n≥0} T_{2n,n}x^{n} for the diagonal T_{2n,n} of the triangle is defined by

A(x) = \frac{x F′(x)}{F (x)},  (5)

where F (x) = x S(F (x)) with S(x) = \frac{G(x)}{x}.

Proof. Suppose we have the following Laurent series

Φ(z) = φ z + φ_{0} + \frac{φ_{1}}{z} + ⋯ + \frac{φ_{n}}{z^{n}} + ⋯

Then, raising this generating function to the power k, we get

[Φ(z)]^{k} = Φ_{k}(z) + E_{k}(z),

where Φ_{k}(z) contains the nonnegative powers of z and E_{k}(z) contains the remaining powers of z. According to Suetin [11], Φ_{k}(z) is the Faber polynomial.

Let us consider the generating function G(z) in terms of Φ(z). That is,

[G(z)]^{k} = [z^{2} Φ(1/z)]^{k} = ∑_{n≥k} T_{n,k} z^{n}.

Then we have

[Φ(z)]^{k} = z^{2k} ∑_{n≥k} T_{n,k} z^{−n}.

After transformation, the Faber polynomial is equal to

Φ_{n}(z) = ∑_{k=0}^{n} T_{2n−k,n} z^{k},  (6)

For the case z = 0, we have

Φ_{n}(0) = T_{2n,n}.  (7)

According to Curtiss [2] and Suetin [11], the generating function for the Faber polynomials is equal to

\frac{tϕ′(t)}{ϕ(t) − z} = ∑_{n≥0} Φ_{n}(z)t^{−n},

where ϕ(t) is the compositional inverse of Φ(t).

Then the generating function for the case z = 0 is equal to

\frac{tϕ′(t)}{ϕ(t)} = ∑_{n≥0} Φ_{n}(0)t^{−n}.

Next we set t = \frac{1}{x}. Taking into account that

(ϕ(1/x))′ = ϕ′(1/x) (1/x)′ = \frac{−ϕ′(1/x)}{x^{2}}

or

ϕ′(1/x) = −x^{2} (ϕ(1/x))′

we get the generating function for Φ_{n}(0)

A(x) = −\frac{x(ϕ(1/x))′}{ϕ(1/x)} = ∑_{n≥0} Φ_{n}(0)x^{n}.  (8)

Since ϕ(t) is the compositional inverse of Φ(t), the following identity holds:

Φ(ϕ(t)) = t.

If we substitute 1/x for t, then we obtain the following relation:

Φ(ϕ(1/x)) = 1/x.

Since

Φ(x) = x^{2}G(1/x) = xS(1/x),

we get

ϕ(1/x)S(1/ϕ(1/x)) = \frac{1}{x}.

Then

\frac{1}{ϕ(1/x)} = xS(1/ϕ(1/x)).

According to (4), we have

\frac{1}{ϕ(1/x)} = F (x)

Therefore, according to (7) and (8), the generating function for the diagonal T_{2n,n} is equal to

A(x) = −\frac{x(\frac{1}{F (x)})′}{\frac{1}{F (x)}} = \frac{x F′(x)}{F (x)} = ∑_{n≥0} T_{2n,n} x^{n}.

The theorem is thus proved.

As applications of Theorem 2, we give the following examples.

Example 3. Let us consider the Pascal triangle. This triangle can be defined by the generating function

[G(x)]^{k} = (\frac{x}{1 − x})^{k} = ∑_{n≥k} \binom{n − 1}{n − k}x^{n}

The solution of the equation

F (x) = \frac{x}{1 − F (x)}

is the generating function

F (x) = \frac{1 − \sqrt{1 − 4x}}{2}.

Therefore, the generating function for the diagonal T_{2n,n} with the general term \binom{2n−1}{n} is

A(x) = \frac{x F′(x)}{F (x)} = \frac{2x}{(1 − \sqrt{1 − 4x}) \sqrt{1 − 4x}}.

Example 4. Let us find the generating function A(x) = ∑_{n≥0} T_{2n,n}x^{n} for the triangle defined by the following generating function

G(x) = x + x^{2} + x^{3}.

Solving the equation

F (x) = x(1 + F (x) + F (x)^{2}),

we get the generating function for the Motzkin numbers (see the sequence \underline{A001006} in [9])

F (x) = \frac{−\sqrt{−3x^{2} − 2x + 1} − x + 1}{2x}.

Then we have

\frac{x F′(x)}{F (x)} = \frac{\sqrt{−3x^{2} − 2x + 1} + x − 1}{(x − 1) \sqrt{−3x^{2} − 2 x + 1} − 3x^{2} − 2x + 1}.

After transformation, we obtain

A(x) = \frac{1}{\sqrt{−3x^{2} − 2x + 1}}.

Example 5. Let us find the generating function A(x) = ∑_{n≥0} T_{2n,n}x^{n} for the triangle defined by the following expression

[G(x)]^{k} = [\frac{1 − \sqrt{1 − 4x}}{2}]^{k} = ∑_{n≥k} \frac{k \binom{2n−k−1}{n−k}}{n}x^{n}.

The solution of the functional equation (4) for this case is the following generating function (see sequence \underline{A001764} in [9])

F (x) = \frac{2}{\sqrt{3x}}sin (\frac{1}{3}arcsin (\frac{\sqrt{27x}}{2})).

Therefore, the desired generating function has the form

A(x) = \frac{xF′(x)}{F (x)} = 1 + ∑_{n>0} \frac{\binom{3n−1}{n}}{2}x^{n} = \frac{\sqrt{3x}}{2\sqrt{4 − 27x}} cot (\frac{1}{3}arcsin (\frac{\sqrt{27x}}{2})) + \frac{1}{2}.

Example 6. Let us consider the triangle defined by the expression

[G(x)]^{m} = [x^{2} cot(x)]^{m} = ∑_{n≥m} T_{n,m}x^{n},

where

T_{n,m} = (−1)^{\frac{n−m}{2}} ∑_{l=0}^{m} \frac{2^{n−2m+l}}{(n − 2m + l)!}\binom{m}{l} ∑_{k=0}^{n−2m+l} \frac{s (l + k, l) S (n − 2m + l, k)}{\binom{k+l}{l}}.

Here s(n, k) and S(n, k) stand for the Stirling numbers of the first and second kinds, respectively [1, 3].

This triangle forms the sequence \underline{A199542} in [9]. Then we have

T_{2n,n} = (−1)^{\frac{n}{2}} ∑_{l=0}^{n} 2^{l} (∑_{k=0}^{l} \frac{k! S (l, k) s (l + k, l)}{(l + k)!}) \binom{n}{l}.

For the equation F (x) = x F (x) cot(F (x)), the solution is the generating function arctan(x). Hence,

\frac{xF′(x)}{F (x)} = \frac{x}{(1 + x^{2}) arctan(x)} = 1 − \frac{2x^{2}}{3} + \frac{26x^{4}}{45} − \frac{502x^{6}}{945} + \frac{7102x^{8}}{14175} + ⋯

Therefore, we obtain

A(x) = \frac{x}{(1 + x^{2}) arctan(x)} = ∑_{n≥0} (−1)^{\frac{n}{2}} ∑_{l=0}^{n} 2^{l} (∑_{k=0}^{l} \frac{k! S (l, k) s (l + k, l)}{(l + k)!}) \binom{n}{l} x^{n}.

Next, we derive some interesting identities between coefficients in triangles.

Theorem 7. Suppose we have the triangle T_{n,k}, which is generated by G(x)^{k} = ∑_{n⩾k} T_{n,k}x^{n}. Then the following identity holds for the central coefficients of the triangle

T_{2n−1,n} = ∑_{i=1}^{n} \frac{1}{i}T_{2i−1,i} T_{2(n−i),n−i}.  (9)

Proof. The result follows from Theorem 2 and the expression (3). We point out that

F (x) = ∑_{n>0} \frac{1}{n}T_{2n−1,n}x^{n}

and

\frac{x F′(x)}{F (x)} = ∑_{n⩾0} T_{2n,n}x^{n}.

Since

x F′(x) = (\frac{x F′(x)}{F (x)}) F (x),

by applying the multiplication rule for formal power series, we obtain the desired result.

Example 8. Using Theorem 7, we obtain the identities for the Stirling numbers.

The Stirling numbers of the first kind s(n, k) count the number of permutations of n elements with k disjoint cycles. The Stirling numbers of the first kind are defined by the following generating function [1]:

ψ_{k}(x) = ∑_{n≥k} s(n, k)\frac{x^{n}}{n!} = \frac{1}{k!} ln^{k}(1 + x).

With the help of (9), we find the following identity for the Stirling numbers of the first kind:

s(2n − 1, n) = ∑_{i=1}^{n} \begin{matrix}( & {2n−1 \atop 2i−1} & ) \\ ( & {n \atop i} & ) \end{matrix} \frac{s (2i − 1, i) s (2 (n − i) , n − i)}{i}.

The Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into k nonempty subsets. The Stirling numbers of the second kind are defined by the following generating function [1]:

Φ_{k}(x) = ∑_{n≥k} S(n, k)\frac{x^{n}}{n!} = \frac{1}{k!}(e^{x} − 1)^{k}.

Using Theorem 7, we derive the following identity

S(2n − 1, n) = ∑_{i=1}^{n} \begin{matrix}( & {2n−1 \atop 2i−1} & ) \\ ( & {n \atop i} & ) \end{matrix} \frac{S (2i − 1, i) S (2 (n − i) , n − i)}{i}.

Example 9. Suppose we have the triangle defined by the following expression

(x e^{x})^{k} = ∑_{n⩾k} \frac{k^{n−k}}{(n − k)!})x^{n}.

Then, using (9), we get

\frac{n^{n−1}}{(n − 1)!} = ∑_{i=1}^{n} \frac{i^{i−2} (n − i)^{n−i}}{(i − 1)! (n − i)!}

or after simple manipulation

n^{n−1} = ∑_{i=1}^{n} \binom{n − 1}{i − 1}i^{i−2} (n − i)^{n−i}.

Example 10. Suppose we have the triangle defined by the following expression

(\frac{x}{(1 − x)^{m}} )^{k} = ∑_{n⩾k} \binom{n + (m − 1)k − 1}{n − k}x^{n}.

Then, according to (9), we obtain

\binom{(m + 1) n − 2}{n − 1} = ∑_{i=1}^{n} \frac{1}{i}\binom{im + i − 2}{i − 1} \binom{(m + 1) n − im − i − 1}{n − i}.

If we put m = 2, we derive the following identity

\binom{3n − 2}{n − 1} = ∑_{i=1}^{n} \frac{\binom{3i−2}{i−1} \binom{3n−3i−1}{n−i}}{i}.

Example 11. Suppose we have the triangle defined by the following expression

[G(x)]^{k} = (\frac{x^{2}}{e^{x} − 1})^{k} = ∑_{n⩾k} T_{n,k}x^{n},

where

T_{n,m} = \frac{m!}{(n − m)!} ∑_{k=0}^{n−m} \frac{k! S_{1} (m + k, m) S_{2} (n − m, k)}{(m + k)!}.

The solution of the equation (4) for this case, that is, F (x) = x\frac{F (x)}{e^{F (x)}−1}, is the generating function ln(1 + x) (see the sequence \underline{A191578} in [9]).

Then, according to Theorem 2, we have

\frac{xF′(x)}{F (x)} = \frac{x}{(1 + x) ln(1 + x)} = ∑_{n⩾0} T_{2n,n} x^{n}.

where

T_{2n,n} = ∑_{k=0}^{n} \frac{k! S_{2} (n, k) S_{1} (n + k, n)}{(n + k)!}.

This is reflected in the sequence A002208 in [9].

Using Theorem 7, we obtain the following identity

∑_{m=0}^{n−1} \frac{(−1)^{m}}{n − m} ∑_{k=0}^{m} \frac{k! S_{2} (m, k) S_{1} (m + k, m)}{(m + k)!} = 1.

3 Acknowledgment

The authors are grateful to the reviewer’s valuable comments that improved the manuscript.

References

[1] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Company, 1974.

[2] J. H. Curtiss, Faber polynomials and the Faber series, Amer. Math. Monthly 78 (1971), 577–596.

[3] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

[4] D. V. Kruchinin and V. V. Kruchinin, Application of a composition of generating functions for obtaining explicit formulas of polynomials, J. Math. Anal. Appl. 404 (2013), 161–171.

[5] V. V. Kruchinin and D. V. Kruchinin, Composita and its properties, J. Analysis and Number Theory 2 (2014), 1–8 .

[6] D. V. Kruchinin and V. V. Kruchinin, A method for obtaining generating functions for central coefficients of triangles, J. Integer Seq. 15 (2012), Article 12.9.3.

[7] S. K. Lando, Lectures on Generating Functions, American Mathematical Society, 2003.

[8] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[10] R. P. Stanley, Enumerative Combinatorics 2, Cambridge University Press, 1999.

[11] P. K. Suetin, Series in Faber Polynomials, Nauka, Moscow, 1984. (in Russian)

2010 Mathematics Subject Classification: Primary 05A15; Secondary 11B75, 05A10. Keywords: generating function, triangle, diagonal, central coefficient, composita.

(Concerned with sequences \underline{A001006}, \underline{A001764}, \underline{A002208}, \underline{A191578}, and \underline{A199542}.)

Received February 28 2014; revised versions received November 10 2014; December 7 2014; February 24 2015. Published in Journal of Integer Sequences, May 13 2015.

Return to Journal of Integer Sequences home page.