Heubach S., Mansour T. Combinatorics of Compositions and Words

Подождите немного. Документ загружается.

54 Combinatorics of Compositions and Words

in which the denominator has a term which is a fraction, which in turn has

another term that is a fraction, etc. Early traces of continued fractions appear

as far back as 306 b.c. Other records have been found that show that the

Indian mathematician Aryabhata (475-550) used a continued fraction to solve

a linear equation [114, pp. 28-32]. However, he did not develop a general

method. Continued fractions were only used in speciﬁc examples for more

than 1, 000 years, and the use of continued fractions was limited to the area

of number theory. Since the beginning of the twentieth century, continued

fractions have become more common in various other areas, for example, enu-

merative combinatorics. The ﬁrst connection between the pattern avoidance

problem (which will be discussed in Chapter 4) and continued fractions was

discovered by Robertson, Wilf, and Zeilberger [174], who found the ordinary

generating function for the number of 132-avoiding permutations in S

with

a prescribed number of occurrences of the pattern 123. Recently, connections

between generating functions for the enumeration of restricted permutations

or words and continued fractions have become more numerous.

Deﬁnition 2.61 A continued fraction is an expression of the form

+ ···

where the letters a

,...denote independent variables, and may be

interpreted as real or complex numbers, functions, etc. If b

=1for all i,then

the expression is called a simple continued fraction. If the expression contains

ﬁnitely many terms, then it is called a ﬁnite continued fraction; otherwise, it

is called an inﬁnite continued fraction.Thenumbersa

are called the partial

quotients. If the expression is truncated after k partial quotients, then the

value of the resulting expression is called the k-th convergent of the continued

fraction and we will refer to the continued fraction as having k levels.Dueto

the complexity of the expression above, mathematicians have adopted several

more convenient notations for simple continued fractions, the most common

being [a

,...] for the inﬁnite simple continued fraction and [a

,...,a

]

for the ﬁnite simple continued fraction.

We will now show that the generating function of the Catalan numbers can

be expressed as a continued fraction.

Example 2.62 Let

f(x)=

1 −

1 −···

Basic Tools of the Trade 55

Then it is easy to see that f(x) satisﬁes f(x)=

1−xf(x)

, or equivalently,

f(x)=1+xf

(x), which is the functional equation for the generating function

of the Catalan numbers. This phenomenon is not restricted to the Catalan

numbers, in fact, any generating function that has a functional equation of

the form

A(x)=a(x)+b(x) A(x)+c(x) A(x)

(2.11)

can be rewritten as

A(x)=

a(x)

1 − b(x) − c(x) A(x)

a(x)

1 − b(x) −

c(x) a(x)

1 − b(x) − c(x) A(x)

a(x)

1 − b(x) −

c(x) a(x)

1 − b(x) −

c(x) a(x)

1 − b(x) −

c(x) a(x)

···

Finally we introduce the Lagrange Inversion Formula,astrongtoolfor

solving certain kinds of functional equations. At its best it can give explicit

formulas where other approaches fail. It is also useful for asymptotic analysis

(in which case we have to leave the world of formal power series and deal with

issues of convergence). The Lagrange Inversion Formula applies to functional

equations of the form u = xφ(u), where φ(u) is a given function of u,when

the goal is to determine u as a function of x. More speciﬁcally, suppose we are

given the power series expansion of the function φ = φ(u), convergent in some

neighborhood of the origin in the u–φ plane. How can we ﬁnd the power series

expansion of the solution of u = xφ(u), say u = u(x), in some neighborhood

of the origin in the x–u plane? The answer is surprisingly explicit, and it even

allows us to ﬁnd the expansion of f(u(x)) for some function f.

Theorem 2.63 [193, Theorem 5.1.1] (Lagrange Inversion Formula) Let f (u)

and φ(u) be formal power series in u,withφ(0) = 1. Then there is a unique

formal power series u = u(x) that satisﬁes u = xφ(u). Furthermore, the value

f(u(x)) of f at

that root u = u(x), when expanded in a power series in x about

x =0,satisﬁes

]f(u(x)) =

n−1

](f



(u)φ

(u)).

Note that the function f in the Lagrange Inversion Formula (LIF) allows us

to compute with equal ease the coeﬃcients of the unknown function u(x)(in

which case f(u)=u), or any function of u(x), for example the k-th power (in

which case f (u)=u

). Oftentimes, we are just interested in the coeﬃcients

