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

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

64 Combinatorics of Compositions and Words

and C(n)=[x

]C(x)=2

n−1

, as expected.

To compute C(m; n), notice that every part of a composition has generating

function x/(1 − x), because the possible sizes for a part are m ≥ 1. Since

the parts add to the total, by Rule 2.51, C(m; n) is the convolution of the

generating functions of the individual parts, that is,

C(m; x)=



1 − x



(1 − x)

= x



j≥0



m − 1+j





n≥m



n − 1

m − 1



, (3.3)

where we have used (A.3) for the third equality. Reading oﬀ the coeﬃcient of

, we obtain that C(m; n)=[x

]C(m; x)=



n−1

m−1



. 2

3.2 Restricted compositions

In this section we consider compositions that have certain restrictions. Re-

strictions can occur in at least two ways: restricting the way the parts are

arranged within the composition, or restricting the set from which the parts

of the composition are taken. We start by looking at compositions that are

restricted in the way the parts are arranged.

3.2.1 Palindromic compositions

Recall that palindromic or self-inverse compositions are those that read the

same from left to right as from right to left. The results on the number of such

compositions and those that have a given number of parts were already known

to MacMahon [136, Statement 5, pp. 838–839]. The generating function in

the case of a general set A was given by Hoggatt and Bicknell [98, Theorem

1.2]. We will use the notation introduced in Deﬁnition 3.1 for compositions by

replacing C with P when referring to palindromic compositions. For example,

(n) denotes the number of palindromic compositions of n with parts in A.

Theorem 3.4 The number of palindromic compositions of n is given by

P (n)=2

n/2

where x denotes the largest integer less than or equal to x, with generating

function P (x)=

1+x

1 − 2x

Compositions 65

Proof Using the same argument as in the case of compositions, but taking

into account that any part that occurs at the beginning also has to occur at

the end of a palindromic composition, is not hard to see that P (n)satisﬁes

the recurrence relation

P (n)=1+P (n − 2) + P (n − 4) + P (n − 6) + ··· ,n≥ 2,

with initial conditions P (0) = P (1) = 1, and P (n) = 0 for all n<0. This

implies that P (n)=2P (n − 2) and iteration gives that P (n)=2

n/2

,as

required. From the recurrence, we obtain (by multiplying by x

and summing

over n ≥ 2) that

P (x) − x − 1=

1 − x

P (x).

Alternatively, using an appropriate modiﬁcation of Figure 3.2, we obtain the

recursion for the generating function directly as

P (x)=

1 − x



≥1

2σ

P (x)=

1 − x

P (x),

where the factor

1−x

accounts for the empty palindromic compositions and

those consisting of a single part. Solving either equation for P (x)givesthe

stated result. 2

If we count palindromic compositions according to their number of parts,

we get a result that depends on the parity of the number of parts.

Theorem 3.5 The number of palindromic compositions

(1) of 2n with 2k parts equals



n−1

k−1



(2) of either 2n or 2n − 1 with 2k +1 parts equals



n−1



The respective generating functions are

P (2k; x)=



1 − x



and

P (2k +1;x)=



1 − x





1 − x



66 Combinatorics of Compositions and Words

Proof First we look at palindromic compositions with an even number of

parts m =2k, which always result in a composition of an even n. Such

a palindromic composition consists of a composition with k parts and its

reverse. Since we get each part in duplicate, it follows from (3.3) that the

generating function is given by

