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

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

114 Combinatorics of Compositions and Words

Theorem 4.32 Let τ =1



. Then the generating function C

(x, y, q) is given

1 −



a∈A

y + x

+ ···+ x

a(−1)

−1

+ x

a



q/(1 − x

yq)

1+x

y + x

+ ···+ x

a(−1)

−1

+ x

a



q/(1 − x

yq)

Proof For all s =1, 2,...,−1,

|x, y, q)=x



b=a∈A

b|x, y, q)+C

s+1

|x, y, q).

Observe that if σ ∈C

n,m

(τ; r) (that is, σ is a composition of n with m parts

in A having r occurrences of τ)andσ

···σ

s+1

= a

b,where1≤ s ≤  − 1

and b = a, then no occurrence of the pattern τ in σ can involve any of the

ﬁrst s letters of σ.Thus,

σ ∈C

n,m

(τ; r) if and only if bσ

s+2

···σ

∈C

n−sa,m−s

(τ; r),

and therefore, for 1 ≤ s ≤  − 1,

|x, y, q)=x

+ x



b=a∈A

(b|x, y, q)+C

s+1

|x, y, q).

Equivalently, using (4.11), we have that

|x, y, q)=x

(x, y, q) −C

(a|x, y, q)) + C

s+1

|x, y, q). (4.18)

Moreover, for s = ,



|x, y, q)=x

a



q +



b=a∈A



b|x, y, q)+C

+1

|x, y, q).

If σ ∈C

n,m

(τ; r)andσ

···σ



+1

= a



b where b = a,thenexactlyone

occurrence of the pattern τ can involve the ﬁrst  letters of σ. Therefore,

σ ∈C

n,m

(τ; r) if and only if bσ

+2

···σ

∈C

n−a,m−

(τ; r − 1). If b = a,we

get that σ ∈C

n,m

(τ; r) if and only if σ

···σ

∈C

n−a,m−1

(τ; r − 1). Hence,



|x, y, q)=x

a



q + x

a





b=a∈A

(b|x, y, q)+x

yqC



|x, y, q),

which, using (4.11), is equivalent to



|x, y, q)=

a



1 − x

(x, y, q) −C

(a|x, y, q)). (4.19)

Statistics on Compositions 115

Iterating (4.18) for s, s +1,...,− 1 and using (4.19) we obtain that

|x, y, q)



+ ···+ x

a(−1)

−1

a



1 − x



(x, y, q) −C

(a|x, y, q))

for all s =1, 2,.... Letting s = 1 and solving for C

(a|x, y, q)gives

(a|x, y, q)=

y + x

+ ···+ x

a(−1)

−1

a



1 − x

1+x

y + x

+ ···+ x

a(−1)

−1

a



1 − x

(x, y, q),

which together with (4.11) completes the proof. 2

We can now apply Theorem 4.32 to a generalization of the Carlitz compo-

sitions.

Deﬁnition 4.33 A k-Carlitz composition is a composition in which no k

consecutive parts are the same, for k ≥ 2.

Example 4.34 (k-Carlitz compositions) Applying Theorem 4.32 with q =0

and A = N gives that the generating function for the number of k-Carlitz

compositions of n with m parts in N is given by

(x, y, 0) =

1 −



j≥1

y + x

+ ···+ x

j(k−1)

k−1

1+x

y + x

+ ···+ x

j(k−1)

k−1

In particular, if we use k =3in Theorem 4.32, then we obtain the generating

function for the statistic level+level [92, Theorem 2.1].

4.3.4 The patterns 1

−1

2 and 2

−1

The next simplest patterns are the patterns 1

−1

2and2

−1

1, which is

the most obvious way to generalize the 3-letter patterns 112 and 221. Note

that these two patterns are not strongly tight Wilf-equivalent, but that their

generating functions have a very similar structure.

Theorem 4.35 Let τ =1

−1

2 and ν =2

−1

1.Then

(x, y, q)=

1 −



j=1

j−1



i=1

(1 − x

(−1)a

−1

(1 − q))

and

(x, y, q)=

1 −



j=1



i=j+1

(1 − x

(−1)a

−1

(1 − q))