of the unknown function itself, and the function f does not really show up at

all in the computations. Let’s see an example of the LIF in action: we will

56 Combinatorics of Compositions and Words

derive once more that Dyck paths of length 2n are counted by the Catalan

numbers, this time with the help of the Lagrange Inversion Formula.

Example 2.64 In Example 2.50 we have derived that the generating function

C(x) for the number of Dyck paths of length 2n satisﬁes the functional equation

C(x)=1+xC

(x). If we deﬁne u(x)=C(x) − 1, then this is indeed of the

form u = xφ(u) with u(x)=C(x) − 1, φ(u)=(1+u)

and φ(0) = 1.We

choose f (u)=u, and apply Theorem 2.63 to obtain

]C(x)=

n−1

](1 + u)



n − 1



n +1





Here we have used the binomial expansion for the term (1 + u)

,andthen

determined the index i such that the power of u is n − 1, followed by some

algebraic manipulations. We have once more shown that the number of Dyck

paths of length 2n for n ≥ 1 is given by the n-th Catalan number

n+1





This example shows that the Lagrange Inversion Formula can give results

very easily; earlier, we had to work a little harder and use a special identity

to obtain the coeﬃcients in Example 2.50.

We close the section with an example where we obtain the generating func-

tion not from a recurrence relation, but by breaking the combinatorial object

of interest into parts for which we know the generating functions. By deriving

the generating function in two diﬀerent ways, we obtain an interesting (well-

known) combinatorial identity. In fact, enumerating a combinatorial object

in two diﬀerent ways can give rise to new identities, or provide combinatorial

explanations for known identities. Nice examples of this technique can be

found in [22, 193].

Example 2.65 (Partitions) Recall that a partition of n is a decreasing se-

quence of integers that sum to n. We will derive the generating function for

the number of partitions in two diﬀerent ways, which leads to an interesting

identity.

Since the parts of the partition are written in decreasing order, the only

thing that matters is which parts are included and how many of each. Each

part of size i>0 contributes a factor of x

to the generating function. If we

look at the parts of size i, then there can be any number of them, thus their

contribution is given by

∞



k=0

)

1 − x

Since the generating function for the number of partitions is the convolution

of all these generating functions for parts of size i,weobtain

A(x)=

∞



i=1

1 − x

Basic Tools of the Trade 57

On the other hand, if we separate the partitions into diﬀerent classes, we

obtain A(x) as the sum of the respective generating functions. A partition can

either be empty, consist of only 1s (and at least one 1), consist of at least one

2 and any number (or no)1s,consistofatleastone3 and any number (or

no)1sor2s, etc. If there is at least one k, then the generating function is

given by

1−x

, and therefore

A(x)=1+

1 − x

+ ···

∞



i=0



j=1

(1 − x

)

This yields the identity

∞



i=1

1 − x

∞



i=0



j=1

(1 − x

)

The fact that there is no easy recursion for partitions gives an indication

that partitions are harder to analyze than compositions. There is a large body

of research on partitions, and a good reference is [10].

2.4 Exercises

Exercise 2.1 Find a recurrence relation

(1) (of order 2) for the number of compositions of n with parts in N;

(2) for the number of words of length n on [k];

(3) for the number of permutations of [n];

(4) for the reverse conjugate compositions of n.

Use the iteration method to ﬁnd explicit formulas for the above recurrence

relations.

Exercise 2.2 Use Maple or Mathematica to ﬁnd the ﬁrst 15 terms of the

sequences

(1) a

= a

n−1

+3a

n−2

with a

=1and a

=2.

(2) b

n−1

+1 with b

=2.

58 Combinatorics of Compositions and Words

Exercise 2.3 Solve the recurrence relations of Exercise 2.2 using Maple or

Mathematica.

Exercise 2.4 Determine the number of words of length n on the alphabet [3],

and derive the generating function for the number of words of length n −1 on

the alphabet [3].

Exercise 2.5 Find recurrence relations for the following counting problems:

(1) The number of words w = w

···w

of length n on {1, 2} satisfying

≥ w

i+2

for all i.

(2) The number of words w = w

···w

of length n on {1, 2, 3} satisfying

≥ w

i+2

for all i.

Use the iteration method to ﬁnd explicit formulas for the above recurrence

relations.

Exercise 2.6