P (2k; x)=C(k; x



n≥k



n − 1

k − 1



which implies that P (2k;2n)=



n−1

k−1



. If there are an odd number of parts

m =2k + 1, then we obtain a composition of either odd or even n.Inthis

case, the palindromic composition consists of a nonzero center part that occurs

once, and a nonzero composition with k ≥ 1 parts and its reverse. Hence,

P (2k +1;x)=



1 − x



C(k; x



i≥1



j≥k



j − 1

k − 1



(Note that the formula also covers the case k = 0, the composition consisting

of just one part.) Expanding the double sum and collecting terms according

to the power of x we obtain that

P (2k +1;2n)=P (2k +1;2n − 1) =

n−k



i=1



n − i − 1

k − 1





n − 1



where the last equality follows from the well known identity (A.6) for a = k−1

and b = n − 2. 2

3.2.2 Carlitz compositions

Recall that a Carlitz composition of n is a composition in which no adjacent

parts are the same (see Deﬁnition 1.18).

Deﬁnition 3.6 We denote the number of Carlitz compositions of n with parts

in A by CC

(n), with generating function CC

(x)=



n≥0

(n)x

, where

we deﬁne CC

(0) = 1 as usual.

Theorem 3.7 [38, Section 2] The generating function for the number of Car-

litz compositions of n with parts in N is given by

CC (x)=

1 −



j≥1

1+x



j≥1

(−1)

1 − x

Compositions 67

Proof As in the proof of Theorem 3.3, we set up a recursion for the number

of Carlitz compositions of n in terms of Carlitz compositions of k<nby

splitting oﬀ the ﬁrst part. However, we now need to keep track of the size

of this part σ

as the remainder of the composition cannot start with that

part. Let CC (σ

···σ



|x) be the generating function for the number of Carlitz

compositions that start with σ

···σ



. Since each Carlitz composition is either

the empty composition or starts with some j ∈ N,wehavethat

CC (x)=1+



j∈N

CC (j|x). (3.4)

Looking at the ﬁrst two parts of σ, we have that a composition starting with

j either consists of just the part j or starts with ji,wherei = j.Thus,

CC (j|x)=x



j=i

CC (ji|x)=x

+ x



j=i

CC (i|x)

= x

+ x

(CC (x) − CC (j|x) − 1) = x

(CC (x) − CC (j|x)),

which gives that CC (j|x)=

1+x

CC (x). Substituting this result into (3.4)

leads to CC (x)=1+



j∈N

1+x

CC (x). Solving for CC (x)givestheﬁrst

representation for CC (x). The second form is the one given originally by

Carlitz [38], and equality of the two forms is a matter of simple algebraic

manipulations (see (8.25), where we will treat a more general case). 2

Combining the two restrictions discussed so far leads to palindromic Carlitz

compositions of n. Note that a palindromic Carlitz composition with an even

number of parts cannot occur, as the two middle parts would have to be the

same.

Deﬁnition 3.8 We denote the number of palindromic Carlitz compositions of

n with parts in A by CP

(n) with CP

(0) = 1. The corresponding generating

function is denoted by CP

(x)=



n≥0

(n)x

Theorem 3.9 The generating function for the number of palindromic Carlitz

compositions of n is given by

CP (x)=1+



j≥1

1+x

1 −



j≥1

1+x

Proof We proceed as in the proof of Theorem 3.7. Let CP (σ

···σ



|x)be

the generating function for the number of palindromic Carlitz compositions

that start with σ

···σ



. As before, CP (x)=1+



j∈N

CP (j|x). The only

diﬀerence in the argument is that we split oﬀ both the ﬁrst and the last part

68 Combinatorics of Compositions and Words

for the recursion, resulting in a factor of x

rather than x

, except for the

composition σ = j.Thus,

CP (j|x)=x

+ x



j=i

CP (i|x)=x

+ x

(CP (x) − CP (j|x) − 1),

which gives (after simpliﬁcation) that

CP (j|x)=

(1 − x

)

1+x

CP (x).

Substituting this result into the equation for CP (x) and solving for CP (x)

gives the desired result. 2

3.3 Compositions with restricted parts

We now look at compositions in which the parts are restricted, that is, A is

a strict subset of N. Several of these restrictions lead to nice connections with

the Fibonacci sequences. The simplest set from which to form compositions

is the set A = {1, 2}. This set was investigated by Alladi and Hoggatt [7] who

proved results on the number of compositions and palindromic compositions

with parts in A.

Theorem 3.10 [7, Theorems 1 and 6]

For A = {1, 2} and n ≥ 0,

(1) C

(n)=F

n+1

(2) P

(2n +1)=F

n+1

and P

(2n)=F

n+2

Proof (1) Since each composition starts either with a 1 or a 2 followed by

a composition of n − 1orn − 2, respectively, we get that

(n)=C

(n − 1) + C

(n − 2).

This is the recursion for the Fibonacci sequence, so we just need to check the

initial conditions. Since C

(0) = C

(1) = 1, we obtain that C

(n)=F

n+1

(2) For palindromic compositions of 2n + 1, the middle part must be odd

(and therefore a 1), with a composition of n on the left, and its reverse on the

right. Thus,

(2n +1)=C

(n)=F

n+1

The formula for P

(2n + 1) in [7] contains a typo.

Compositions 69

For palindromic compositions of 2n, there are two possibilities. If the palin-

dromic composition has an odd number of parts, then the middle part has to

be a 2 combined with a composition of n − 1 and its reverse. If there are an

even number of parts, then the palindromic composition is made up from a

composition of n and its reverse. Thus,

(2n)=C

(n − 1) + C

(n)=F

+ F

n+1

= F

n+2

as claimed. 2

Alladi and Hoggatt also enumerated these compositions according to rises,

levels and drops (see Deﬁnition 1.12). In the case A = {1, 2}, a rise corre-

sponds to a 1 followed by a 2, a drop occurs whenever a 2 is followed by a 1,

while 11 or 22 create a level. It is easy to see that the number of rises in all

compositions is equal to the number of drops in all compositions, as each rise

in a composition σ is matched by a drop in the reverse composition R(σ).

Theorem 3.11 [7, Theorems 9 and 10] Let r(n) and l(n) denote the numbers

of rises and levels in all compositions of n with parts in A = {1, 2}.Then

(1) r(n +1)=r(n)+r(n − 1) + F

n−1

(2) l(n +1)=l(n)+l(n −1) + L

n−1

where F

and L

are the Fibonacci and Lucas numbers, respectively. The

associated generating functions are given by

(x)=

(1 − (x + x

))

and A

(x)=

x(x + x

)

(1 − (x + x

))

Note that r(n) is a shifted convolution of two Fibonacci sequences, and

that l(n) is the convolution of the Fibonacci sequence and the Lucas sequence

(with L

:= 1).

Proof (1) The compositions of n + 1 are obtained by adding either a 1 to

a composition of n or a 2 to a composition of n − 1. In each case we get all

the rises in those compositions, plus an additional rise if a 2 is added to a

composition of n − 1 ending in 1, of which there are C(n − 2) = F

n−1

.This

establishes the recurrence. The derivation of the generating function is left as

Exercise 3.9.

(2) By similar reasoning, we have that l(n+1) = l(n)+F

+l(n−1)+F

n−2

Since L

= F

n+1

+ F

n−1

(which can be easily established by induction), we

obtain the recurrence relation. The generating function for l(n) is derived

by ﬁrst proving that l(n)=r(n +1)+r(n − 1). Since l(2) = r(3) = 1 and

r(1) = 0, the formula holds for n = 2. Assume it holds true for n.Then

l(n +1)=l(n)+l(n − 1) + F

+ F

n−2

=(r(n +1)+r(n − 1)) + (r(n)+r(n − 2)) + F

+ F

n−2

= r(n +2)+r(n).

70 Combinatorics of Compositions and Words

Thus,

(x)=

∞



n=1

(r(n +1)+r(n −1))x

(x)+xA

(x)=

x(x + x

)

(1 − (x + x

))

which completes the proof. 2

We now look at a diﬀerent set A, namely the set of odd integers. Compo-

sitions with parts in A = {2k +1,k ≥ 0} were studied by Grimaldi [76], who

found interesting connections with the Fibonacci and Lucas sequences. We

give one of his results.

Theorem 3.12 [76, Section 1] Let A be the set of positive odd integers and

let a(n, 2k +1) denote the number of occurrences of 2k +1 in the compositions

of n.Then

(1) C

(n)=F

for n ≥ 1.

(2) a(1, 1) = 1 and a(n, 1) =

n−1

for n ≥ 2.

(3) a(n, 2k +1)=a(n − 2k, 1) for k ≥ 0, n ≥ 2k +1.

Proof (1) The compositions of n with odd parts can be recursively created

by either appending a 1 to the compositions of n −1orbyincreasingthelast

part of a composition of n − 2by2. Thus,C

(n)=C

(n − 1) + C

(n − 2).

Since the initial conditions are C

(1) = C

(2) = 1, we have C

(n)=F

for

n ≥ 1.

(2) Using the same construction as in part (1), but now keeping track of

the number of 1s, we obtain a recurrence relation for the sequence a(n, 1).

Those compositions that end with 1 contribute an additional 1 to the total

count. However, those compositions of n − 1 which had a 1 at the end that

was increased to a 3 contribute a loss of one 1 per composition. Those are

exactly the compositions of n − 2. Therefore,

a(n +1, 1) = a(n, 1) + C

(n)+a(n − 1, 1) − C

(n − 2)

= a(n, 1) + a(n − 1, 1) + F

n−1

This is a nonhomogeneous second order linear recurrence relation. Let a

a(n, 1). Then the general solution is of the form a

= h(n)+p(n), where

h(n)=c

+ c

(since the homogeneous recurrence relation is the Fi-

bonacci recurrence relation) and p(n)=c

nα

+ c

nβ

(since the nonhomo-

geneous part consists of the Fibonacci sequence; see for example [78]).

Substituting ﬁrst p(n) and the explicit formula for F

n−1

into the recurrence

relation and using that α

− α − 1=β

− β − 1 = 0 results in equations

Compositions 71

that can be solved for c

and c

, and we obtain that c

=(−1+

√

5)/10 and

=(−1 −

√

5)/10. Using the initial conditions a

=2anda

=3,wethen

obtain c

=1− (7

√

5/25) and c

=1+(7

√

5/25). This gives an expression

for a

which can be transformed into a combination of Fibonacci and Lucas

numbers by splitting oﬀ a factor of α and β from each of the terms α

and

and then collecting terms according to α

n−1

−β

n−1

and α

n−1

+ β

n−1

(see

Exercise 3.10).

(3) To illustrate the general case, look at the following example. The com-

positions of 3 into odd parts are given by 111 and 3. The compositions of

5 into odd parts are 11111, 113, 131, 311, and 5. The only compositions in-

volving a 3 are 113, 131, and 311. We can obtain each of these if we increase

each of the 1s in the composition 111 (one at a time) to 3. In general, each

part of size 2k − 1 in a composition of n − 2 can be increased by 2 to ac-

count for one of the parts of size 2k + 1 in the compositions of n. Therefore,

a(n, 2k +1) = a(n − 2, 2k − 1), and iteration will give the stated result for

k ≥ 0, n ≥ 2k +1. 2

Note that in this case, starting with the recurrence equation for a(1, 1) has

led to the connection with the Fibonacci and Lucas sequence, which would

not have been so easy to see from the generating functions. The moral of the

story is that each approach has its own advantages and disadvantages.

So far we have looked at speciﬁc sets A, and utilized the structure of the

particular set to derive recursions and generating functions. We will now

derive structural results for a general set A, from which we can then obtain

specialized results by using a particular set A.

Theorem 3.13 Let A ⊆ N and m ≥ 0. Then the generating function for the

number of compositions of n with m parts in A is given by

(m; x)=





a∈A



and the generating function for the total number of compositions of n with

parts in A is given by

(x)=

1 −



a∈A

Proof Each part of a composition can consist of any of the elements in

A, thus the generating function for a single part is given by



a∈A

composition of n with m parts is the sum of these parts, hence the generating

functions multiply, which gives the ﬁrst result. From (3.1), we have that

(x)=



m≥0





a∈A



1 −



a∈A

72 Combinatorics of Compositions and Words

which completes the proof. 2

Example 3.14 Chinn and Heubach [51] studied (1,k) compositions (that is,

compositions in {1,k}), a generalization of the (1, 2) compositions studied by

Alladi and Hoggatt [7]. Using Theorem 3.13 with A = {1,k} ,wecaneasily

recover their result that C

(x)=

1−x−x

(see [51, Lemma 1, Part 1] ).For

k =2, this reduces to the generating function of the shifted Fibonacci sequence

(see (A.1)), and we obtain the result given in Theorem 3.10.

Example 3.15 Applying Theorem 3.13 to the set A = {1, 2, ..., },weobtain

the result of Hogatt and Bicknell [98]:

(x)=

1 − x − x

−···−x



−1

1 − x − x

−···−x



Thus, the number of compositions of n with parts that are less than or equal

to  is given by the shifted -generalized Fibonacci number. Speciﬁcally,

{1,2,...,}

(n)=F (; n +  − 1)

for n ≥ 0,whereF (; n)=





i=1

F (; n −i) with F (;  −1) = 1 and F (;0)=

···= F (; −2) = 0 [69]. Combinatorially, this can be seen using the following

recursive method: to create the compositions of n, add i to the right end of

the compositions of n − i,fori =1, 2,...,.The-generalized Fibonacci

sequences occur in [180] as sequence A000073 for  =3, A000078 for  =4,

A001591 for  =5, and A001592 for  =6.

We can also easily obtain results on odd and even compositions.

Example 3.16 Theorem 3.13 when applied to the odd or even positive inte-

gers gives

{1,3,5,...}

(j; x)=



1 − x



and C

{2,4,6,...}

(j; x)=



1 − x



that is, C

{2,4,6,...}

(j; x)=x

{1,3,5,...}

(j; x). This equality follows easily, since

every odd composition of n with j parts uniquely corresponds to an even com-

position of n + j with j parts (increase each odd part by 1).Sonowlet

A = {2, 4, 6,...}.ToobtainC

(j; n)=[x

(j; x), the number of even

compositions, we need to expand C

(j; x) into a series. Using (A.3), we get

that

(j; x)=

(1 − x

)

= x



i≥0



i +(j −1)

j − 1





≥j−1



j − 1



2+2

Compositions 73

after appropriate re-indexing. Thus, the number of compositions of 2n with

j parts in {2, 4, 6,...} is given by C

{2,4,6,...}

(j;2n)=



n−1

j−1



, which is also the

number of compositions of 2n − j with j odd parts.

Turning our attention to the total number of compositions with odd parts,

Theorem 3.13 gives

{1,3,5,...}

(x)=

1 −

1 − x

1 − x − x

This is the generating function of the modiﬁed Fibonacci sequence (

=1,

= F

for n ≥ 1), therefore, the number of compositions of n with parts in

{1, 3, 5,...} is given by F

for n ≥ 1, which was proved in Theorem 3.12 using

the recurrence relation. More generally, let N

d,e

be the set of all numbers of

the form k · d + e where k ≥ 0, d, e ∈ N. Then Theorem 3.13 yields

d,e

(x)=

1 −

1 − x

− x

If d =2e, then the set A consists of all odd multiples of e,and

2e,e

(x)=C

{e,3e,5e,...}

(x)=

1 − x

− x

= g

Thus, the number of compositions of n = k · e with parts in {e, 3e, 5e,...}

is given by F

for k ≥ 1. This result can be readily explained using a com-

binatorial argument: multiply each part of a composition of n with parts in

{1, 3, 5,...} by e to create a composition of n · e with parts in {e, 3e, 5e,...}.

In the examples discussed so far, the generating function we obtain when

applying Theorem 3.13 to a speciﬁc set A can be expanded into a series that

allows us to obtain an explicit expression for C

(n). This is not always the

case, as will be seen in the next example.

Example 3.17 Let A = {2, 3, 5, 7, 11, 13,...} be the set of prime numbers.

Then

(x)=

1 −



p∈A

Since powers of x

for n ≤ K cannot involve powers of x

with p>Kfor some

constant K, we can use the function 1/(1 −



p∈A,p≤K

) to approximate

(x) for powers up to K. Using Maple or Mathematica, we expand the

approximate function into its Taylor series. Since the 11th prime number is

31,wecanusetheﬁnitesumwith11 terms to get correct values for C

(n)

for n ≤ 31.HereistheMathematica code for series expansion:

Series[1/(1 - Sum[x^Prime[n], {n, 1, 11}]), {x, 0, 30}]