116 Combinatorics of Compositions and Words

Proof Let A = {a

,...,a

}. To derive a recurrence relation for C

(x, y, q),

we once more decompose σ according to where the largest part occurs. If σ

does not contain a

, then the generating function is given by C

d−1

(x, y, q).

Otherwise, σ = σ

(1)

(2)

,whereσ

(1)

has parts in A

d−1

. The generating

function for these compositions is given by x

d−1

(x, y, q)C

(x, y, q)for

ˆσ = σa

. Adding the two cases and solving for C

(x, y, q)gives

(x, y, q)=

d−1

(x, y, q)

1 − x

d−1

(x, y, q)

. (4.20)

To derive a recurrence relation for D

(x, y, q), we again decompose σ ac-

cordingtowheretheparta

occurs and let ˆσ = σb where b is bigger than

the maximal element of A.Thus,σ = σ

(1)

(2)

...a

(s)

(s+1)

,where

(i)

has parts in A

d−1

for 1 ≤ i ≤ s + 1. Note that the extra part b in the

sequence σb can only be part of an occurrence of τ if σ ends in a

−1

,whichis

equivalent to σ

(i)

= ∅ for i = s +3− ,...,s+ 1. This special case can only

occur if s ≥  − 1, in which case we get an extra factor of q in the generating

function. From the s parts a

, we obtain a factor of x

,andthesegments

(i)

and σ

(s+1)

b each create a factor of D

d−1

(x, y, q). If s ≥  −1, then we

have to take into account whether the special case occurs, so we distinguish

between the compositions not ending in a

−1

and those that do. Overall, we

obtain that

(x, y, q)=

−2



s=0

d−1

(x, y, q)

s+1

∞



s=−1

d−1

(x, y, q)

s+1

− D

d−1

(x, y, q)

(s+1)−(−1)

+ qD

d−1

(x, y, q)

(s+1)−(l−1)

Simplifying these sums using geometric series yields

(x, y, q)=

(1 − x

(−1)a

−1

(1 − q))D

d−1

(x, y, q)

1 − x

d−1

(x, y, q)

. (4.21)

Deriving an explicit formula for D

(x, y, q) is rather formidable, so we derive

a recurrence relation for

(x,y,q)

instead. (We employed the same “trick” for

the generating function of cracked compositions.) Rewriting (4.21) in terms

(x,y,q)

and deﬁning c

=1−x

(−1)a

−1

(1−q)andb

= x

y,weobtain

the linear recurrence relation

(x, y, q)

d−1

(x, y, q)

−

Statistics on Compositions 117

which can be iterated easily. Using that D

∅

(x, y, q) = 1, we obtain

(x, y, q)



i=1

−



j=1



i=j

1 −



j=1



j−1

i=1



i=1

. (4.22)

To complete the proof, we return to Equation (4.20). Combining (4.20)

and (4.21) (both have the same denominator) gives

(x, y, q)=

(x, y, q)C

d−1

(x, y, q)

d−1

(x, y, q)

. (4.23)

Rewriting (4.23) in terms of C

(x, y, q)/D

(x, y, q) produces yet another nice

linear recurrence, which, when iterated d times with the initial conditions

∅

(x, y, q)=C

∅

(x, y, q)=1,resultsin

(x, y, q)=

(x, y, q)

d−1

···c

Combining this result with (4.22) gives the explicit expression for C

(x, y, q).

We obtain the general case for |A| = ∞ by taking limits as n →∞.The

result for ν =2

−1

1 is obtained by replacing a

with a

,usingˆσ = σb with b

less than or equal to the smallest element in σ, and adjusting the arguments

accordingly. 2

Example 4.36 We can apply Theorem 4.35 for q =0and A = N to obtain

the generating function for the number of compositions of n with m parts

which avoid the -letter patterns τ =1

−1

2 and ν =2

−1

1, respectively:

(x, y, 0) =

1 −



j≥1



j−1

i=1

(1 − x

(−1)i

−1

)

and

(x, y, 0) =

1 −



j≥1



i≥j+1

(1 − x

(−1)i

−1

)

Furthermore, if we use  = 3 in Theorem 4.35, then we obtain the generating