(1) Find an explicit formula for the number of Carlitz compositions of n in

{1, 2}.

(2) A word is called Carlitz if it does not contain two consecutive letters that

are the same. For example, 121 and 212 are the only Carlitz words on

{1, 2} of length three. Find an explicit formula for the number of Carlitz

words on {1, 2} of length n.

Exercise 2.7 Prove the identity



n+1

i=1

= F

n+3

−1 for n ≥ 0(where F

the n-th Fibonacci number) by using rules for generating functions.

Exercise 2.8 Derive the explicit formula for the Lucas sequence.

Exercise 2.9 Prove by induction that the explicit formulas for the Fibonacci

and Lucas sequences produce integer values.

Exercise 2.10 Prove Theorem 2.22.

Exercise 2.11 Prove Rules 2.45 and 2.56 either by induction on k or by

using the deﬁnition of the generating function.

Exercise 2.12 Compute the generating function for the sequence {a

}

n≥0

where a

=1and a

= F

for n ≥ 1.

Exercise 2.13 Let C(m; n) denote the number of compositions of n with m

parts in N. Prove that for ﬁxed m ≥ 1,



n≥0

C(m; n)x

(1 − x)

Basic Tools of the Trade 59

Exercise 2.14

(1) Derive the generating function for the number of compositions of n in

{1, 2} that avoid the substring 11. The recurrence relation for this se-

quence was derived in Example 2.17.

(2) The ﬁrst few values of the sequence are given by 1, 1, 1, 2, 2, 3, 4,

5, 7, 9, 12, 16 and 21. Checking this sequence in the Online Ency-

clopedia of Integer Sequences [180] produces a match with the Padovan

sequence A000931. However, the sequence for the number of composi-

tions is shifted in relation to the Padovan sequence. Use the generating

function given for the Padovan sequence and apply Rule 2.45 to derive

the generating function for the number of compositions in {1, 2} that

avoid the substring 11. Compare your answer to Part (1).

Exercise 2.15 Find the recurrence relation and the generating function for

the number of compositions of n in {1, 2} without d consecutive 1s. (Hint:

condition on the position of the ﬁrst 2.)

Exercise 2.16 Derive a recurrence relation for the Bell numbers B

(see

Deﬁnition 2.59).

Exercise 2.17 A smooth word is a word in which the diﬀerence between any

two adjacent letters is either −1, 0 or 1. Find an explicit formula for the

generating function for the number of smooth words of length n on the alphabet

[3]. Use either Maple or Mathematica to ﬁnd an explicit formula for the

number of smooth words of length n on the alphabet [3].

Exercise 2.18 A strictly smooth word is a word in which the diﬀerence be-

tween any two adjacent letters is either −1 or 1. Find an explicit formula for

the generating function for the number of strictly smooth words of length n on

the alphabet [3]. Use either Mathematica or Maple to ﬁnd an explicit formula

for the number of strictly smooth words of length n on the alphabet [3].

Exercise 2.19 Find an explicit formula for the generating function for the

number of smooth compositions (seeExercise1.12) of n with parts in [3].

Exercise 2.20 Find an explicit formula for the generating function for the

number of strictly smooth compositions (see Exercise 1.12 ) of n with parts in

[3].

Exercise 2.21 A k-ary tree is a plane tree in which each vertex has either

out-degree 0 or k (see Deﬁnitions 7.2 and 7.20 ). A vertex is said to be internal

if its out-degree is k. Use the LIF to ﬁnd an explicit formula for the number

of k-ary trees on n internal vertices.

60 Combinatorics of Compositions and Words

Exercise 2.22 Go to the On-Line Encyclopedia of Integer Sequences [180]

and look up the functional equation for the large Schr¨oder numbers (sequence

A006318). Verify that it has the form of (2.11) and derive its continued

fraction form.

Exercise 2.23

∗

Let f

m,l

(x, y)=



(1 − x − y)

(1 − 2x −(1 −x)y)

m+1



. Show that



m,l

(x, y)=

(1 − x)

−m

(1 − 2x)

+1



i≥0



 + i





(1 − 2x)