function for the statistics level+rise and level+drop [92, Theorem 2.2]. Note

that the proof given for the patterns 112 and 221 in [92] uses a diﬀerent

argument (based on solving a system of equations) which is hard to generalize

for the longer patterns 1

−1

2and2

−1

4.3.5 Families of patterns

In this section we consider several families of -letter patterns. For example,

the easiest generalization of the pattern 212 is the pattern 21

−2

2, but a more

118 Combinatorics of Compositions and Words

general version would be the pattern pτ



p,whereτ



is a pattern of length

 −2 with letters from the alphabet [p −1]. Likewise, the pattern 121 can be

generalized to the pattern τ =1τ



1, where τ



is a pattern of length  −2with

letters from {2, 3,...}. The following theorem gives the generating functions

for these two families of patterns.

Theorem 4.37 Let τ = pτ



p and ν =1ν



1,whereτ



is a pattern of length

 − 2 in [p − 1] and ν



is a pattern of length  −2 in {2, 3,...}.Then

(x, y, q)=

1 −



j=1

1+x

−1

(1 − q)



α∈B

ord ( α)

where B

is the set of all compositions α = a

···a

−2

with parts in A

such

that α is order-isomorphic to τ



,and

(x, y, q)=

1 −



j=1

1+x

−1

(1 − q)



α∈

ord ( α)

where

is the set of all compositions α = a

···a

−2

with parts in

j−1

such that α is order-isomorphic to ν



Proof We use arguments similar to those of the proof of Theorem 4.35,

except we now use D

(x, y, q)withˆσ = a

σ. Therefore,

(x, y, q)=C

d−1

(x, y, q)+x

d−1

(x, y, q)D

(x, y, q). (4.24)

Now we derive a recurrence relation for D

(x, y, q). If σ does not contain the

letter a

, then the generating function for the number of such σ is given by

d−1

(x, y, q). Otherwise, we write σ = σ

(1)

(2)

where σ

(1)

has parts in

d−1

.Ifa

(1)

is not order-isomorphic to τ, then we can split oﬀ σ

(1)

and

we express the generating function as the diﬀerence between the generating

function for all such σ and those where σ

(1)

is order-isomorphic to τ



d−1

(x, y, q) −y

−2



α∈B

ord ( α)

(x, y, q).

For those compositions where σ

(1)

is order-isomorphic to τ



we have one oc-

currence of τ in the part that we are splitting oﬀ and therefore get an extra

factor of q in the generating function given by

−1



α∈B

ord ( α)

(x, y, q).

Statistics on Compositions 119

Combining the three cases we obtain

(x, y, q)=C

d−1

(x, y, q)

+ x

d−1

(x, y, q) −(1 −q)y

−2



α∈B

ord ( α)

(x, y, q).

Solving this equation for D

(x, y, q) and substituting into (4.24) yields

(x, y, q)=



1+(1− q)x

−1



α∈B

ord ( α)



d−1

(x, y, q)

1+(1− q)x

−1



α∈B

ord ( α)

− x

d−1

(x, y, q)

Using induction on d together with the initial condition C

p−1

(x, y, q)=

1 − y



p−1

j=1

gives the result for τ. Replacing a

by a

,usingˆσ = a

and adjusting the arguments accordingly gives the result for ν. 2

Example 4.38 We can apply Theorem 4.37 for τ =21

−2

2.Sincetheonly

compositions with −2 parts that are order-isomorphic to 1

−2

are of the form

−2

, the generating function is given by

−2

(x, y, q)=

1 −



j=1



1+x

−1

(1 − q)



j−1

i=1

(−2)a



In particular, by setting A = N, y =1, q =0,and =3we obtain the

generating function for the number of compositions of n that avoid 212 as

212

(x, 1, 0) =

⎛

⎝

1 −



j≥1

(1 − x)

1 − x + x

(x − x

)

⎞

⎠

−1

The sequence of values for n =0,...,20 is given by 1, 1, 2, 4, 8, 15, 30, 58,

114, 222, 434, 846, 1655, 3230, 6310, 12322, 24067, 46997, 91791, 179262

and 350106. Note that the ﬁrst time the pattern 212 can occur is for n =5,

as the composition 212. Similarly,

−2

(x, y, q)=

1 −



j=1



1+x

−1

(1 − q)



i=j+1

(−2)a



and the generating function for the number of compositions of n that avoid

121 is given by

121

(x, 1, 0) =

⎛

⎝

1 −



j≥1

(1 − x)

1 − x + x

2j+1

⎞

⎠

−1

120 Combinatorics of Compositions and Words

The corresponding values for n =0,...,20 are 1, 1, 2, 4, 7, 13, 24, 44,

82, 153, 284, 528, 981, 1820, 3378, 6270, 11638, 21608, 40121, 74494 and

138317. Note that the ﬁrst time the pattern 121 can occur is for n =4,asthe

composition 121.

In [92], the two patterns 212 and 121 were not treated individually, but

as part of the patterns peak and valley, as were the patterns 213

∼ 312 and

132

∼ 231. We will now look at families that generalize these patterns, namely

the patterns τ = pτ



(p +1),where τ



is a pattern with letters in [p − 1], and

ν =1ν



2, where ν



is a pattern with letters in {3, 4,...}.

Theorem 4.39 Let τ = pτ



(p+1) and ν =1ν



2,whereτ



and ν



are patterns

of length  − 2 in [p − 1] and {3, 4,...}, respectively. Then

(x, y, q)=

1 −



i=1

i−1



j=1



1+x

−1

(q − 1)



α∈B

j−1

ord ( α)



where B

j−1

is the set of all compositions α = a

···a

−2

with parts in A

j−1

such that α is order-isomorphic to τ



,and

(x, y, q)=

1 −



i=1



j=i+1



1+x

−1

(q − 1)



α∈

j+1

ord ( α)



where

j+1

is the set of all compositions α = a

···a

−2

with parts in

such that α is order-isomorphic to ν



The proof of Theorem 4.39 is similar to that of Theorem 4.37 and is left for

the interested reader.

Example 4.40 We can now obtain results on the individual 3-letter patterns

213 and 132. In both cases, the patterns τ



and ν



consist of a single part, and

therefore, ord(α)=α.Forτ = 213 and ν = 132, this gives



α∈B

j−1

ord ( α)



1≤α≤j−1

and



α∈

j+1

ord ( α)



α≥j+1

respectively. Applying Theorem 4.39 for τ = 213 with A = N, y =1,and

q =0gives

213

(x, 1, 0) =

1 −



i≥1



i−1

j=1

(1 − x

(x − x

)/(1 − x))

and the sequence for the number of compositions of n that avoid 213 for n =

0, 1,...,20 is given by 1, 1, 2, 4, 8, 16, 31, 61, 119, 232, 452, 881, 1716,

Statistics on Compositions 121

3342, 6508, 12674, 24681, 48062, 93591, 182251 and 354900.Forν = 132,

we obtain

132

(x, 1, 0) =

1 −



i≥1



j≥i+1

(1 − x

2j+1

/(1 −x))

and the corresponding sequence for n =0, 1,...,20 is given by 1, 1, 2, 4, 8,

16, 31, 61, 119, 232, 452, 880, 1712, 3331, 6479, 12601, 24505, 47653, 92664,

180187 and 350372. Note that the patterns 213 and 132 both can occur for the

ﬁrst time for n =6.

Note the curious fact that the two sequences agree up to n = 10, even

though both patterns appear for n ≥ 6. Is this a coincidence? What is going

on? To explore this phenomenon and ﬁnd answers to these questions, see

Exercise 4.14.

A ﬁnal word of caution: Theorems 4.37 and 4.39 are quite powerful in

that they cover large families of patterns, but their usefulness for ﬁnding nice

expressions for the respective generating functions depends heavily on one’s

success ﬁnding explicit expressions for the sums over compositions that are

order-isomorphic to the inner patterns τ



and ν



. In Example 4.40, the inner

pattern was of length one, so those sums were readily computed. If the inner

pattern is longer, then the task becomes more diﬃcult.

The results of this chapter also cover the case of avoidance of subword pat-

terns by setting q = 0 in the respective formulas for the generating functions.