Hint: [y

m,l

(x, y)=

(1 − x)

(1 − 2x)

m,l



(1−2x)

(1−x)



Chapter 3

Compositions

In this section we will derive basic results on compositions, and also look

at some variations of compositions, by restricting either the placement of

the parts within the composition or the set from which the parts are taken.

Examples of restriction in terms of placement of the parts are Carlitz compo-

sitions and palindromic compositions. In the area of restricted sets, we will

present the results of Alladi and Hoggatt [7] and Grimaldi [76], who studied

compositions in {1, 2} and compositions with odd parts. We will then derive

results for a general set A which includes their results as well as results on

the sets A = {1,k} [50], A = N\{1} [77], A = N\{2} [52], and more generally,

A = N\{k} [51] as special cases.

To provide alternative viewpoints which often simplify proofs, we will give

two additional graphical representations of compositions, namely bar graphs

and tilings. Both bar graphs and tilings are combinatorial objects studied in

their own right (see for example [26] for bar graphs and [29, 44, 66, 81, 82,

84, 85, 86, 107, 106, 151, 152, 153, 167] for a small sampling of tiling related

articles). Framing questions about compositions in terms of bar graphs or

tilings has the potential to lead to new questions and insights. We conclude

with colored compositions, especially the n-color compositions introduced by

Agarwal [3], and a variation of compositions that arises from the bar graph

representation of a composition.

3.1 Deﬁnitions and basic results (one variable)

In the examples given in Chapter 2, we looked at compositions in N and

also at compositions in restricted sets, such as A = {1, 2} or the set of odd

integers. We will use the following notation to refer to compositions with

parts in a set A.

Deﬁnition 3.1 Let A = {a

,...}⊆N be an ordered set. We denote the

number of compositions of n with parts in A (respectively with m parts in A)

by C

(n)(respectively C

(m; n)). The corresponding generating functions are

62 Combinatorics of Compositions and Words

given by

(x)=



n≥0

(n)x

and C

(m; x)=



n≥0

(m; n)x

with C

(0) = C

(0; 0) = 1, C

(m;0) = 0 for m ≥ 1,andC

(m; n)=0for

n<0. We will omit the reference to A if A = N, that is, C(n) denotes the

number of compositions in N.

Note that

(x)=



n≥0





m≥0

(m; n)





m≥0



n≥0

(m; n)x



m≥0

(m; x).

(3.1)

We start by introducing a visualization of a composition as a bar graph that

will be useful for deriving recurrence relations for the generating functions.

Deﬁnition 3.2 A bar graph of a composition σ = σ

···σ

is a sequence

of columns composed of cells, where column j has σ

cells.

Figure 3.1 shows the bar graphs corresponding to the compositions of 4.

FIGURE 3.1: Bar graphs associated with compositions of 4.

Using the bar graph of a composition to set up a recurrence relation, we

give a diﬀerent proof of Theorem 1.3. In addition, we derive the respective

generating functions.

Theorem 3.3 For 1 ≤ m ≤ n, C(n)=2

n−1

and C(m; n)=



n−1

m−1



.The

respective generating functions are C(x)=

1 − x

1 − 2x

and C(m; x)=

(1 − x)

Compositions 63

Proof We give two diﬀerent proofs to illustrate the techniques of Chapter 2,

namely iteration and use of generating functions. For both approaches we

will rely on the fact that each composition σ of n canbewrittenintheform

σ = σ



,whereσ

∈ [n]andσ



is a composition of n − σ

, as illustrated in

Figure 3.2.



FIGURE 3.2: Recursive structure of compositions.

Thus, for all n ≥ 1,

C(n)=



j=1

C(n − j)=

n−1



j=0

C(j). (3.2)

This implies that C(n) −C(n −1) = C(n −1), or C(n)=2C(n −1). Iterating

this equation and using the initial condition C(0) = 1 we get that C(n)=2

n−1

for all n ≥ 1.

We now use the generating function approach. One way to do this is to

multiply (3.2) by x

,sumovern ≥ 1 and then express everything in terms of

the generating function C(x). However, with a little practice, we can go di-

rectly from the recurrence for C(n) to a recurrence for the generating function

without these intermediate steps. The structure given in Figure 3.2 indicates

that a composition (translates into C(x)) consists of a part σ

(which con-

tributes a factor of x

) combined with another composition (contributes the

factor C(x)). Taking into account the empty composition (which contributes

1), we arrive at

C(x)=1+



≥1

C(x)=1+

1 − x

C(x).

This implies that

C(x)=

1 − x

1 − 2x

=(1− x)



n≥0

=1+



n≥1

n−1