We classify the 3-letter patterns according to tight Wilf-equivalence in Table

4.3 and list the Theorems that give the respective generating functions.

TABLE 4.3: Equivalence classes for 3-letter patterns

τ Theorem

111 Theorem 4.32

112, 221

Theorem 4.35

212, 121

Theorem 4.37

123

Theorem 4.30

132, 213

Theorem 4.39

4.4 Exercises

Exercise 4.1 Derive the results given for levels in Corollary 4.5.

122 Combinatorics of Compositions and Words

Exercise 4.2 Derive the generating function for the number of rises and lev-

els, respectively, in all compositions with parts in

(1) A = {1,k};

(2) A = {m |m =2k +1,k ≥ 0}.

Exercise 4.3 Derive the generating function for the number of levels in all

compositions of n with m parts given in Example 4.6.

Exercise 4.4 For palindromic compositions of n,

(1) derive the generating function for the number of levels;

(2) derive that [y

(x, y)=

⎧

⎪

⎨

⎪

⎩

1 − x

for m =2

(2j − 1 − (2j − 3)x

(1 + x

)(1 − x

)

for m =2j, j ≥ 2

2(1 + x)(j +(j − 1)x + jx

2j+1

(1 + x

)(1 + x + x

)(1 − x

)

for m =2j +1,j≥ 1.

Exercise 4.5 Derive the generating function for the number of rises and lev-

els, respectively, in all palindromic compositions with odd parts.

Exercise 4.6 Derive the generating function for the number of rises in all

palindromic Carlitz compositions of n with parts in N.

Exercise 4.7 Derive the generating function for the number of levels and

drops in all partitions of n with parts in N.

Exercise 4.8 Find the generating function for the number of compositions of

n that have m parts according to the number of weak rises (occurrences of the

subword patterns 11 and 12).

Exercise 4.9 Asequence(composition, word, partition) s = s

···s

called up-down alternating if s

2i−1

≤ s

and s

≥ s

2i+1

, for all i ≥ 1.Find

the generating function for the number of up-down alternating compositions

of n with m parts.

Exercise 4.10 List the 13 (subword) patterns of length three, and indicate

which ones belong to the same symmetry class with regard to occurrence.

Statistics on Compositions 123

Exercise 4.11 Prove the identity given in Equation (4.10),namely

1 − α



j=1

j−1



i=1

(1 − x

α)=



j=1

(1 − x

α).

Exercise 4.12 For G

and G

as deﬁned in the proof of Theorem 4.26, show

that

d−1

= b

d−1

+ G

d−2

and

= G

d−1

+ b

(1 − q)(b

d−1

+ G

d−2

Exercise 4.13 Derive a continued fraction expansion for C

valley

(x, y, q) that

also works for the case d = ∞.

Exercise 4.14 This exercise relates to Example 4.40.

(1) Write a program in Mathematica or Maple (or any other language) to

create the compositions of n that avoid 213 and 132, respectively. (Hint:

in Mathematica, you can either create the respective compositions re-

cursively, eliminating those that contain the pattern of interest when

appending a 1 or increasing the rightmost part, or use built-in functions

to create all compositions of n and then extract those that avoid the

respective pattern).

(2) Use your program to create the compositions of n =6, 7,...,10 that

avoid 213 and 132, respectively. Find a bijection between these compo-

sitions for n =6, 7,...,10.

(3) For n =11, there is one more composition that avoids 213 than there

are compositions that avoid 132. Explain why the bijection you have

found in Part (2) no longer works and identify the 213-avoiding compo-

sition(s) that are not in one-to-one correspondence with a 132-avoiding

composition.

Exercise 4.15 Find the generating function for the number of compositions

of n with m parts in N that avoid the pattern 1332.

Exercise 4.16

∗

A pattern τ = τ

···τ

of length n is a word that contains all

the letters 1, 2,...,max

. Prove that the number of patterns of length n is

given by (see A000670 in [180])



k=1



j=0

(−1)





(k − j)



k=1

k!S(n, k),

where S(n, k) denotes the Stirling numbers of the second kind (see Table A.1)

which count the number of ways to partition a set of n elements into k

nonempty subsets.