THESiS

Q CU-i

This is to certify that the
dissertation entitled

PATI'ERN AVOIDANCE IN SET PARTITIONS AND

 

 

a COMPOSITIONS
I 2%
>— 4-
I C0 ’3?
< C *- 1 presented by
I «S (‘1)
119-5
21' 5 'fi
9 _.

Adam M. Goyt

E

has been accepted towards fulfillment
of the requirements for the

Ph.D. degree in Mathematics

 

 

 

W/

Major msor’ 3 Signature
Mate, Hg], (Q 00?“

Date

 

MSU is an afiinnative-action, equal-opportunity employer

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/07 p:ICIRC/DaleDue.indd-p.1

 

 

PATTERN AVOIDANCE IN SET PARTITIONS AND COMPOSITIONS
By
Adam M. Goyt

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Department of Mathematics

2007

ABSTRACT
PATTERN AVOIDANCE IN SET PARTITIONS AND COMPOSITIONS
By
Adam M. Goyt

We consider pattern avoidance in set partitions and compositions as natural
extensions of pattern avoidance in permutations. We enumerate pattern avoiding
set—partitions, even and odd pattern avoiding set partitions, and generalized set
partitions patterns. The generalized set partitions patterns are then used to en-
code set partition statistics. We continue our focus on set partitions statistics by
considering distributions over pattern restricted sets. These distributions give nice
q-analogues of the Fibonacci numbers, which are then shown to satisfy q-analogues
of many Fibonacci identities. We finish by considering a poset of restricted com-
positions. We show that this poset is shellable and use shellability to determine
its Mobius function. We then show that the Mobius function and the zeta func-
tion are both rational, and determine generating function in commuting variables

according to the type of the composition.

ACKNOWLEDGMENTS

I would like to thank my wife, Aletha M. Lippay, whose patience and loving
care are, without a doubt, the reason I was able to accomplish this. I would also
like to thank my advisor, Professor Bruce E. Sagan, for his patient guidance. This

work would not have been possible without his wonderful support and great energy.

iii

TABLE OF CONTENTS

LIST OF TABLES ........................................................... v

LIST OF FIGURES ......................................................... vi

INTRODUCTION ........................................................... 1

CHAPTER 1

AVOIDANCE OF PARTITIONS OF A THREE-ELEMENT SET ............ 4
1.1 Introduction .......................................................... 4
1.2 Double Restrictions ................................................... 6
1.3 Higher Order Restrictions ............................................ 12
1.4 Even and Odd Set Partitions ......................................... 13
1.5 Generalized Partition Patterns ....................................... 19
1.6 Set Partition Statistics ............................................... 25

CHAPTER 2 ‘

SET PARTITION STATISTICS AND Q-FIBONACCI NUMBERS .......... 33
2.1 Equidistribution of ls and TI) ......................................... 33
2.2 Distribution over IIn(13/ 2) ........................................... 34
2.3 q-Fibonacci Numbers Past and Present ............................... 35
2.4 q-Fibonacci Identities ................................................ 39
2.5 Determinant Identities ............................................... 48
2.6 Other Analogues ..................................................... 52

CHAPTER 3

THE MOBIUS FUNCTION OF A COMPOSITION POSET ................ 56
3.1 Introduction ......................................................... 56
3.2 The Mobius Function of Cd .......................................... 58
3.3 Shellability and the Mobius Function ................................. 61
3.4 Rationality ........................................................... 68
3.5 Generating Functions in Commuting Variables ....................... 78

BIBLIOGRAPHY ........................................................... 82

iv

LIST OF TABLES

Table 1 Enumeration of partitions restricted by 3 patterns ................... 13
Table 2 Enumeration of even and odd partitions restricted by at least 2 patterns 18

Table 3 List of p, q-Fibonacci Identities ...................................... 54

LIST OF FIGURES

Figure 1: 137/26/45 ......................................................... 31
Figure 2: D ................................................................. 49
Figure 3: CL-labeling of [(Lbb. aabbab] ........................................ 66
Figure 4: Zg-Q ................................................................ 74
Figure 5: M)?g ................................................................ 77

Introduction

The focus of this dissertation is pattern avoidance in set partitions and com-
positions. We wish to give some background on paterns in permutations, as this is
the birthplace of our topic. To do this, we will introduce some notation and basic
definitions, to be made more rigorous in the next. chapter.

Let [n] = {1, 2, . . . ,n} and let Sn, be the symmetric group on [n]. We write our
permutations in one line notation, so the permutation 132 represents the permu-
tation 0 6 5'3 with 0(1) 2 1, 0(2) 2 3, and 0(3) = 2. If 7r 6 5k. and 0 6 Sn, then
one says that a copy of 7r occurs in 0 as a pattern if there is a subsequence 0’ of 0
such that replacing the smallest element of 0’ by 1, the next smallest by 2, and so
on, results in the permutation 7r. For example in the permutation 15243, 154 is a
copy of the pattern 132. If there are no copies of a particular pattern in 0 6 Sn,
then we say 0 avoids the pattern. For a set of permutations R Q S 1:7 let Sn,(R) be
the set of permutations in Sn, which avoid every permutation in R.

In 1979, Knuth published a proof that the cardinality #371931) = Cn, the
nth Catalan number. He was interested in the enumeration of this set because the
permutations which avoid the pattern 231 are exactly the stack sortable sequences.
The fact that such a lovely enumeration emerged from a natural computer science
question sparked other people’s interest. The next natural question was the enu-
meration of 871(0) for any 0 E 33. It was shown that #Sn,(0) 2 Cu for any
0 6 $3. In 1985, Simion and Schmidt published a paper, in which they enumer-
ated Sn(R) for any R C_: S3 as well as the odd and even permutations avoiding
patterns in R, and the number of involutions avoiding all patterns in R. The study
of patterns in permutations exploded from this point, and is currently an area of
very active research.

In 1996, Klazar defined a notion of pattern avoidance in set partitions involving

restricted growth functions. More recently, Sagan gave a definition of pattern

avoidance in set partitions, which uses a block form of partitions. Let [In be
the set of partitions of the set [it] and R Q “It: Similar to the definition for
permutations, let IIn(R) be the partitions of [n], which avoid every partition in
R. In a 2006 preprint, Sagan enumerates Hn(7r) for any 7r 6 H3. In the second
chapter we enumerate IIn(R) for any R Q H3, the even and odd partitions of
[n] avoiding R, and the partitions in II” avoiding generalized partition patterns.
Generalized partition patterns are analogues of generalized permutation patterns
introduced by Babson and Steingrl’msson and are patterns in which certain blocks
must be adjacent. Babson and Steingrimsson introduce the generalized patterns
as a way to classify Mahonian statistics on permutations. See the next paragraph
for a. definition of statistic and Mahonian statistic. In most cases, generalizing a
pattern does not. change the enumeration of its avoidance. In two cases we were
unable to obtain a closed form for the enumerations and hence used exponential
generating functions to handle them. Finally, we show that set partition statistics
can be written in terms of generalized partitions.

The second chapter deals with distributions of set partition statistics on pattern
restricted sets of set partitions. A statistic, p, on a set S is a function p : S —> P,
where I” = {0, 1, 2, . . ..} When studying statistics, we often consider the generating

function

Z (IMO),

065'

A Mahonian statistic 7' has generating function

2 (17(0) = [72.]ql := [72,]q[n — 1]q - - - [1]q,

UESn

where [qu 2 1+ q + (12 + . . . + qk _1. Notice that if we let q = 1 then [qu : k

and [n]ql = 'n!. For this reason, we say that [n]ql is a q-analogue of nl. It is known

that #Hn(13/2) = 2n _ 1 and #11,,(13/2, 123) = By, the nth Fibonacci number.
In chapter three we consider the generating functions for distributions of statistics

ls and rb introduced by VVachs and White and obtain nice q-analogues of 271— 1

and Fn.

It turns out that the q—analogue of 2" — 1

is exactly the same as the generating
function for the number of integer partitions with distinct parts of size at most n-l.
We are able to prove this relationship by bijection. The q-analogues of Fn are
closely related to q—analogues of Fn first discovered by Carlitz and Cigler. We
also prove this relationship using a bijection. The exciting part is that we were
able to take these q—Fibonacci numbers, Fn(q), and prove many q-analogues of
Fibonacci identities bijectively by adapting tiling scheme proofs of Benjamin-Quinn
and Brigham et. a1. We also use a method due to Linstrom and popularized by
Gessel and Viennot to prove a q-analogue of the Euler-Cassini identity using lattice
paths and determinants of the Toeplitz matrix foan(q).

Recently, Stanley and Bjorner produced an analogue of Young’s lattice for
compositions, called C. In the last chapter, we consider a restricted version of
this lattice. That is, we consider all compositions, which avoid the composition
d + 1. This simply restricts the part sizes of the compositions to at most n. We
call this new lattice (In. The lattice Cd has a nice Mobius function. We show
that Cd is CL-shellable and show that n(u,w) = (—1)'”'+"’“’l (‘5) dm where Iu| is
the sum of the parts of u and (fibrin is the number of d—normal embeddings of
u in it). we also provide a combinatorial proof of the same fact. we show that
the series Z3 = ((0 w)u 8 it), where C is the zeta function of Cd, and the series
111.50 = ,u(u, w)u®w, where p is the Mobius function of Cd, are rational by showing

that they are accepted by a finite state automota. Finally, we determine norm and

length generation functions for C and n.

Chapter 1
Avoidance of Partitions
of a Three-element Set

1. 1 Introduction

If f : S —> T is a function from set S to set T, then f acts element-wise on objects
constructed from S. For example, if (1.1a2...an is a permutation of elements
of S then f(a1a2...an,) = f(a1)f(a2) . ..f(an). Also, define [it] to be the set
{1,2, . . . ,n} and [k, n] to be the set {13, k +1,...n}.

Suppose that S Q Z is a set with #S = n, then the standardization map
corresponding to S is the unique order preserving bijection St S : S —* [n]. For
example if S = {2, 5, 7, 10} then StS(2) = 1, StS(5) = 2, StS(7) = 3, and
S t 5(10) = 4. “When it is clear from context what set the standardization map is
acting on, we will omit the subscript S.

Let p = alag . . . a k E S k be a given permutation, called the pattern, where S k
is the symmetric group on k letters. A permutation q 2: blbg . . . bn, 6 Sn contains
the pattern p if there is a subsequence q’ = billy? . "bile of q with St(q’) = p.
Otherwise q avoids p. For example the permutation q = 32145 contains 6 copies

of the pattern 213, namely 324, 325, 314, 315, 214, and 215. On the other hand q

avoids the pattern 132. For R Q S k, let
Srn,( R) = {q 6 Sn, : q avoids every pattern p E R}.

The problem of enumerating Sn,(R) for R Q S3 was considered by Simion and
Schmidt [37]. We will consider the analogous problem for patterns in partitions.
A partition 7r of set S Q Z, written 7r l- S, is a family of nonempty, pairwise

disjoint subsets BI, 82, . . . , Bk of S called blocks such that U5: 1 B,- = S. We

write 7r = Bl/BQ/.../Bk and define the length. of 7r, written €(7r), to be the
number of blocks. Since the order of the blocks does not matter, we will always

write our partitions in the canonical order where

min 31 < min 82 < < min Bk.-

We will also always write the elements of each block in increasing order. For
example, 137/ 26/ 45 l- [7] has length 3.
Let
II", = {7r l- [71]}

be the set of all partitions of [n]. Suppose 0 is a set partition of length m and 7r is
a partition of length 8. Then 0 contains 7r, written 7r Q 0, if there are 6 different
blocks of 0 each containing a block of 7r. For example 0 = 137/26/45 contains
7r = 2/37/ 5 but does not. contain 7r’ = 2/37/6 because 2 and 6 are in the same
block of 0.

Let 7r 6 IIk be a given set partition called the pattern. A partition 0 E IIn
contains the pattern 7r if there is some 0’ Q 0 with S t(0’ ) = 7r. Otherwise 7r avoids
0. For example 0 = 137/26/45 contains six copies of the pattern 7r = 14/2/3,
namely 17/2/4, 17/2/5, 17/4/6, 17/5/6, 26/3/4, and 26/3/5. It is important to
note here that when looking for a copy of 7r in 0, the order of the blocks does not
matter. On the other hand consider the pattern 7r’ = 1/234. To be contained in 0
the copy of the block 234 of 7r’ must be contained in a block of size three or larger.
The only such block of 0 is 137. It is impossible to find an element smaller than

1, so 0 does not contain a copy of 7r’. For R Q IIk. let

IIn(R) = {0 E 117;, : 0 avoids every pattern 7r E R}.

The extensively studied set of non-crossing partitions may be defined as the

fir“- a 1.11

set IIn(13/ 24). It is known that #Hn( 13/ 24) = Cn, where C71, is the nth Catalan
number [31], [39]. For a survey of results about. non-crossing partitions see Simion’s
paper [36].

Sagan [34] has provided enumerative results for IIn,(R) when #R = 1. In
the spirit of work done by Simion and Schmidt on permutation patterns [37],
we will enumerate IIn(R) for #R 2 2. We then define the sign of a partition
and enumerate the set of signed partitions of [n] avoiding particular patterns. In
section 5, we define generalized patterns analogous to the generalized permutation
patterns of Babson and Steingri’msson [2], and provide enumerative results for
those. Finally, we will show how these generalized partition patterns can be used

to describe set partition statistics.

1 .2 Double Restrictions

In this section we will consider the case of #IIn(R) where #R = 2. Given a set
partition 0 = 81/82/ . . . /Bk f- [n], let 00 = Bf/Bg/ . . . /Blcc be the complement
of 0 where

B§:={n—a+1:aEBi}.

For example if 0 = 126/ 3/ 45 then 00 = 156/ 23/ 4. The following result is obvious,

so we omit the proof.

Proposition 1.2.1 (Sagan) For n 2 1,

“71(06) = {7T6 2 7T 6 1171(0)},

#Hn(0c) = #Hn(0).

The following Lemma is an immediate consequence of Proposition 1.2.1.

Lemma 1.2.2

#nrn,(12/3,123) = sauna/23,123)
#Hn(1/2/3~12/3) = #Hn(1/2/3,1/23>
#nn,(12/3.13/2) = #nn(1/23,13/2).

There are 10 different sets R with elements from I13 and #R = 2, so by Lemma
1.2.2 there are seven different cases to consider. Note that #IIO = 1 by letting the
empty set partition itself. Since any partition in I11 or I12 cannot possibly contain
a partition of [3], we have #IIO(R) = 1, #II1(R) = 1 and #II2(R) = 2 for all
R Q H3. The fact that #II3 = 5 implies that #II3(R) = 3 for any R C 113, with
#R = 2. Hence, it suffices to consider it 2 4 in the following results.

A partition 0 l- [n] is layered if0 is of the form [1. i]/[i+1,j]/[j+1, k]/ . . . /[€+
1,71]. An example of a layered partition is 0 = 123/ 4/ 56/ 789. A partition 0 is a
matching if #B 3 2 for every block B of 0.

We will use the following results of Sagan [34] repeatedly, so we state them

HOW.

Proposition 1.2.3 (Sagan)

Hall/W3)

Hn(12/3) = {0 = 81/82/ . . . /Bk : minBi = ifor each, i, and

{0 : l(0) S 2}, (1.1)

[k + 1,n] Q Bi for some i}, (1.2)
IIn(13/2) = {0 : 0 is layered}, (1.3)

Hn(123) = {0 : 0 is a matching}. E] (1.4)

“1p-u « l ‘I

Proposition 1.2.4 For all n 2 3,

th,(1/2/3,12/3) = {12...n,1/23...n,13...n/2},

Proof: Let 0 E IIn(1/2/3,12/3). By (1.1), 0 may have at most two blocks. If
€(0) = 1 then 0 = 12.. .71. If [(0) = 2 then by (1.2), we must have [3,n] C Bi for
i = 1 or 2. Cl

Proposition 1.2.5 For all n 2 1,

I—In(1/2/3,13/2) = {020:12...kf/(A7+l)(k+2)...n
for some k E [72]},

#HnU/2/3913/2)

Tl- .

Proof: If 0 E IIn(1/2/3,13/2) then 0 is layered by (1.3), and 6(0) 3 2 by (1.1).

Hence 0 is of the form described above. The enumeration follows immediately. Cl

Proposition 1.2.6

{12/34.13/24.14/23} n = 4,

Hn(1/2/3.123) =
0 n 2 5.
3 n = 4,

#Hn.(1/2/3,123) =
0 n > 5,

Proof: If n 2 5 and 0 l- [n], then [(0) 2 3 or 0 has a block of size 2 3 by the
Pigeonhole Principle. Thus by (1.1) and (1.4), IIn(1/2/3, 123) = (Z) for n, 2 5. The

case n = 4 is easy to check. Cl

Proposition 1.2.7 For all n 2 3,

IIn(1/23,12/3) = {12...n,1/2/.../n,1n./2/3/.../n—1},

#Iln(1/23,12/3) = 3.

Proof: Let 0 = Bl/Bg/.../Bk avoid 12/3. If k = 1 then 0 = 12...n, which
avoids 1/23. Similarly, when k = n, we have 0 = 1/2/ . . . /n, which avoids 1/23.
If k = n — 1 and n E 8,; for i 2 2 then Bl/Bi is a copy of 1/23. Thus n 6 BI
and 0 = 1n/2/3/.../vn — 1. If 1 < k < n — 1 then, by (1.2), we must have
{n —- 1, n} Q B, for some i, and there is at least one more block. Hence 0 contains

a copy of 1 / 23, and so this case can not occur. Cl

Proposition 1.2.8 For all n 2 1,

l'In,(12/3,13/2) = {0 =1/2/.../k — 1/k(k + 1) . . .n,
for some 13 E [72]},

#11,.(12/3, 13/2) = n.

Proof: Suppose 0 = 81/32/ . . °/Bk E Hn(12/3,13/2). Then by (1.2) we have
i E B,- for each i and exactly one of the B,- contains [1: + 1, it]. From (1.3) we have
that 0 must be layered. So [k + 1,71] 6 B k, and B k = [k‘, n]. Thus there is exactly
one 0 E IIn(12/3,13/2) of length A: for each k E [n]. C]

9

Proposition 1.2.9 For all n 2 1,

II-n,(12/3,123) = {0 = Bl/Rg/ . . . /Bk' : min Bi = i,
and k = n — 1 or n},

#Hn(12/3,123) = Tl.

Proof: Assume 0 = Bl/BQ/.../Bk E IIn(12/3.123). Then by (1.2) and (1.4),

k: = n — 1 or n. The result follows. Cl

Let Fn, be the nth Fibonacci number, initialized by F0 = 1 and F1 = 1. A com-
position of an integer n is an ordered collection of positive integers n1. n.2, . . . , "k
such that n = 72.1 + 71.2 + . . . + "k' The n, are called parts. It is easy to see that

Fn, counts the number of compositions of n with parts of size 1 or 2.
Proposition 1.2.10 For all n 2 0,

Hn(13/2, 123) = {0 : 0 is a layered matching},

saunas/2.123) Fn.

Proof: Any 0 E Hn(13/ 2, 123) must be layered by (1.3) and a matchng by (1.4).

There is a bijection between the compositions of n with parts of size 1 or 2
and the partitions of [n] that are layered matchings. If 0 = 81/82/ . . . /Bk E
I'In(13/2,123), then we map 0 to the composition n = 72.1 + n2 + . .. + "k with
”i 2 #Bi- [3

From the results above we know that
#Hn<1/2/3.13/‘2) = #Hllr(12/3913/2) = wan/3.123) = n,

10

and we have a very nice description of the elements in each of these sets. It
is interesting to note that one gets similar results when avoiding certain sets of

permutations in S3.

Proposition 1.2.11 (Simion, Schmidt) For every n 2 1,

#Sn(123, 132,231) = #Sn(123,213,312) = n.

#.s,-,,(132,231.321) = #Sn,(213,312,321)=n.

And:

qESn(123,132,231) q: (n.n—1,....k+1,k—1,k—2,...,2,1,k),

q E Sn,(123, 213,312) q = (n,n — 1,. . . ,k + 1, 1,2,3,. . . ,k),

(1 E Sn(132,231,321) q = (n. -— 1,72. - 2, . . . k + I,n.,k., k - 1,... ,2, 1),

Hill

q E Sn,(213,312,321) q = (k — 1,...32,1,n.n — 1,. ..,k).l:l

The Fibonacci numbers also occur when avoiding permutations.

Proposition 1.2.12 (Simion, Schmidt) For every n 2 1,

#Svn_(123,132, 213) = F”. El

There is a simple map (I) : II" —> Sn, given by sending 0 = 81/82/ . . . /Bk. to
BkBk —1---Bl- For example, @(1/23/4/56) = 564231.

Proposition 1.2.13 The map (I) restricts to a bijection from the set IIn(I3/2, 123)
to the set Sn(123, 132,213).

11

Proof: We may describe q E Sn(123, 132,213) recursively. To avoid the patterns
123 and 213, we must have q—1(n) S 2. If q—1 (n) = I then the remaining positions
form a permutation in Sn _ 1(123, 132,213). If q—1(n) = 2 then q—1(n — 1) =
1, otherwise there will be a copy of 132 in q. The remaining positions form a
permutation in Sn _ 2(123,132,213).

Suppose 0 = 31/32/ . . . /Bk E Hn(13/2,123), then 8;, = {n} or {rt—1,72,}.
The permutation <I>(0) thus begins with n or n — 1, n. Inductively, one can see
that this restriction of the map (I) is well defined.

To prove that the restricted (I) is a bijection we provide its inverse map. Let
q = q1q2...(1n, E Sn,(123, 132, 213) then we say that {I}; is a descent if (7k > (Us + 1.
Let D = {(11‘1,(["2,...,q"[} be the set of descents of q, with i1 < i2 < < i6.
Then

(I)_1(q)=(111+1(1;[+2...(m/([,-€_1+1...q,-£,/.../q1...q,j1.

For example (D—1(564231) = 1/23/4/56 because its descent set is D = {3, 4. 6}.

we now show that (If1 is well defined. Every (1 E Sn(123, 132,213) must have
a descent in at least one of its first. two positions. After this initial descent there
may be no more than one position between any two descents. Thus the blocks
of (P-1(q) will have size at most 2, and from the description of the elements of
Sn,(123, 132,213) above (IV—l(q) will be layered.

The fact that (I) and (D—1 are inverses follows easily from the descriptions of

the maps. Cl

1.3 Higher Order Restrictions

We begin, as with double restrictions, by reducing the number of cases. The

following Lemma is a consequence of PrOposition 1.2.1.

12

Lemma 1.3.1

#H72.(1/2/3,12/3,123) = #11,,(1/2/3, 1/23,123),
#H'n.(1/2/3~12/3s13/2) = #Hn(1/2/3,1/23.13/2),

#IIn(12/3,13/2,123) = #II..(1/23,13/2,123).D

The results for #HMR) where #R = 3 are easy to prove. Table 1.3.3 de-
scribes these sets and gives their enumeration for n 2 4. The following proposition

describes #IIn(R) for #R 2 4. We omit the simple proof.

Proposition 1.3.2 For R Q 113 with #R 2 4 and n 2 4,

0 if {1/2/3, 123} Q R,
#Hn(R) =
1 else. Cl

Table 1: Enumeration of partitions restricted by 3 patterns

 

 

 

 

 

 

 

 

 

 

 

 

R 1172(3) #Hn(R)
{1/2/3,12/3,13/2} {12...n,1/23...n} 2
{1/2/3,12/3,123} 0 0
{1/2/3,13/2,123} {12/34} 1if7i==4

Q) OifnZ 5
{1/2/3,1/23,12/3} {12...n} 1
{12/3,13/2,123} {1/2/.../n,1/2/.../n—2/(n—1)n} 2
{1/23,12/3,13/2} {123...n,1/2/.../n} 2
{1/23,12/3,123} {1/2/...,/n1n/2/3/.../n——1} 2

 

1.4 Even and Odd Set Partitions

In this section we will consider the number of even and odd partitions of the set
[n], which avoid a single pattern of length three. A partition 0 l- [n] with l (0) = It

has sign,

Even partitions 0 satisfy sgn(0) = 1, and odd partitions 0 satisfy sgn(0) = —1.

We will use the following notation:

Ell-HUT)

{0 l- [n] : sgn(0) = 1},

OIIn(7r) = {0 l— [n] : sgn(0) = —1}.

The following follows directly from the definitions.

Lemma 1.4.1 The sign of0 is the same as the sign of 06. Thus #EIIn(12/3) =
#EIIn(1/23) and
#OH72.(12/3) = #()II-n,(1/23). I]

We will use the following result of Sagan [34] repeatedly, so we state it. now.

Define the double factorial by

(2i)!!=1-3-5m(2i—1).

Proposition 1.4.2 (Sagan)

#Hn(1/2/3) = 2""1. (1.5)
#nn(12/3) = (9+1, (1.6)
#117,,(13/2) = 2"”. (1.7)

["53] ($991)” CI (1.8)

i=0

#Hn.(123)

We now consider single restrictions. By Lemma 1.4.1 there are only four cases.

Proposition 1.4.3 For all odd n 2 1,

14

#Enn(1/2/3) = 1.

#011,.(1/2/3) = 2" — 1 —- 1.

For all even n 2 2,

#En,,(1/2/3) = 2” — 1 — 1,

#()Ilrz(1/2/3) = 1.

Proof: By (1.1), any 0 E I'In(1/2/3) must have [(0) S 2. If n is odd then a
partition of length 1 will be even and a partition of length 2 will be odd. There
is only one partition of length 1, and #OIIn,(7r) + #El'ln(7r) = #Hn(7r) for any
pattern 7r. Thus, the result holds for odd n by (1.5). The proof for even n is

similar. Cl

Proposition 1.4.4 For all odd n _>_ 0,

#Enn.(12/3l = —] +1.

 

_ n2]
#Onn(12/3l = — -

Proof: By ( 1.2) we have. for 72. odd,
n. — 3
_2—

. _ 2 _ 2
#EH71.(12/3)=1+ k'Z-:0(2k+1) = 1+ £171 = [fl-EL] +1,

15

and by (1.6)

. 2 . 2
#onn(12/3) = ('2') +1— ("7—1) — 1 = [L] .

The proof for even it is similar. Cl

Proposition 1.4.5 For all n. 2 I,
#onn(13/2) = #EIIn(13/2) = 2" * 2.

Proof: By (1.7) it suffices to give a sign reversing involution U) : Hrz.(13/2) —>
IIn(13/2). By (3), 0 E IIn,(13/2) is layered, so it is ofthe form 0 = 81/82/ . . . /Bk,
where either Bk = {n} or Bk 3 {n}. Let

81/82/ . . . /B,,. _ 1 o {n} if Bk = {n},
81/82/“°/Bk—{"'}/n if Bk 3 {n}.

do) =

Notice that vf)(0) is still layered for any 0 E IIn,(13/ 2), so it! is well defined. And,
ll) is its own inverse because it either moves n into the block preceding it if {n} is
a block and into its own block otherwise. Also, v") changes the Sign of 0 by either

increasing or decreasing the length of 0 by 1. Cl

Proposition 1.4.6 For all n 2 1,

tail
#EH71,(123) = Z )(4i+2)!!
'J
0

1

N

I'—

It
0 41: + 2
(41)

(I)

71
4

i

16

Proof: Any 0 E IIn(123) is a. matching. If i blocks of 0 have 2 elements each and
the remaining blocks are singletons then 0 has i + (n — 2i) 2 n — i blocks. Thus
sgn(0) = (—1)"‘ — (n. T i) = (—1)i. So the even and odd counts are obtained by

taking the appropriate terms from (1.8). Cl

Table 1.4.7 gives the results for #EIIn(R) and #OIIn(R) where #R Z 2 and
n 2 4. We prove the enumeration of EIIn(13/2.123) and OHn,(13/2.123) as an

example and leave the rest to the reader.

Proposition 1 .4.7

[Fm/2] for n E 0, 1 (mod 6),

#Enn.(13/2~ 123) Fn/2 for n E 2. 5 (mod 6),
[Fn/2] for n E 3, 4 (mod 6).
[Fn / 2] for n E 0, 1 (mod 6),
#OIIn(13/2. 123) = Fn/2 for n E 2, 5 (mod 6),

[Fin/2] for n. E 3, 4 (mod 6).

Proof: Let 0 = Bl/BQ/.../Bk E IIn,(13/2,123). Then Bk 2 {n} or {n —
1,n}. If Bk = {n} then Bl/BQ/ . . . /Bk _ 1 is a layered matching of [n — 1] and
sg11(Bl/BQ/.../Bk _1) = sgn(0). If Bk = {n — 1. n} then 81/32/ . "/Bk _1
is a layered matching of [n — 2] and sg11(Bl/82/.../Bk _ 1) = —sgn(0). Thus

we have that

#EIIn(13/2,123) = #EII.,,_1(13/2,123)+ #()n,, _ 2(13/2,123).

Similarly,

#Onn(13/2,123) = #()I_In_1(13/2,123)+ #EIIn _ 2(13/2.123).

17

Table 2: Enumeration of even and odd partitions restricted by at

least 2 patterns.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

R #Enn(R) #OHn(R)
{1/2/3,12/3} 1 for n odd 2 for n odd
2 for 77. even 1 for 77. even
{1/2/3,13/2} 1fornodd n—lfornodd
n — 1 for it even 1 for 71. even
{1/2/3,123} 3forn=4 0
0 for n 2 5
{1/23,12/3} 2 for n odd 1 for n odd
1 for n even 2 for n even
112/3, 13/2} 172/21 W21
{12/3,123} 1 n —1
{13/2,123} [Fn/2] fornE0,1 [1771/2] fornE0,1
(mod 6) (mod 6)
Fn/2 fornE2,5 Fn/2 fornE2,5
(mod 6) (mod 6)
[Fn/2] fornE3,4 [Fm/2] fornE3,4
(mod 6) (mod 6)
{1/2/3,1/23,12/3} 1 for 72. odd 0 for n odd
0 for it even 1 for n even
{1/2/3,12/3,13/2} 1 1
{1/2/3,12/3,123} 0 0
{1/2/3,13/2,123} 1 0
{1/23,12/3,13/2} 2 for n odd 0 for 77. odd
1 for n even 1 for n even
{1/23,12/3,123} 1 1
{12/3,13/2,123} 1 1
{1/2/3,1/23,12/3,13/2} 1 for 77. even 0 for 77. odd
0 for it odd 1 for n even
{1/2/3,1/23,12/3,123} 0 0
{1/2/3,12/3,13/2,123} 0 0
{1/23,12/3,13/2,123} 1 0
{1/2/3,1/23,12/3,
13/2,123} 0 0

 

Now induct on n. To show that the proposition is true when 0 S n S 5 is easy.

18

 

This leaves us with twelve cases to check for the inductive step. We will show one
of them. It is easy to see that Fn is odd unless n E 2, 5 (mod 6).

Suppose that n E 4 (mod 6). Then we have

#_EIIn(13/2,123) = #EHn_1(13/2,123)+#OII.,,_2(13/2,123)

= LFn,—1/21+F-—2/2
Fri—1"l'l’Fn—2
2
= [Fn,/2].Cl

 

1.5 Generalized Partition Patterns

Babson and Steingrimsson [2] defined generalized patterns for permutations. These
were patterns in which certain elements were required to be consecutive. General-
ized permutation patterns were used to describe permutation statistics and classify
Mahonian statistics. In this section we will define a similar notion for set partition
patterns and consider the avoidance case. In the next section we will show that
generalized partition patterns can be used to describe set partition statistics.

Recall that if 0 = 81/82/. . '/3k is a partition then the blocks are written
in such a way that min 81 < min 32 < < min Bk- This gives us a well
defined notion of adjacency of blocks, where we consider 8,- as being adjacent to
both 8,; __ 1 and B,- + 1. Consider the partition 0 = 147/25/36 and the pattern
7r = 13/ 2. Suppose now that a copy of 7r must appear in adjacent blocks. Then
17/ 2 is still a copy, but 17/ 3 is not. We may also have the blocks in the restricted
copy of 13/ 2 in the opposite order making 25/4 a copy of it in 0. We will denote
7r with the adjacency restriction by the generalized pattern p = 13|2. In general,
we will denote block adjacency using a vertical bar.

Recall that the elements of a block are put in order by size, which gives us a

way to consider adjacent elements. Now, suppose we want to find a copy of 13/ 2

19

in 0 = 147/ 25/ 36, but we require that the elements that represent 1 and 3 in this
copy are adjacent. In this case 14/ 3 is a copy of 13/ 2, but 17/ 6 is not, since 1 and
7 are not adjacent in their block. We will denote this by the generalized pattern
p =13 / 2. In general, we will denote element adjacency by placing an are over the
elements, which must be adjacent.

If p is a generalized pattern, then the notation II", (p) denotes the set of parti-
tions of [n], which avoid p. Similarly, if R is any set of generalized patterns then
IIn(R) is the set of partitions of [n], which avoid all generalized patterns in R.

we are interested in enumerating the IIn(R) where R is a set of partitions of
[3] at least one of which contains an adjacency restriction. It turns out that the
adjacency restrictions do not actually restrict most of the original patterns. This

is summed up in the next lemma.

Lemma 1.5.1 The following are true for generalized patterns:

Hall/W3) = Hn(1l2/3) = Hn(1/2l3l = Hn(1|2|3),
Hell/23) = Hri(1l23) = Hell/23) = ”MHZ/{3).
11.7,,(13/2) = finds/2) = 11,,(13l2) = nn1’sl2),
nn(123) = 11,,(123) = and?) = n..,,(i\23),
n,.,(12/3) = H,,,(f2/3).
name = mafia).

Proof: We will only prove the second line as the others are very similar. First
we show that IIn(1/23) = II-n,(1]23). It is obvious that if a partition 0 l- [n]
contains a copy of 1|23 then it contains a copy of 1 / 23. So it will suffice to show
the other containment holds. Let 0 = BI/ 82/ . . . / Bk f- [n] contain a copy a / be
of 1/23. Suppose a E 8,; and h, c E Bt. If s < t then the block Bt _ 1 exists and
min Bt __ 1 < min 815 S l) < c. Letting d = min 3t _ 1 gives a copy d/bc of 1|23 in
0. If s > t then Bt + 1 exists and min Bt + 1 S a < b < c. Letting e = min Bt + 1
gives a copy e / be of 1|23 in 0. We remind the reader that the adjacent blocks of

the copy of 1|23 may appear in either order in 0.

20

Now we will show that H7),(1 / 23) = IIn(1/ 23). Again, it suffices to show that
if 0 l— [n] contains a copy of 1 / 23 then it contains a copy of 1/ 23. Given a copy
a/bc of 1 / 23 in 0, if b and c are not adjacent in their block 8 then let (I be the
minimum of all of the elements of B which are larger than b. Tints a/bd is a copy

of 1 / 23 in 0. These two observations can be used to prove the remaining equality.

El

Let R be a set of generalized patterns, and let S be the same set with adja-
cency restrictions dropped. That is if, for example, 1|23 E R then 1/23 E S, and
S only contains patterns without adjacency restrictions. Lemma 1.5.1 says that
unless 12|3 or I2|3 E R, we have that. IIn(R) = IIn(S). However, since we have
[171(12l3) =
IIn(I2 I3), we only need to consider cases when 12|3 E R. The sets IIn(S) were
enumerated in sections 2 and 3, so we need only enumerate the sets Hn,(S U {12]3})
where
S Q H3 — {12/3}.

Proposition 1.5.2 Let S Q I13 - {12/3} then IIn(SU {12|3}) = l'In(SU {12/3})

unless S = Q) or {123}.

Proof: The cases where #S 2 2 follow automatically from those with #S = 1
and Lemma 1.5.1. The three cases with #S = 1 are very similar, so we will only
prove the statement for S = {13/2}. Let 0 E IIn(13/2,12]3), then 0 must be
layered. Thus any copy of 12/ 3 in 0 easily reduces to a copy of 12|3 as in the proof

of Lemma 1.5.1. Cl

The following lemma describes the elements of II,-,,(12|3).

Lemma 1.5.3 We have 0 E IIn(l2|3) if and only if whenever a block Bt of 0

satisfies #Bt _>_ 2, then

#Bt—l = 1and#Bt+1 =1.

21

Furthermore, if Bt + 1 = {a} then a < b for every b E Bt — {min 3t}-

Proof: First we show that 0 = Bl/BQ/ . . . /Bk E Hn(12|3) can be described as
above. Let #Bt Z 2 and suppose that Bt _ 1 contains at least 2 elements and
let a < b be the two smallest elements of Bt _ 1. Let. c < d be the two smallest
elements of Bt- By the definition of canonical order, a < c. If b < d, then ab/d is
a copy of 12]3. If b > (1, then cd/ b is a copy of 12|3 another contradiction. The
proof that #Bt +1 = 1 is similar. The single element in Bt +1 must be larger
than c by definition. If it is larger than any other element of Bt we will again have
an unwanted copy of 12]3.

Now, suppose that 0 E IIn has the structure described above. Then it is

straight forward to show that 0 cannot contain a copy of 12]3. C]

First we will consider the case where S = (D in Proposition 1.5.2. Let on =

#Hn(12|3) and let
u

f(.r) = 2 an?!

n20

be the corresponding exponential generating function.

Proposition 1.5.4 For n 2 2,

"—271—2
an.=(L.n__1+1+ Z ( k >an,—k-2
k=1 '

with the initial conditions a0 = 1 and a1 = 1, and f (.1?) satisfies the differential
equation

,”=y'+y(em-—1)+e$.

Proof: That #II0(12|3) = #II1(12|3) = 1 is obvious. Let 0 = 81/82/ . . . /Bk E
IIn(12|3). Either #31 = 1 or #81 Z 2. If #31 = 1 then, by the definition of

canonical order, 81 = {1}. Clearly any 12|3 avoiding partition of the set [2,72]

22

will still avoid 12|3 if we prepend the block {1}. This gives the first term of the
recursion.

Now suppose that #31 2 2, then either 0 = 12 . . . n or not. The case where
0 = 12 . . . n is counted by the 1 in the recursion. If 0 ¢ 12. . . n. then, by Lemma
1.5.3, we must have 82 = {2}. If k. of the elements from [3 n] are in 81, then the
remaining n — k — 2 elements must form a 12l3 avoiding partition. This establishes
the recursion.

Using the recursion to produce the differential equation satisfied by [(1') is
routine and is left the reader. Cl

The substitution y = MEI/2 simplifies the equation to

,. 3)

u = u(c" — — + e‘r/2.

Using Maple, we obtain the solution

.r/2) ,.r/2)+

ll = (71- 15(26’ + C2 ' AIR“

21¢_—3(2eI/2)/[{fl(r¥F/2ezI/2)(l.lf—

21(\/_—3((?Jl/2)/I\/__3(28$/2)C‘T/2(1.1‘,

for certain constants C1 and C2, where [71(3) and Kn,(z) are the modified Bessel
functions of the first and second kinds respectively. There are known combinatorial
interpretations for certain Bessel functions. See, for example, [3] and [26]. It
is unlikely, however, that there is a combinatorial interpretation for the Bessel
:13/2

functions appearing in the exponential generating function f (.17) = ”€- , since

K \/-_—3(e‘r/ 2) is not well defined as a formal power series.

23

Is.‘

Now, we turn our focus to 11,),(123, 12[3). Let bn, = #Iln,(123, 12|3) and

be the corresponding exponential generating function.
The proof of the following proposition is very similar to the proof of Proposition

1.5.4 and is omitted.

Proposition 1.5.5 For n 2 3,
0n, = bn _ 1 + (n — 2)!)72. _ 3

with the initial conditions b0 = 1, bl = 1, and b2 2 2. Also, g(:r) satisfies the
differential equation

ym : y” +1!!! + y. D

Using Maple, we obtain the solution
y = Dle‘r/Z/li(1/4 + .1: + DQcI/2Bi.(1/4 + r)+
D30”2 (Ai(1/4 + :r) / Bi(1/4 + r)e_‘T’/2dr—

/Ai(1/4 + JT)(3—m/2(l.l.‘8l(I/4 + 1.)) ,

for constants D1, D2, and D3, where Ai and Bi. are Airy functions.

It is not terribly surprising that Airy functions appear, since these functions
are closely related to Bessel functions, and
Iln(123,12|3) is a subset of the set Hn,(l2|3). There do not seem to be any ex-
isting combinatorial interpretations of Airy functions. There is also unlikely to
be a combinatorial interpretation of this generating function due to the fact that

Ai(1/4 + :17) is not well defined as a formal power series.

24

For completeness we will consider the cases where odd and even set partition
avoid generalized set partitions. As before only the cases 011MB) and El'lniH)
where R = {12]3} or {123,12l3} are new.

Let oan = #OHn.(12l3) and can = #EHn(12|3). Let obn = #011n(123, 12l3)
and ebn = #EHn(123,12|3). The following propositions easily follow from the
recursions above. We let x be the truth function, where X of a statement is 1 if
the statement is true and 0 if the statement is false.

Proposition 1.5.6 For n 2 2,

. . — 2 .— 2
0a” = Can — 1 + Xi" "'9 CW") + Z?— 2, I even (72 l )oan - 2 - l

n—2 n—2
+Zz=1,10(m( l )ean—2—l?

and

n — 2 n — 2 )
1:2,leven( l )(’a'72.—2-l

n—2 n—2
+21: 1, lodd( l )0(z.n__2_l.Cl

can, 2 can _ 1 + x(n is odd) + 2

Proposition 1.5.7 For n 2 3

01)" = 0b,, __ 1 + (n — 2)ebn _ 3,

and

cl)", = ebn _ 1 + (n — 2)obn _ 3. D

1.6 Set Partition Statistics

Carlitz [16, 17] and Gould [27] were the first to give versions of the q-Stirling num-
bers of the second kind. In [33], Milne introduces an inversion and dual inversion
statistic on set partitions, whose distributions over partitions of [n] with 11: blocks
produce these two q-Stirling numbers of the second kind. Later, Sagan [35] intro-

duced the major index and dual major index of a set partition, whose distributions

25

produced the same two q—Stirling numbers of the second kind. At around the same
time, Wachs and White [40] investigated four natural statistics, which they called
lb, ls, rb, and rs, again producing the same two q-Stirling numbers of the second
kind. Other statistics of interest are the number of crossings, nestings and align-
ments of a partition, see for example [14], [20], or [29]. In this section we will show
that all of these statistics can be described in the language of generalized partition
patterns.

we will need some more notation. Consider the pattern 7r = 1 / 23. If we are
looking for a copy of 7r in 0 = 137/ 26/ 45, but we want the element representing 1
in the copy to be the minimum of its block then 1/45 is a copy, but 3/45 is not.
We will represent this generalized pattern by A1 / 23. And in general, we will denote
such a generalized pattern by putting an are over the first element of the block, in
which we want the minimum to occur. In the same fashion, if we want the element
representing 1 in a copy of 1 / 23 to be the maximum in its block, then we denote
the pattern by f / 23. If we want the element representing 1 in a. copy of 1 / 23 to
be both the minimum and the maximum of its block, then we denote the pattern
by TIA / 23.

In the sequel, if we say p is a pattern then ,0 may or may not have adjacency
restrictions. Let p be a pattern and 0 E II”. Then p will be treated as a function
from fin to the nonnegative integers by letting p(o) be the number of copies of p

in a. If we have patterns p1.p2, . . . ,pg then

(p1+ p2 + . . . + pg)(o) = [21(0) + [02(0) + . . . + p£(0').

We begin with the inversion statistic. Let or = Bl/Bg/ . . . /Bk
E 117;, and b 6 Bi' We will say that (b, Bj) is an inversion if b > min Bj and i < j.
Define the inversion number of a, written inv(a), to be the number of inversions

in a.

26

We may calculate inv(o) by summing, over all elements b E [n], the number of

inversions of the form (b. Bj). This oliiservation leads to the next Proposition.

Proposition 1.6.1 For (my a 6 11,1,

Proof: We will show that there is a one-to-one correspondence between inversions
and copies of 13/ 2. Let (7 : Bl/BQ/.../Bk.. Let b 6 Bi and (b, Bj) be an
inversion. If a = min Bi and c = min Bj then (b, Bj) corresponds to the copy ab/c
of f13/ A2. C(imversely, if nb/c is a copy of A13/ 2, then a = min Bi and c = min B j
where i < j since a < 0. Also, b > c = min Bj. Thus, the copy ab/c yields the

inversion (b, Bj). Cl

Let 0 = Bl/Bg/ . . . /Bk be a partition. We will say that (b, Bi + 1) is a descent
of 0 if b 6 Bi and b > min Bi + 1. Let (1,: be the number of descents of 0 in block

Bi Then the major index of (7 is

k —1
maj(o) = 2 id]; = (11 + 2032 + . . . + (k — 1)(lk _ 1.
i=1

Notice that each descent (b. Bi + 1) contributes i to the major index.

Proposition 1.6.2 For any or E II”,
maj(o) = (A13IA2 + A1/ A24] T3)(0).

Proof: Let a = 81/32/ . . . /Bk and b 6 Bi- Let p1 =13] A2 and p2 =A1/ 24] 73.
We will first show that (1), Bi + 1) is a descent if and only if b represents the 3 in
a copy of p1, or, for i 2 2, the 4 in a copy of p2. Then we will show that each

descent (b, Bl" + 1) contributes i to the right hand side.

27

Let (b, Bi + 1) be a descent. If a = min B,- and c = min 81+ 1 then ab/c is a
copy of p1 where b represents the 3. If additionally i Z 2 and we let (1 = min Bj
where j < i then d/ab/c is a copy of p2, in which b represents the 4. For the
converse, let ab/c be a copy of p1, then c = min Bi + 1 for some i, and (1), Bi + 1)
is a descent. Similarly, a copy d/ab/c of p2 with c = min Bi + 1 for some i Z 2
produces the descent (b, B,- + 1).

If (b, Bi + 1) is a descent, then there is exactly one copy of p2 with b repre-
senting 3, since the 1 in p1 must be represented by a = min Bi: and the 2 must
be represented by c = min Bi + 1. Now, if b represents the 4 in a copy of p2
then the 2 must be represented by a 2 min Bi: and the 3 must be represented by
c = min Bi + 1. But now the 1 may be represented by the minimum of any block

appearing before Bi- So the total contribution of the two patterns is 1+ (i — 1) = i.

E]

Let a = 81/32/ . . . /Bk and b E Bin The dual of a descent is an ascent, which
is a pair (b, Bi __ 1) with b > min Bi _ 1. Note, it is true that each b 6 Bi forms
an ascent because of the canonical ordering. So, we define the dual major index
to be

A k

major) = Z (i_1)(#3,).
i: 2

The dual inversion number of a, written inv(o), is the number of pairs (b, Bj)
such that b 6 Bi, b > min B j, and i > j. we will call these pairs dual inversions.
Clearly, inv(0) = maj(o) for any (7 E II", since every ascent causes i — 1 dual

inversions.

Proposition 1.6.3 For any a E II-n,

A A AAAA

inv(a) = maj(0) =( 1/ 2+ 1/ 23)(0).

Proof: Let a = B1/32/ . . . /Bk' The proof that 162(0) 2

28

( 1/ 2+ 1/ 23)(0) is similar to the proof of Proposition 1.6.1. The only difference
here is that the minimum of a block can represent the b in a dual inversion (b, Bj).

This is taken care of by the first pattern. Cl

Wachs and White [40] define four natural statistics on partitions by encoding
the partitions as restricted growth functions. Their statistics are lb, ls, rb, and
rs. which stand for left bigger, left smaller, right bigger and right sn'ialler. For
consistency, we will define these statistics without introducing restricted growth
functions, and hence the names of the statistics may seem a little unusual.

Leta = B1/Bg/ . . . /Bk- If I) 6 Bi, then we will say that (b, 81-) is:

o a left bigger pair of a if i < j, and b > min Bj,

o a left smaller pair of a if i > j and b > min Bj,

o a right bigger pair of 0 if i < j and b < max Bj,

o a right smaller pair of a if i > j and b < max Bj.

Let 112(0), ls(a), rb(o), and 729(0) be, respectively, the number of left bigger
pairs, the number of left smaller pairs, the number of right bigger pairs, and the
number of right smaller pairs in a.

Notice that (b, 3]) is a left bigger pair if and only if it is an inversion of a, and
(b, 3]) is a left smaller pair if and only if (b, 8]) is a dual inversion of 0. Thus we

have from Propositions 1.6.2 and 1.6.3 that.

A A

15(0) = ( 13/ 3(0),

[3(0) =(/1/T2+A1/A23)(0).

29

we will now consider the other two statistics.

Proposition 1.6.4 For any a E II”,
rb(c7)=(r1/A23\+/13/f24\+fll/A2A +32/ hiya).

Proof: Let a = 81/82/ . . . /Bk° The pattern A1 / A23A counts right bigger pairs
(b, Bj) where b = min Bi and #Bj Z 2. The pattern A13/ A24? counts those pairs
where b 74 min Bi and #B]- 2 2. The other two patterns correspond to the same

two cases when #8 j = 1. C]

The proof of the following proposition is similar to the proof of Proposition

1.6.4 and is omitted.

Proposition 1.6.5 For any 0 E II",
rs(0) = (if / 3+ “157 “23(0). C]

There has long been interest in non-crossing partitions. Recall that the non-
crossing partitions are those in the set Hn(13 / 24) for some n. Non-nesting parti-
tions may be described as those in the set Hn,(T;1/ 23). Note that this definition
of a non-nesting partition is not the only one. Klazar [30] defines non-nesting
partitions as those in the set IIn(14/ 23).

Recently, however, there has been increasing interest in counting the number
of crossings or nestings of a partition. In [20], Chen et al. show that the crossing
number and nesting number are symmetrically distributed over II” by giving a
bijection between partitions and vacillating tableaux. In [29], Kasraoui and Zeng
give an involution of 1177,, which exchanges the crossing number and the nesting

number while keeping another statistic, the number of alignments of two edges,

fixed.

30

We will describe each of these statistics and show that they too may be trans—
lated into the language of patterns.

Let 0 = Bl/BQ/ . . . /Bk E 1117,. We may rewrite 0 as a set P Q [n] x [n] in
the following way. If a,b E B,- and there is no 0 E Bi such that a < c < b then
(a,b) E P. If Bi = {(1} then ((1, d) E P. It’s easy to see that P uniquely represents
a. We will call P the standard representation of a.

Let A be a family {(i1,j1), (-i2,j2)} Q P. we will say that A is:

o a crossing if i1 < i2 < 11 < jg,

o a nesting if i1 < i2 < jg < j1,

e an alignment if i1 < 11 3 i2 < jg.

For example, the following diagram represents a = 137/ 26/ 45, where an edge

connects elements if they are adjacent in a block.

Figure 1: 137/26/45

Notice that the pair {(1,3),(2,6)} forms a crossing, the pair {(2,6),(4,5)}
forms a nesting and the pairs {(1, 3), (4, 5)} and {(1, 3), (3, 7)} each form an align-
ment of two edges.

Let cr(0) be the number of crossings in o, ne(o) the number of nestings, and
al(o) the number of alignments.

The following proposition is an easy consequence of the previous definitions.

31

Proposition 1.6.6 For any a E Hn,

cr<o> = (Es/21x0).
ndfl =(figfixw,

ma)=ubfi+fifi+fiwflu

Let a E I17), and P be the standard representation of 0. Consider the family A =

{(i1,j1), (ig,jg), . . . (i1..jk)} Q P. Then A is a k-crossing if i1 < ig < <17]; <
j1 < jg < < jk' We say A is a k-nesting if 7:1 < ig < < ik <
jk < lie _1 < < j1. Let crk(o) be the number of kt-crossi11gs of o and

nek(o) be the number of lit-nestings of a. Notice that or = crg and me = neg. The

following proposition describes these two statistics as patterns.

Proposition 1.6.7 For any a E II",

gym =(uk+u/uk+a/Hykfimmn,

2mmm = MOM/2Qk—U/ijw+1DW)D

32

Chapter 2
Set Partition Statistics and
q—Fibonacci Numbers

2.1 Equidistribution of ls and rb

In this chapter, we are interested in the distributions of set partition statistics
on IIn(13/2) and IIn,(13/2,123) and the resulting q-analogues of Zn and Fn. Of
the known set partition statistics, only the left smaller, Is, and right bigger, rb,
statistics of W'achs and White [40] seem to give interesting distributions on these
sets.

For a statistic p on a finite set S, the distribution of p over S is

Z qp(s)_

sES

Hence, the coefficient of (1k is the number of s E S with p(s) = k. The follow-

ing theorem shows that the statistics rb and ls are equidistributed over the sets

“71(13/2) and Hn(13/2,123).

Theorem 2.1.1 For any n,

7r 6 Hn(13/2) 7r 6 Hn(13/2)

and

Z (11.9(7r) = Z qrb(7r).

71' e Hn(13/2, 123) 7r 6 anus/2,123)

Proof: Given a set partition 7r = Bl/Bg/ . . . /Bk E IIn(13/2), let the comple-
ment of it be the partition rc 2 BE/ . . . /B§/Bf, where Bf = {n— b+l : b E Bi}-

33

Notice that taking the complement reverses the order of the blocks since 7r is lay-
ered. Clearly complementation is an involution, and so bijective. So it suffices to
show that it exchanges ls and rb. This easily follows because the block order is
reversed and minima are exchanged with maxima. Also, complementation does

not alter the block sizes and so restricts to a map on IIn(13 / 2, 123). C]

2.2 Distribution over Iln(13/2)

Define

Anlq) = Z qrbbr),
it E IIn(13/ 2)

It will be useful to think of the rb statistic in the following way. Let 7r =
Bl/Bg/ . . . /Bk be a partition and mj = max Bj. For each element b E Bi with
i < j and b < mj, we have that (b, Bj) is a right bigger pair. The number of
right bigger pairs of the form (b, 13]) will be the contribution of Bj to rb. When

restricted to layered partitions the contribution of Bj is
Z #8,: = min Bj — 1.
i < j

The generating function An,(g) is closely related to integer partitions. An inte-
ger partition A = (A1, Ag, . . . , )‘kl of the integer d is a weakly decreasing sequence
of positive integers such that 23]“: 1A1 = d; the ’\i are called parts. We let
[A] = :53: 1A1. Denote by Dn _1 the set of integer partitions with distinct

parts of size at most n — 1. It is well known that

For the rest of this chapter we will refer to a set partition as just a partition and

34

an integer partition by its full name.
For the following proof it will be more convenient for us to list. the parts of an
integer partition in weakly increasing order. Let 6,5 : H72(13/ 2) —> Dn _ 1 be the

map defined by

¢)(Bl/Bg/.../Bk) = (A1,A2,...,)\k_ 1),
where ’\j = Z; = 1 #3,;

Theorem 2.2.1 The map (5 is a bijection, and for 71' E IIn(13/2), rb(7r) = |O(7r)|.

Hence,
n — 1 .
1472(0) = H (1+ (11")-
i = 1
Proof: Given /\ = (A1,Ag, . . . , ’\k _ 1) consider, for 1 S j g k, the differences

dj = Aj — Aj _ 1, where A0 = O and ’\k. = ii. If /\ E Dn—l then we have
dj > O for all j. And if (p(r) = /\ then the dj give the block sizes of 7r. But
since it is layered, it is uniquley determined by its block sizes. So ab is bijective.

Since ’\j = 27- < j #Bi is the contribution of Bj +1 to rb (and B1 makes no

contribution) we have rb(7r) = |o(7r)| as desired. C1

The proof of Theorem 2.2.1 will be useful for proving q-analogues of Fibonacci

identities.

2.3 q-Fibonacci Numbers Past and Present

We turn our focus to the distribution of rb over Hn(13/2,123). As remarked in
the introduction

#nn(13/2,123) = Fn.

35

The distribution of rb over 1171(13/ 2, 123) gives a nice q-analogue of the Fibonacci

numbers. Let

Fn((1) = Z (17")(7r).
7r 6 Hn(13/2,123)

Proposition 2.3.1 The generating function Fn(q) satisfies the boundry condition

F0(q) = 1, F1(q) = 1, and the recursion
Fnlq) = (1” "' an. _ 1((1) + (1"— 2Fn _ 2(a)-

Proof: Let it E IIn(13/2, .123). Since 7r is a matching it must end in a block
of size one or of size two. If it ends in a singleton then the singleton is {n},
which contributes n — 1 to rb, and the remaining elements form a partition in
Hn _ 1(13/2,123). Similarly the doubleton case is counted by the second term of

the recursion. El

We now introduce the q-Fibonacci numbers of Carlitz and Cigler and explore
their relationship to the q-Fibonacci numbers as defined above. Let BS}, be the
set of binary sequences 13 2 b1 . . . bn, of length n without consecutive ones. It is well
known that
#BS}; 2 En + 1. In [18, 19], Carlitz defined and studied a statistic on BS};

as follows. Let p : BS}, —> N be given by

p(fi) = p(b1 . . . bn) 2 b1 + 2bg + . . . + nbn,

and define

Fwi‘ ((1) = 2 (1pm-
{3 e as}, _ 1

Carlitz showed that F7501) satisfies F0K(q) = 1, F1K(q) = 1, and

F75 (q) = Ff. 1(0) + q" ' 1F€L 2(a)-

7

36

Cigler [22] defined his q-Fibonacci polynomials using Morse sequences. A Morse
sequence of length n is a sequence of dots and dashes, where each dot has length
1 and each dash has length 2. For example, V = o o — — o— is a Morse sequence
of length 9. Let MS" be the set of Morse sequences of length n. Each Morse
sequence corresponds to a layered partition where a dot is replaced by a singleton
block and a dash by a doubleton. So, #MS-n, = Fn.

Define the weight of a dot to be a: and the weight of a dash to be yqa +1
where a is the length of the portion of the sequence appearing before the dash.
Also, define a weight w : MS” —> Z[;1:,y,q] by letting w(z/) be the product of
the weights of its dots and dashes. For example, the sequence above has weight

(I)(I)(yq3)(:e/(15):If(y(18) = :v3y (116- Let

Fg(.r,y,q) = Z 100/).
l/ E AISn

Cigler shows that FnC(;r, y, q) satisfies FOC(;1:,y, q) = 1,

F1006, y, q) = .17, and
Fr? (1:, y (1) = 17175. 1(1', 31, q) +2110" _ 1Fn.— 2(1‘» 31. (1)-

Note that F7§(1,1,q) = F,{‘(q). In fact, Cigler [21, 22, 23, 24] studied more gen-

1

eral q-Fibonacci numbers satisfying the above recursion with yqn " replaced by

t(yqn " 1), where t is an arbitraty nonzero function. One could apply our method

to such q-analogues, but we chose t to be the identity for simplicity.

Proposition 2.3.2 For all n 2 0,

n ,
F'ni‘l) = (1(2) Fri.fl (1M)-

37

Proof: It suffices to construct a bijection 11-77(13/2, 123) <—> BS" _ 1 such that.
if 7r 4—> ,8 then T‘b(7'l') = ('2') — p(ti).

Let it E Hn,(13/ 2, 123) be mapped to the binary sequence .13 = b1 . . .b,;, where
bi = 0 if i and i + 1 are in separate blocks and bi = 1 otherwise. For example,
1 /2/34/ 56 <—> 00101. We first show that this map is well defined. Suppose 7r H
b1 ...bn, where bi = 1 and bi + 1 = 1 for some i, then i, i + 1, and i+ 2 must be
in a block together. This contradicts the fact that the blocks may only be of size
at most 2. The fact that this map is a bijection is straightforward.

Now, suppose that it +——> [3 and {3 2 b1 . . . b". If every element of it is a maximum
of its block, which is the same as saying that every block is a singleton and that.
bi = 0 for all i, then rb(vr) = 2?;11i = ('2'). If bi = 1 for some i then i and
i+ 1 are in the same block. Thus. i is no longer a block by itself and so no longer
contributes rb. When i and 13+ 1 were in different blocks, {i} contributed i— 1 to
rb, so we have lost. i — 1. Also, since i and i + 1 are now in a block together, the
block containing i + 1 cannot be put together with i to form a right bigger pair.
This reduces the contribution of {i i + 1} by 1. These are the only changes made

when bi = 1. Thus, each time bi = 1 we reduce rb(1/2/ . . . /n) by i and hence,

rb(r) = (’2’) — Z 2': (g) — p(r’3)- E1

i:b,~=1

V
In order to describe the relatirmship between Fn(q) and "((17,341) we w111

define a weight, w on the partitions in H7-1,(l3/2, 123). Let

u} : Hn,(13/2,123) —> Z[.r.s, q],

38

with w(7r) = 3(31/32/ . . . /B,,) = [1]“: lira). where

1, minBi—l If 3:1,
wlB-i)= q # ,

Wmin B,- — 1 if #3,: = 2.

Now, let

Fn.(417,y,(l)= Z LUCK").
it e 11,,(13/2, 123)

Let s(7r) be the number of singletons of it, (1(a) be the number of doubletons of 7r.

It is easy to see directly from the definitions that

F7711, y, (1) = Z 173(71')yd(7r)qrb(7r).
it E II,,(13/2,123)

The proof of the next proposition is omitted since it parallels that of Proposition

2.3.2 using the bijection [171(13/2, 123) <—+ I'llSn mentioned above.

Proposition 2.3.3 We have that

TI:

FTI.(iF~.y»(1) = (1(2)FT(LJ(E: ya 1/(1)' D

2.4 q-Fibonacci Identities

We now provide bijective proofs of q-analogues of Fibonacci identities. Many of the
proofs in this paper are simply q-analogues of the tiling scheme proofs of Fibonacci
identities given in [4, 15]. It is impresive that merely using the rb statistic on
Hn(13/2,123) gives so many identities with relatively little effort. We will state
our identities for F'n(.1:, y, q), but one can translate them in terms of 177,9(412, y, q) or

Fyéqq) using Propositions 2.3.2 and 2.3.3.

39

Theorem 2.4.1 For n 2 O

2)1 . .
Fn+2('£ y (1)= I"‘(1(+2 )+ Z il'j3/(I(j F.” J-(I(1J+2,yql+2,q).
j— — 0

Proof: There is exactly one partition in II.” + 2(13/ 2, 123) with all singleton
blocks and the weight of this partition is 1:" 7' + 2q(n 3— 2). The remaining partitions
have at least one doubleton. Consider all partitions where the first doubleton is
{j + 1, j +2}. There are exactly j singletons preceding this doubleton contributing
:rJ q(%) to the weight of each partition. The doubleton contributes weight qu . The
remaining blocks of these partitions form layered matchings of [j + 3, n + 2]. we
may think of these as being layered matchings of [n — j] where the contribution of
each block to the rb statistic is increased by j + 2. Hence, these contribute weight
Fn __ j(.r qu + 21: mi”, q). Thus, the contributed weight of the partitions, whose
first doubleton is {j + 1, j + 2}, is
( j + 1

2 )F (FI1J+2.y(1"+2.(1)-

41?" .1111 n ._ j

Summing from j = 0 to n the weighted count of partitions whose first doubleton
is {j + 1, j + 2} and adding the weight of the partition with all singletons proves

the identityD

Theorem 2.4.2 For n 2 0,

n
F212, + ital/.11) = Z 17y" (H (J +1>172“, ”(11,21 +1,y1,21 +1”),
i=0
and
"—1 2' 1 2' 1
:2 ”WA/1U _1.)F2n—2j—1(HIJ+ .qu+ ,q).
j =0

40

Proof: If 71' E Ilgn +1(13/2,123), then 7r must have at least one singleton.
Consider all partitions with first singleton {2j + 1}. This block must be pre-
ceded by j doubletons, which contribute quJiJ _ 1) to the weight. The singleton
{23' + 1} contributes .1'q2J to the weight. The remaining 2n — 2 j elements form
a layered matching of [2 j + 2,271. + 1]. As in the previous proof, we may think
of these as being elements of H2n _ 2j(13/ 2, 123) where the contribution of each
block to rb is increased by 2j + 1. This portion of our partition will contribute
an _ gJ-(quJ + 1, yq2J + 1, q) to the weight.

This proves the first identity. The proof of the second identity is similar, and

hence omitted. Cl

Theorem 2.4.3 For all n 2 0 and m. 2 0,

Fm + 11(37» 9*!) = me-Fs 111(1)Fn.-(J7(1m» 9‘17"} (1)
+ 11117" — lFm _ 1(.1.'. y, (1)17” _ 1(.1:qm + 1, mm + 1, (1).

Proof: Every it E Um + n.(13/29 123) has {171, m + 1} as a block or does not.
If 7r has {771, m + 1} as a block then the blocks prior to this block form a parti-
tion in Hm _ 1(13/ 2, 123). This contributes Fm _ 1(.-r.y.q) to the weight. The
doubleton {1a, m + 1} has weight qu _ 1. The remaining blocks form a partition
in H[m + 2,771+ "1(13/2, 123). The contribution of each block in this partition to
the rb statistic is increased by m + 1, so this portion of the partition contributes

m + 1 m + 1

Fn _ 1(;1:q ,yq q) to the weight. Thus, the sum of 111(71') over all 7r in

Hm + ”(13/2, 123) with doubleton {m, m + 1} is

77"+1,y"7'1’+1,(1).

2111"" _ 1F,” _ {(1, .11. (1)1}, _ 1(4111 (1

41

If 7r E Hm + 11(13/ 2, 123) does not have {m, m+1} as a block, then we can split
7r into a partition of [m] and a partition of [m + 1, m + n]. By a similar argument,

the sum of 112(71') over all it in Hm + n(13/2, 123) without the block {m, m + 1} is
Fm(~17~, 311(1)]:1'1i-"1ms Wm: (I)- D

Theorem 2.4.4 For n _>_ 1,

, ‘2 .—
anF2'1'1.+l(Ial/a(/) + 312(1 7? 1

= F," + 10?» y (1)Fn, + 1(1rqn', ya". (1)

n+2 n+2

Fn _ 1(17, y, q)Fn _ 1(zvq ya a)-

Proof: Notice that each partition 7r E l'Ign +1(13/2,123) has one of three
configurations: Either the element 71 + 1 is in its own block, is in a block with n,
or is in a block with n + 2.

‘We put together the right hand side of the identity by considering the set
II" + 1(13/2,123) x H.” + 1(13/2, 123). A weighted count of the elements (7r1,7rg)
of this set by increasing by n the contribution to rb of each block in fig is
E, + 1(17, y. (1)1711, + 1011”. ya": (1)-

Let II’n+1(13/2,123) >< II’n+1(13/2,123) be the set of those ordered pairs
(711 fig) such that 7r1 ends in a doubleton and fig begins with a doubleton. There is
a bijection between II’n + 1(13/2,123)xfl’n+ 1(13/2,123) and [In _ 1(13/2,123)x
IIn _ 1(13/ 2, 123) by removing the last block of 7T1, removing the first block of TF2,
and reducing each element of fig by 2. The weighted count of such pairs (7r1, 7rg) is
312(12” — 1Fn_ 1(17. :1. (1)Fn _ 1(qu + 2, W" + 2,11)-

Thus,

42

Fn, + 1(17. 11,101}, + 1071": 1111"; (1) -
y2q2n -— an _ 111.. y, (1)17” _ 1(.rq" + 21W” + 2,11)

is the weighted count of (r1, 7rg) E Hn + 1(13/2, 123) x [In + 1(13/2.123), where
7r1 ends with a singleton or 7rg begins with a singleton or both. In any of these
three cases we create a partition in IIgn + 1(13/ 2, 123) by removing the singleton
at the end of 7r1 or the singleton at the beginning of fig, concatenating the parti-
tions and increasing the elements of mg by n. The statement about the possible
configurations of an element of Hg” + 1(13/2,123) shows that this construction

gives a bijection

n2.,,1+1(13/2,123) <—» II,,+1(13/2,123) >< I17,,+1(13/2,123)

;,1+1(13/2,123) >< H,’n+1(13/2.123).

In each case we lose a singleton block, whose weight is .rq". Thus, we must multiply
an, + 1(.17,y.(1) by .rq" to obtain an appropriate weighted count of 112,, + 1(13/ 2, 123).
El

Theorem 2.4.5 For n. 2 0, Fn(.r. y. q)Fn + 1(.r, y.q) =

2
1 1 . . .
Z]- : Uri/J (1 Fn _ jl-w’ . 11111 1(1)Fn _ leq-1 + 1,qu + 11(1)-

Proof: Consider an element (711 fig) E IIn(13/2. 123) XII" + 1(13/2, 123) with
7r1 = A1/Ag/ . ../Ag, and fig = B1/Bg/ . ../Bm. Search through the blocks in
the order B1, A1, Bg, Ag, . . . and find the first singleton block.

If the first singleton is some Ai = {j} then B1,. . . , Bi are all doubletons, and
j is odd. There are (j — 1)/2 doubletons at the beginning of 7r1 and (j + 1)/2
doubletons at the beginning of fig contributing qu(J _ 1l2/2 to the weight. The
singleton block A27 has weight 1qu _ 1. The remaining 6" — i blocks of 7r1 form a
layered matching of [j + 1.11,], which has weighted count Fn _ -(.'1:qJ,qu,q). The

J

43

remaining 1n — i blocks of fig are a layered matching of [j + 2, n + 1], which has
weighted count Fn _ j(;qu + 1,qu + 1, q). So the weight contributed by all pairs

(r1, r2) with Ai = {J} as the first singleton is

[.13 J _ . . . . 1
(1 :ry-’-Fn -— J(J*(1J.y(1j.(1)Fn, _ Jl-W/J +1.y(1j + ,q)-

If the first singleton is some Bi = {J + 1} then j is even, and by similar
arguments, the weight contributed by all such pairs (7r1, 71g) with B,- = {j + 1} as

the first singleton is

[El
:17qu F", _ ji~l’(1‘]al/(1Ja(I)Fn,—— J(<N1J + 1, qu +1.11)-

Sumrning over all possible cases gives the identity above. 1:]

The identity Fn = 2k > 0 (n I A.) relates the Fibonacci numbers Fn, to the
binomial coefficients (2). For convenience we assume that (713) = 0 if k > 71..
To state a q-analogue of this identity, we need the q-binomial coefficients. The

q-binomail coeflicients are

I.

 

n
Define = 0 if k: > n for convenience. Carlitz [18] derived the following

k

identity using algebraic and operator methods. We will provide an alternate proof

using the relationship between layered partitions and integer partitions.

44

Theorem 2.4.6 (Carlitz) For n _>_ 0,

(n n—k.
Fn('l7y([)= :1,” —2fi'ykq (2-—)A (n—k)
1120 k

Proof: Let Hi,(13/2,123) be the set of 7r E Hn.(13/2,123) with exactly I:

doubletons. Thus we have

H,.1(13/2 123) =U Hi, (13/2,123),
2k 3 n

where U is the disjoint union. This implies that

Z 01(77) = Z :17" — 2193111: 2 qrb(7r)

71 e IIn(13/2.123) k 2 0 7r 6 H ,,(13/2 123)

It suffices to show that

k: (1'7'b(7r) 2 (1(71.) _ k(n _ k) 1,, _ k
W E “i 1(13/2, 123)

Let it E Hi ,,(13/2 123) with doubleton blocks B,I,B,2,...,B.,k. As in the

proof of Proposition 2.3.2 the maximum rb(r) is (3), and each doubleton 8,}. of

7r reduces rb by min B, .. This gives 11s that
'J

_ 1; - .
Z (1er) = Zq(2) Z} = 1mm Bl},
71 6 Hi ,(13/2 123)

where the first sum on the right hand side is over all possible choices of k doubletons

B- B- 8- Th 'olth‘ 1919" 111 (Til—”k;
,1, ,2,..., ,k. erlgi. an(s1(.,1seq1a .oq q

45

Z]; = 1n — min Bi]-

we?

 

Consider the map which sends 7r to the integer partition A = (A1, A2, . . . , Ak),

where )‘j = n — min 81]“ This is clearly a bijection Hig(13/2,123) —* ES __ 11

where E7]; _ 1 is the set of integer partitions with exactly k parts of size 3 n — 1

and consecutive part sizes differ by at least 2. It is well known that

-2 n — k
AeEk k

n. — 1
See Andrews" book [1] for a proof.

n ,. , - n. —— k
Thus, we have 2 )qrb(7r) = (1(2) _ Mn. _ I") . Cl

7r 6 Hi,(13/2, 123 k

Another identity involving binomial coefficients is F2,” 2 22 = 0 (21.)Fn _ k'

Theorem 2.4.7 For n. 2 0,

In, in + k " n , .. ,.
F2'n,(17191(1) = Z q( 2 )_ "k ,,r1.—A I,

k=0 k

n, _ ki‘ln + k1,“, (In + k‘

y, (1)-

Proof: Let A}: be the set of partitions 7r 6 H2,,(13/2, 123), which begin with
a partition of [n + k] having exactly k doubletons.

We claim that Hn(13/2,123) is the disjoint union of the Ak' First, we show
that each A k is nonempty for 0 g k S n. The proof is by induction on the number
of doubletons in 7r. The case where 7r has 0 doubletons is obvious. If 7r has 6
doubletons with the last doubleton B = {11,11 + 1} then we split this doubleton
forming a new partition 71’ with a and a +1 in singleton blocks. Now, by induction
there must be some t such that 71’ has exactly t of its doubletons in the first 71 + t
elements. If a > n+t then 7r also has exactly t doubletons in the first n+t elements.
If a S t then 7r has exactly t + 1 doubletons in the first 71 + t + 1 elements.

It suffices to show that each 7r 6 Hn(13/ 2, 123) is in exactly one Ak. Suppose

that 71 has exactly j doubletons in the first 71 + j elements. And suppose that

46

for some i > j, 71 also has exactly 1 doubletons in the first 71 +73 elements. This
means that there must. be exactly 1' — j doubletons consisting of elements from
[71+ j +1, n+1]. Since there are only .,-_ j elements in this set we have a contradiction.
This also proves the case where i < j. Thus, each partition 7r 6 HQn,(13/ 2, 123) is
in exactly one Ak'

Using Theorem 2.4.6 it is easy to see that

. ,. _ A _ n .
Z WU?) =(I( 2 ) II II it Uk FrL—k(‘1w(l,2+kf n+k ’q.) El
71' E A}; ’7

we conclude this section by finding a q-aualogue of

71—2
FII+F,,__1+ Z 171.271—2—k =2".
k=0

We provide a proof for a q-analogue involving F A (q) as this is the nicest pioof.

Theorem 2.4.8 For n, 2 0,

n. — 2 n n
F501) + anrl‘_1(q)+ Z F]? ((1)1121; + ‘3 H (1+ (11): H (1+ (1k).
11' = 0 j = k + 3 k =1

Proof: Let 1’3 2 ()1 ...bn, E 8311, where 357;, is the set. of binary sequences
of length n. We consider the same statistic that Carlitz did. Namely, {2(6) 2
2;: = 1 kbk. Clearly,

TI.

2: qpid): H (1+qk).

(3 E 887), k = 1

Now, we count in a different way. Separate all binary sequences with no con-
secutive ones into those which end in a one and those which end in a zero. Those

which end in a zero are counted by Bi ((1), and those which end in a one, must

47

have a zero preceding the one and are counted by q' 1‘ F ri\— 1(q).

Now, consider all sequences. in which the first time consecutive ones appear are
in positions k+l and k+2, for O S k 3 71—2. The binary sequence preceding these
ones is a binary sequence of length It, and it must end in a 0. Thus, the first. part is
counted by F AK (q). The two ones contribute (121‘ + 3 and the remaining n - k + 3
positions form a binary sequence Without restriction contributing Hj = k + 3(1 +

(1]). Putting these together and summing over A" gives the identity. [:1

2.5 Determinant Identities

In [22], Cigler proves a q-analogue of the Euler-Cassini identity,

. 'n.
Fn—l4n..+k'_FnFn+k—1=(—1)Fk—l'
we state his theorem without proof.

Theorem 2.5.1 (Cigler) Fork 2 1, the q-Fibonacci polynomials F,§'(JT, y, q) sat-
ibify

FC

n—l

(-I'~.I/q.r1)F,€’+ ktzxy. (1) - FS(I~ysq)FnC+k_ fine/(1,q)

, n. _ 7 _.
= (—l)nq(2)yn 1F£_1(;17.yqn,q).l:l

Cigler proves this identity twice. once by using determinants and once by adapt-
ing a bijective proof of Zeilberger and Werman [41]. we will prove a q-analogiie
of the Euler-Cassiiii identity for Fn(q) by using weighted lattice paths and their
relationship to minors of the Toeplitz matrix for the q-Fibonacci sequence. This
is a well known method of Lindstrom [32], which was later poimlarized by Gessel

and Viennot. [25].

48

Consider the digraph D = (V, A) where the verticies are labeled 0. 1. 2, . . ., and
the only arcs are from vertex 7). to vertex n+1 and from vertex n. to vertex n+2 for
all nonnegative integers n. The portion of the digraph consisting of the vertitcies

0, 1,2,. . . ,6 is pictured below. All arcs are directed to the right.

 

Figure 2: D

It is easy to see that the number of directed paths from (i to b in D is F b _ a'
Let the are from n. to n + 1, written 71(71—4: 1), have wieght w(n(n—.+ 1)) = 1m”.
Let. the are from n to n. + 2 have weight w('n.(n_i+ 2)) = yqn. Let p be a directed
path from a to b, written a i» b. We define the weight of p, written w(p), to be

the product of the weights of its arcs. It. is not hard to see that
. . a
SAP) = Fb _ (l(«lq am“. (1)..
I)

where the sum is over all paths p from a to b.
Suppose that U1 < 21.2 < < “k and “1 < 1‘2 < < 29A. are verticies in
D. We will think of the ”i, as starting points of paths and the “i, as endpoints of

paths. Let
p p p -

1 2
P = {”1 —* 'l’a(1)‘“2 —* "(11(2)‘ ' ' ' . “k —’ WM}

be a k-tiiple of paths from the it]; to the L‘J’, where a E S k’ the symmetric. group on
k elements. We Will let the weight. of such a k-tuple be w(P) = Hi __. 1w(pi). Let
sgn(P) = sgn((r), where sgn denotes sign, and consider all such k-tiiples of paths,

P. We have that

Z sgn(P)w(P)
P

49

‘LJ'H'

is equal to the kxk minor formed from rows 11.1, u2, . . . , “k and columns '01, ’02, . . . , "k
of the Toeplitz matrix pictured below. We label the rows and columns starting

with 0. For example, column 0 starts with F0(.r, 3], q) and the rest of the entries

are 0.
F0(17.y.(1) 171(17- :1}. (1) F207. .2]. (1) F307. 3141)
F _ 0 Fotrq, ya. (I) F1011. (1y, (I) F2(:I'q, yqs C1)
0 0 F0(-rq2. z/(12.q) 1710172. 31(12, (1)
.. I Z I I '- _i

 

 

We will say that. two paths are no-nerossing if they do not share a vertex.

Theorem 2.5.3 Let 21.1 < 11.2 < < "k and v1 < 1’2 < < ”I: be ver-
ticies in D. Let m+ be the sum of the weights of the noncmssing k-taples of
paths, P, from 2.1.1, 112. . . . , "k to 11.12, . . . yak, with sgn(P) = 1. Let m— be the
sum of the weights of the nonerossing k-taples of paths, Q, from 211,112, . . . ,uk to
v1.1.2, . . . ,vk, with sgn(Q) = —1. The k x k minor given by rows 111, ug, . . . , "k.

and columns 2:1,1'2. . . . , Pk of the Toeplitz matrix is equal to m+ — 771—.

Proof: We prove this by giving a weight-preserving, sign-reversing involution
on the k-tuples of paths where at least one pair of paths cross. Let kt-tuple P have
a crossing pair of paths. Let u )1, the starting point of path 17,31, be the smallest
starting point of any path which crosses another path. Let. 10 be the first vertex
shared by pil and another path 1),-j. Let 111-2 be the starting point of path p’j'
Exchange the portions of the 1),-l and 1),-2 starting at w. This produces a new
k-tuple of paths, Q, and is clearly an involution. Since the weight of the k-tuple
of paths is just the product of the weights of all arcs appearing in the k-tuple, the

weight is preserved. Finally, the permutation for P and Q differ by a transposition

so sgn(P) = —sgn(Q). Cl

The digraph D that we are making with is relatively restrictive as the next

theorem shows.

50

Theorem 2.5.4 Let m be the k X 1: minor of F consisting of rows a1 < "(L2 <
< “k. and columns v1 < 1'2 < < ""k- If W > v,- for some i then m = 0. If
u3 < ‘01 or iffor some i Z 0 andj _>_ 1 we have “i < aj and uj + 2 < v.1: + 1 then

m = 0.

Proof: If u.) > 2'.) for some i then there are no k-tuples of paths with startings
points u1,u2, . . . , “k and endpoints 11,122, . . . , ck. Thus m = 0.

Suppose that for some i and j we have vi < u j and uj + 2 < v,- + 1. Let p j?
pj + 1, and p]- + 2 be the paths starting at uj, “j + 1, andu]- + 2 respectively. The
endpoints of pj, p j + 1 and p j + 2 must appear after uj + 2. We may assume that
p j ends before p j + 1. In order to avoid crossing the path p j + 1, the path p j must
contain the vertex ltj + 1. Now. every vertex between a j + 1 and the endpoint of
p j lies on either p j or p j + 1. Since pj ends at. a vertex appearing after Uj + 2,
we must have that “j + 2 appears on pj or pj + 1. Hence, there is no noncrossing

k-tuple of paths and m = 0. Cl

There are two more cases to consider. The case where we have a k-tuple of
paths with starting points (1.1,'112,...,ak and endpoints '01. v2, . . . , ”k with 11.1 <
v1 < u2 < 1'2 < < “I; < I". is just the product

k
H Fri —11,Ij((1u’.‘-17»(lu’i.’/~(l)-
i = 1

The last case to consider is the case where 11.1 < 1.1.2 < 231 < 1:2 <
- < "I." _1 < “k < ck. _1 < ck. This case produces a block matrix with
2 x 2 blocks along the diagonal, whose determinant is just the product of the de-
terminants of the blocks. We may as well just consider the case of two paths with
“1 < u2 < v1 < '02. We will prove the special case where 1L1 = 0, u2 = 1, v1 = n,
and '02 = n + k, which will give us the q-analogue of the Euler-Cassini identity

discussed above. The general case is proved similarly.

51

Theorem 2.5.5 For n 2 0 and k 2 1,
Fn.(rv. y. (M), + k _ 1W, ya (I) - Fn, _ 1(1'61. yq. qun + 1,:(172 y (1)
, n+1
: (_1)-r2..q( 2 )yan _1(.rqn+1,yqn+1,q).
Proof: Clearly the left hand side is the minor given by rows 0 and 1 and

columns n and 11+ k. We will first show that. the weighted count of the noncrossing

pairs of paths is
n + 1 , ,
q( 2 )yan _1(.rq"’+1,yqn+1,q). Let p be the path starting at 0 and s

be the path starting at 1. The portions of p and s between 0 and n are unique,
since p must pass through all of the even verticites and 3 must pass through all
of the odd verticies. Thus if n is even the path p must stop at n, and if n is odd
then 3 must stop at n. Assume, without loss of generality, that p stops at n. Then
3 must contain the vertex n + 1 and must continue to the vertex n + 1:. Since p
stopped at n there is no restriction on the portion of s between n + 1 and n + k.
The paths between n + 1 and n + k contribute weight F k _ l(qu’ + 1, yqn + 1, q).
The first portions of p and s contribute q(n 3- 1)y"' to the weight. The product of
these gives the weight of all possible noncrossing pairs.

Now, if n is even then p goes from “1 to v1 and 3 goes from oz to 1:2, so the
sign of all noncrossing pairs is 1. If n is odd then p goes from “1 to 1:2 and 3 goes

from u2 to 1:1, so the sign of all noncrossing pairs is -1. Cl

2.6 Other Analogues

The q—Fibonacci numbers that are the focus of this paper come from two statistics,
which are equidistributed over the set Hn(13/ 2, 123). The TI) statistic proved most
useful for proving identities. The next natural question is whether the bistatistic
(ls,rb) also has nice propertites when considered on the set Hn,(13/2,123). The

answer is yes. Because the proofs of the p, q-Fibonacci identies are very similar to

52

.4.

 

the proofs above we will define the p. q-Fibonacci numbers and leave the proofs of
the identites to the reader.

We define

Fluff, 11.1).(1) = Z l,s(7r)yr‘l(7r)pls(7r)qrb(7r).
7T E “71(13/2, 123)

We will also need the p, q- binomial coe cient,

n—i+1_qn—i+1

p" - (1i

 

, k
k V_ i=1
p-q

One identity involving these p, q—Fibonacci numbers is

. ,. .. n _ ,. . _ ,. n — k
Fn('~'7~ ye Pa (1) = Z In _ 2" g,“ (pq)(2) Lin 1")
h 2 0 k

The proof is omitted as it is similar to that of Theorem 2.4.6

The following is a list of p. q-analogues of some well known Fibonacci identities.
Letting p = 1 gives the identites involving Fn,(.'1:, 3), q). The proofs are very similar
to the proofs given in this chapter. There are some cases where we may let at =
y = 1 and obtain analogues involving just p and q. In the list we let F n(.r. y) =
Fn(.‘r, y,p, q), and Fn(p, q) be the case where :17 = y = 1.

There are other analogues of Fibonacci numbers which could be studied. For
example, there is a restricted set of permutations which is counted by the Fibonacci
numbers, see [37] Given the plethora of permutation statistics, these are bound to
be interesting analogues. One may also find another 1). q-analogue of the Fibonacci
numbers in the following way. It’s not hard to see that the weight of a dash in a
Morse sequence as defined by Cigler can be translated to give a statistic on layered

matchings where the weight of a doubleton B is qmmBg/, and the weight of a

singleton is just a". Call this statistic rc, for Cigler. In a similar way we can find
a new statistic lc, which defines the relationship between the is statistic and the
q-analogues Carlitz and Cigler. The bistatistic (1c, rc) gives another p, q-analogue

of the Fibonacci numbers.

Table 3: List of p. q-Fibonacci Identites

n. + 2
Fn, + 2(41311) = 1,1n,+ 2(P(I)( 2 )

n. __ _
+ Z]- : 0 I] 1/(1N1) (2)1)” J 2W 17,, _ flaw/J + 2. ya] + 2)

 

(1.qu + 1’y(12j + 1)

F2” + 1(13 y) = 23.1: 0,374.1 + 1) - 10 + 2).,30 +1)F2n— 2)

 

F271,(13~2l/) = y"(pq)"(n — 1)

+231:0Iy,}p2.1(]+1) J(J+3) 1(1j(j 1)F2(n—j)—1(‘F(/2J+1’y(12j+1)

 

Fm+,,(;r. y) = F7»n(.r.pn'. gp")Fn,(.rqm‘. yq’”)

+ pp” —— lqm "m _ l(‘1,pn+ 1, pp" + 1)Fn _ 1(J‘qm + 1.3/(1771+ 1)

 

F27; + 1017.21) = W (Fn, + 1(Ip". 311)")1771, + 1(4I'(1"3y(1"‘)

_ y27)2n — 1(l2n + 1F.” _ l(mpn‘ ypn)Fn _ 1(J’qn + 23 Wn + 2))

 

”1017’an. + 1(13 y) =
2}”; 201 (...,21 1}}(2n _ 2j _ 1),] [(2102/2)

'Fn — 2 Jim?" . 31021 )Fn — 2j(”12‘] + 14142] + 1))
- 2
n2 ' ' _ '_ [(2J+1)/2j
+ zjl =/ 3(‘I.y2,]pj(2n 2y 2)q
'Fn - 21'0"!” ~ L9‘12‘])Fn — 2j(-”(IQJ + Isl/(1% +1»

 

Table 3 (cont’d)

 

XXL-:11 (Iy2ip2(n(2i + 1) — 1(2 + 3) — 1)q2i

22+2’quZ-i-2) 22. 22,)

'F2n — 22: — 2t”! F272. — 22: - it"! M1

+ 1y2i+ 1p(22: + 2)(2n — 4) — 21:2 + 3,122'0' + 1)

22 + 23W121+ 2)

-F2n — 2i — 3(Iq ; F272, — 22: — 2(1‘1121'+ 193/‘121+ 1))

 

F3k —1(‘1E‘.y) = Fk-(Ip2k_19y1)2k-1)

-Fk(;rpk _ lqkfljpk _ lkuF}; _ 1(4W12ka M1213)

+ yp2k — qu — le _ 1(Jl’p2k, yp2k)

kf—lqk+19 k—1qk+1) 2k 2k)

'5; _ 1(;rp yp Fk _ 1(;rq ,yq

'1.‘ p2

+ Wk — 2,121: —— IFH

k- l’yPQk— 1)

'Fk—1(;r(1)(1)k.y([)q)k)Fk _ 2(1.(12k + 1,y(12k +1)

+ y2p3k + 4,131.: — 2 Fl: 21:.)

_ 1(11921“. y!)

'Fk-2( [ck-+1 qu-l-l)

17p q ,yp 2k +1 21: +1)

Fk _ 2(;rq ,yq

 

F2n+ 1(1’3'9) =

:i j ($271. — 2i — 2j + 1yi +j(pq)n(n — i —j — 1) + i +j

,n—j+i+1n—i n+j—i+1n—j n-J’ "-13
(q ) (I) ) ,- j
M M

 

I125 = 1(1 +1)" - kq’“) =
annlp. q) + W" — 1F", _ 1(1), (1)

+22 = 0 F1, _ 1(1). (1)1)" ‘ k +1(1k 1131: k + 3(1+P"_ J +101)

 

55

Chapter 3
The Miibius Function

of a Compostion Poset

3. 1 Introduction

We now turn our focus to compositions. A composition a is an element
(al,(i2,...,ak) E lP’k, where I? = {1,2,3,...} is the set of positive integers.
The length of a composition a = ((11,02,” .,m,) is 6(a) = k, and the norm is
n. if 2.2-k: lai = n, also written lol = n. The on) are called parts. For example,
a = (1,3, 2, 1,4) is a composition of 11, and (1.3.1.24) is a different composition

of 11. Define Cn, to be the set of all compositions of n and let

C = U Cu.
71-

VVe are interested in studying a particular partial ordering on a set of restricted
compositions. Before we define this set, let’s briefly remind the reader of some
basic terminology about partially ordered sets (posets). A poset is a set P with
relation 3, which is reflexive, antisymmetric, and transitive. For example, if we
consider the set [12] and we say that for a, b E [12], a S b if and only if a divides
b, then [12]S is a poset with this relation.

The poset [12k is finite, but. we could easily consider the set 1P> under the same
relation and have an infinite poset. For any 1?, z E P the set [13:] of elements
31 E P such that .r. S y 3 z is called an interval of P. A poset P is locally finite
if any interval is finite. A snbposet of P is a set Q (_2 P under the same partial
orderng as P. Finally, two posets P and Q are isomorphic if there is a bijection
qb : P —+ Q such that for at. y E P, .r g y if and only if Mat) 3 p(g).

The partial ordering on C that we are interested in was introduced by Bjéirner

56

3“.-

‘2

and Stanley to produce a composition analogue of Young’s Lattice. Unfortunately,
their paper has since been withdrawn from the arXiv. For more information on
Young’s Lattice, we refer the reader to [38, 39]. To define the poset C we define
its covering relation 0 4 13. In a poset an element y covers an element :1", y > :17, if
y > at and there is no 2 with y > z > 17. In C, we say that 13 >— a = ((111.02. . . . .ak)

if [3 is of one of the two following forms:

13 = (nl‘u‘2""’“l—l‘a‘l+1’a'i+l"°°*ak')

U = (al,(r2,...,(¥lj_1,0i+1—h,h,(1&i+1,...,(1'k).

We will consider the poset. Cd, which is the subposet of C consisting of corn-
positions a = (01.02....,(rk) with (Li S d for 1 g i g k. "(l is the set of
compositions, with part sizes at most (l. Bjorner and Stanley use the fact that
C is isomorphic to a poset of words to determine the Mtibius function of C. We
will follow in their footsteps and use the fact that. the poset Cd is isomorphic to a
restricted poset of words.

Let. A* be the free monoid under concatenation of A 2 {a,b}. We think of
A* as the set of all words that can be created from the alphabet A. The identity
in 14* is the empty word 6. We say that the length of a word a = H1112 . "Uh is
[ill = 1:. Let u = 11.1712 . . . “k and w = 101102 . . . u'f be words in A*. We make
A* into a poset by letting a S w if there exist. i1 3 i2 3 g ik such that
uj = wij for 1 g j S k. We call the set. L = {'i1,i2 . . . , ii.) an embedding of u in
w and let wL = "Bil/(“2'2 . . . wik. If L is an embedding of u in w, then we say that
w j is supported by u in t if j E 1.. For example, the word abaab is a subword of
w = aabbababb, since 1122'u'3'w5w8 = abaab, and a3 is supported.

k.

Use the notation a 2 aa . . .a. Given a con'iposition a = ((11, 02, . . . ,ak) let
V '

k

57

p(a) = bal — 1ab“? _ 1a . . . aha/i7 _ 1. Clearly (,6 : C —> A* is a bijection. Note

that (b sends a part I: of a composition to a bb. . . b unless it is the first part of the

k — 1
composition, in which case the inital a is dropped.
Theorem 3.1.1 The map ¢ is an isomorphism of C and A* as partially ordered

sets.

Proof: Since we’ve already established d as a bijection between A* and C, it is
enough to Show that (b preserves the partial orderings.

Let a = (01,02, . . . ,ak) -< ,6 = (131,132,...,,(3g) E C. If 6 = k then, for some
j, ,133- = aj + 1 and {3,: = a) for i yé j. It is not hard to see that in this case @053)

th

is obtained from p(a) by inserting a b into rb(a) anywhere between the j and
(j + I)“ occurrence of an (1.. Thus, p(a) is a subword of (9(1)).

Ifl = 1: +1 then ['0 + 1 = aj +1 — h for some h, 61- = h and [3,: = (Yl' for 217$ j
or j + 1. In this case rb(li) is obtained from p(a) by inserting an a between the jth'
and (j + I)“ occurrence of an a.

Thus ,8 > a => 9503) >- p(a). The converse is proved similarly. [3

Let A; be the subposet of A* consisting of all words that do not contain at + 1
consecutive b’s. Notice that (2') restricts to an isomorphism between Cd+19 as

defined above, and the subposet, A3. Much is known about partially ordered sets

on words and subword order, so it will be convenient to work with the poset A:

to understand the poset C(1-

3.2 The Miibius Function of Cd

To every locally finite poset, P, and field, K, we associate an incidence algebra,
I (P) The elements of I (P) are functions, f, which assign a scalar, f (a,b), to

each interval [a,b], and f(a,b) = 0 if a f b. For f,g E [(P) and k E K we have

58

_'—-_ 1
" l .
g

_.‘ .

(kf)(a, b) = k(f(a, b)) and (f + g)(a, b) = f(a, b) + g(a, b). We define ”multiplica-

tion” in this algebra as the convolution

(f * a) (a, b) = Z fan-age. b).

a<r§b

The multiplicative identity of [(P) is

‘ 1 if a = b
0(a. b) =

() otherwise.

We are interested in two special functicms in I (P) One of them is the zeta

function,

1 if a S l)
((0,1)) =

0 otherwise

That is to say C(a, b) = 1 if the interval [a. b] is not empty and C(a. b) = 0 otherwise.
It. can be shown. [38], that. C is invertible with respect to the multiplication defined
above. That is, there is some ,a such that. C * p = p * C = 6. The inverse of C is
the Mobius function, it. It is easy to see that, since ,a is the inverse of C, p. is the

unique function in [(P) satisfying the following three properties.
0 ,u(.'l?,.1?) = 1
o :1. S z S yll(3».l/) = 0
o p.(;r.y) = 0 for .r f y

To describe the .\I6bius function of A; we will need the concepts of d—normal

embedding and right-most embedding. We will call a set [r.s] a run if

w-r = wr+1 = = 1123. Let the repetition set of w be R(w) = {j : wj =
wj _ 1}. An embedding i = {i1, i2, . . . , 17k} of u in w is called d-normal if (a)

R(w) (_2 {i1, i2, . . . , 27k}, and (b) if a has a run of (l b’s and the first b in this run

59

m‘ .-
l‘zfi

corresponds to wij in the embedding then “"ij __ 1 = a and i j - 1 E L. Let (35”,,

be the number of d-normal embeddings of u in w. The right-most embedding of n
in w is the unique embedding {j1,j2, . . . ,jk} such that if g jév, 1 g t S k for any

other embedding {i1, i2, . . . ,ik} of u, in w.

Theorem 3.2.1 For any words a, w E A;
Mu. w) 2 (_1)|w| + |u| w '
A u (172.

Proof: This proof is essentially the same as the proof of Theorem 3.1 from [7].
We will show that the function f (a, w) = (—1)l“'"I + In] (1,12,) dn satisfies the three
conditions above and hence, must be ,a.

Clearly, f (an) 2 1, and f (a,w) = 0 for a fi w. It remains to show that
EU S v S w f(vgw) = 0 for any n S w.

Suppose that [w] = n and [n] = A". Let N be the set of t = {i1,i2, . . . ,ir} such
that 1. is a d-normal embedding of wt, in w. Let N6 = {1. : #1. is even} (_i N and

N0 = {1. : #1, is odd} Q N. Then

X: f(vuw) = (-1>"(#Ne — #No).

a _<_ v S w

A bijection between Ne and N0 will complete the proof.
For each embedding L E N let I. f be the minimal number in [n] such that t f is

not in the right-most embedding of a in w,. Define ll) : N —> N by

4

LU{if} lftf $1.,
L— {if} lftf E t.

We show that w is well-defined. If t f ¢ L then, since [{(w) g L, we must have

R(w) Q L U I. }. If I, E I. then we want to show that 1. [l(w). If i E R(w)
f f f f g

60

then wif = wif

violates the definition of right-most embedding.

_ and i — 1 is in the ri lit—most embeddin of u in wL. This
1 f g g

We must show that w (V;,( Supoose w removes an
,,

) is still an element of A:.

l

a creating a run of d + 1 b‘s in will!) Since it can have a run of at most d b‘s,

I.

the first b in this newly formed run of b‘s cannot be in the right-most embedding.
Thus, the a would never have been removed.

If 1/2 inserts a b creating a run of d + 1 b’s in 10,190) then 20,, has a run of d b’s.
Let the first. b in this run be in position it. Since L is a d-normal embedding of
10,, in w, w]; t _ 1 = a, it — 1 E L. Thus, w cannot insert a b at the beginning of
the run. Inserting a b in the middle of the run violates the definition of right-most
embedding.

Clearl ' w is its own inverse and changes the arity of L. C]
. O t.

3.3 Shellability and the Mobius Function

We now give an alternate proof that p(n,w) = (_1)|w| + |n|(lub)dn by showing
that A; is dual CL-shellable. Shellability of a poset is a condition on a simplicial
complex related to the poset. We’ll begin by giving the topological background
necessary to develop the theory of shellability.

A simplicial complex A is a family of subsets o of a vertex set V, called sim-
plicies, such that if a Q 7' Q V and r E A then a E A. The dimension of
a simplex o is dimo = [0] — 1. The dimension of a simplicial complex A is
dimA = n = Inax{dirno E A}. Each simplex in A is called a face and the sim-
plices, which are maximal with respect to containment are called facets. We say
that A is pure if all facets are of the same dimension.

We say that a simplicial complex A is shellable if the facets can be ordered,
F1, F2, . . . Ft: in such a way that for each 1 gj S t, we have that Fjfl (UT; ; [17,)

is a union of maximal subfaces of F J

61

Let [:1 k(A) be the km reduced homology group of A over Z, and let dim [ii/AA)
be its dimension. We refer the reader to [28] for background on homology and
reduced homology of simplicial complexes.

Shellable complexes have very simple structure and homology as the next the-

orem [13] shows.

Theorem 3.3.1 Let A be a pure, shellable simplicial complex of dimension k then
A is homeomorphic to a wedge of k-spheres and hence dim [ll-(A) = 0 for 0 g i <

k.l:l

Let P be a poset. A chain of length n in P is an ordered (n + 1)-tuple
($0,171, . . . ,atn), with .r, g Ii +1 for 0 S i S n — 1. A chain c = (r0,r1,...,:rn)
is said to be saturated if Ii < 11,: + 1 for O S i S n — 1. We will say that a chain
c = (r0, r1, . . . ,rrn) in the interval [17, y] is maximal if c is saturated, r0 = :r, and
.1772, = y. A locally finite poset P is ranked if every maximal chain in any interval
has the same length.

There is a special simplicial complex associated to each poset P called the order
complex. The order complex A( P) has the elements of P as its vertex set and all
chains of P as its simplicies. Notice that each interval of a ranked poset gives rise
to a pure order complex. A poset P is called shellable if its order complex A(P)
is shellable.

Bj6rner showed that the poset of words on any finite alphabet under subword
order is dual CL-shellable [6]. We will show that the poset A; admits a dual CL-
shelling under the same labeling. First, let us define a chain lexicographic labeling
of a poset as introduced by Bjérner and ,VVachs [11, 12].

Let P be a finite poset with a unique minimal element 6 and a unique maximal
element 1. Let E(P) = {(Iy) E P x P : a: < y} be the set of edges of the
Hasse diagram of P, and A! (P) be the set of maximal chains in P. A chain-edge

labeling of P is a map E : {(:1:,y,c) E E(P) x AMP) : at, y E c} —» Z satisfying the

62

following condition. If two maximal chains c1 and (:2 share their first k edges then
€(r, y, Cl) = [f(a‘, y, c2) for the first k edges (:17, y) of each chain.
The chain—edge labeling 1’? associates to each maximal chain,

c = (0 = 10,171, . . . ,.rn = 1) a unique n-tuple

l(c)= (€(.170,;1‘.1,c),[(.‘1‘.1,.’172,c),...,l;’(;1‘.n_1,:Ifn,c)).

Notice that any saturated k-chain inherits a potentially different labeling for each
maximal chain that includes it. To establish uniqueness, we use rooted intervals.

A rooted interval of P is an interval [16, y]r, where r is a maximal chain in [6, .r].
If e is a maximal chain in [13, y],~ then r U c is a maximal chain in [6, y]. Hence, the
labels l(m) and €(m’) of any two maximal chains m and m’ of P containing r U c
must agree on the elements of r U c. Thus, for any maximal chain c in [.r, y],~, l(c)
is unique in [.r, y],~.

A maximal chain c in [:1:. y],~ is called ascending (descending) if
£(;2:0,;171,c) < (>)t(r1..r2,c) < (>)... < (>)t(.r.n,_1,:1tn,c).

Given chains c(.r0, r1, . . . ,‘.L‘k) and c’ = (16,191, . . . ,r’k) in [:r, y]r, we say that c is
lexicographically smaller than c’, €(c) <1” €(c’), if €(.1:i, :11,- + 1,1:) < l(r’i, .1;- + 1, c’)
in the first coordinate, where E(c) and f(c’) differ.

A chain edge labeling l is called a CL-labeling (chain-lexicographic labeling) if
for each rooted interval [17, y].,~ there exists a unique ascending maximal chain c,
and c <lea: c’ for any other maximal chain c’ E [:1', y]r. If P has a CL-labeling then

we say that P is chain—lewicoraphically shellable.

Theorem 3.3.2 (Bjfirner,WaChs) If a poset P is chain-leadcographically shellable

then its order complex: A(P) is shellable. [:1

The shelling of the complex A(P) is given by putting a linear ordering < A

63

w‘ “a! 11
~.-

on the set of maximal chains 01,112,. . .,cn such that l(ci) < €(C:J-) implies that
c7; < A cj. This odering on the maximal faces of A(P) is a shelling.

The dual, P*, of a poset P is a poset on the same elements as P, in which .10 g y
in P* if y _<_ :1: in P. A poset is called dual CL-shellable if its dual is CL-shellable.
Without considering the dual of the entire poset, we simply reverse the labelings
on our chains. That is to say, for c = (.170, 11:1, . . . , .rk) in [:r,y]-,~, we consider the
labeling €*(c) = (6(23;C _1,.rk,c),l”(:rk._ 2.1:); _ 1,c), . . .,€(:1:0,:1:1,c)). Now, 5* is
a dual CL-shelling of P if 5* satisfies the same two conditions above. Let P be the
poset P — {0,1}. Clearly, P is shellable if and only if P is.

Shellability allows us to find the Mobius function of a poset using the topology
of its order complex. Let A1,: be the number of chains of length i starting at f) and
ending at 1. Thus, H0 = 0 and HI = 1. A proof of the following theorem can be

found in [38].

Theorem 3.3.3 (Hall) For any finite poset P with 0 and 1,

,u.p(f), 1) = Z (—1)lh‘,?'. Cl
i 2 0
It is easy to see that Hi is the number of chains of length i — 2 in the poset P.
This essentially says that H7: = Ci _ 2 where Cl" _ 2 is the number of i — 2-simplicies
in A( P). Define the reduced Euler Characteristic of a finite simiplicial complex A

to be

g(A) = —1+ 2 (—1)jcj.
120

Thus, we have that

1110(6). 1) = “AU-3))-

A proof of the following theorem can be found in [28].

64

Theorem 3.3.4 For any simplicial complezr A,

HA): Z (—1)kdimHA.(A).Cl
A7 2 —1

This gives us that 11p(f),1) = 2A7 Z _1(—1)k dim flk(A(P)). Thus, by our
remarks above, if P is shellable then A(P) is shellable and hence 11p(f),1) =
(—1)k dim Hk(A(P)). This simplifies the computation of the Mobius function of
a shellable poset.

The question now is how to determine dim Ilk(A(P)) from the dual CL-shelling.
Let D(;r, y) be the number of descending maximal chains in the interval [517, y]r.

In their paper [8] Bjorner, Garsia, and Stanley give the following corollary, stated

here as a Theorem.

Theorem 3.3.5 (A. Bjorner, A. Garsia, R. Stanley) LetP be a ranked poset,
and [:r, y] be an interval of P. If t : P —-> Z is a CL-labeling of P then

1111:. y) = (—1>"‘D(.r.. y). D

We apply this information to the poset AZ. We will use the same labeling that

Bjorner used in [6] to determine the Mobius function of A*.

Let [’11,w],~ be a rooted interval of A*, and let each maximal chain c = (u =
.171..r2,.. "1A7 =11?) in [11.11:] be assigned a label [(711) = (£1071). [2(771), . . . , lk.(m))
as follows. Label the edge (.rk _ 1.1147) by [(;rk _ 1,;rk, c) = i1, where i1 is the
least element of [A] such that [A] — {i1} is an embedding of 'T’A' _ 1 in 17k. Label the
edge (ark _ 2. 'TA' _ 1.0) by €(rk _ 2, ml: _ 1, c) = i2, where 12 is the least element.
of [A7] — {l1} such that [A] —— {1.1, 12} is an embedding of IA" _ 2 in 75A" Repeat this
process for the remaining edges. It is clear that if two maximal chains have the

same first 3 edges then the labels on these edges will be the same. Figure 3 shows

this chain-edge labeling for [abb. aabbab].

65

 

       
 

 

 

 

 

a a bba b
1 3
aa (1 (1 bba abbab (1a bob
1
5
1
5 6 3 1
a bbb (1. at b ( bba a bab

abb
Figure 3: CL-labeling of [abb,aabbab]

Theorem 3.3.6 (Bjiirner) The map f : A“ —> Z described above is a dual CL-

labeling for each interval of A*. E]

In Bjiirners proof [6] he shows that the unique ascending maximal chain is one
corresponding to the right-most embedding of u in w. Let {i1, i2, . . . , 17k} be the
right-most embedding of u in w, then the ascending maximal chain is the maximal
chain labeled by the elements of [n] — {11. i2, . . . , i A} from smallest to largest. The

unique ascending chain in Figure 3 is

r

1 3 .
abbaba — abbab — abab — abb.

It is also clear that since we are working with the right-most. embedding, this chain
must have the lexicographically smallest possible entries.

Each maximal chain of an interval [11,219] in A: is also a maximal chain of the

66

Ifl~ 46*!" i

same interval in A*. We will denote by [11,7111]d the interval [711,111] in A* restricted
to A2. We will label the edges of A; by (d : A: —> Z in exactly the same way as

we did for A*.

Theorem 3.3.7 The map 6d : A; —> Z is a dual CL-labeling for each interval of

A22, and hence A"; is CL-shellable.

Proof: we already know that there is exactly one ascending maximal chain, mo, in
the labeling of an interval ['11, w] in 14*, and that. 1710 corresponds to the right-most
embedding of u in w. This means that there is at most one ascending maximal
chain among those in the interval ['11, 111]“). We must show that this chain is still
in [11, w]. Unless a chain passes through an element.- with a run of b’s of length at
least (1 + 1, that chain is in [11,-11.2](1.

Note that u and w both do not contain such a run. The only way to pass
through an element with such a run is by removing an a that was originally sepa-
rating d +1 or more b’s. Recall that at each step the left-most element is removed,
maintaining an embedding. Since 11 does not contain a run of d + 1 or more b’s
and we are considering the right-most embedding of 11, such an a cannot be the

left-most removable element. 1:]

Corollary 3.3.8 For words 11. and 10 17114:; we have 11(11, w) = (—1)l“"’ l + [U] ((illldn'

Proof: By Theorem 3.5 it suffices to show that the number of descending chains
in [11,111] is the same as the number of d-normal embeddings of u in w.
Suppose 1. = {i1, i2 . . . , i k} is an embedding of u in w such that there is a max-

imal chain m with [n] —- {51(m), €2(m), . . . , l. _ k(m)} = 1,. Then m is descending

n
if m is obtained by deleting the entries we, with j E [n] — L, from right to left.
This is possible only if for each jl < 12 < j3 with j1,j3 E [n] — L and 32 E 1,,

we have that wjl gé 711.7]‘2. And if 11 contains a run of d b’s and the first b in the

run corresponds to wjt then w j t _ 1 = a and jt — 1 E 1,, otherwise this maximal

67

“MAI-(1.4;;
. ),

chain will pass through an element not in A2}. These two conditions show that
{i1, i2, . . . , ik} is a d-normal embedding of 11 in w.

Similarly, if L = [1'], i2, . . . , ’A‘l is a d—normal embedding of u in w then there
is a descending maximal chain corresponding to L given by deleting the elements

w j? with j E [n] -— L, from right to left. Cl

3.4 Rationality

Let S a finite set. The formal power series algebra in the noncommuting variables
of S over the field Z, denoted Z ((S)), is the set of all infinite series f = 2,- (717.17,
where Ci E Z and 1‘)" is some word in S *. We define the * operation on Z ((S)) to
be f* = e + f + f2 + . . . where e is the the empty word in S*. A series f E Z ((S))
is called rational if it can be constructed from a finite number of monomials under
a finite number of the usual algebraic operations in Z ((S)) and the =1: operation.
Let ft = 1* — 6. Clearly, f+ is rational if f is.

The ring Z ((4)), where A 2 {a,b} as before, is simply the set. of series of
the form f = 2w E A* cusw, with Cw E Z. We may also consider series of the
form f = Z“, S w C(uyuqll X w where 11 {>31 w just represents the ordered pair
(11,211) E A* x A*. Rationality of such a series is defined similarly.

In [9] Bjiirner and Reutenauer showed that the following four series are rational:

Z(11.) = 2 C(11, 11.7)711),
w E A*
M (11) = 2 11(11. '11,!)111,
w E A*
Z s = 2: C (11. '11')'11. X 11',
w E 14*
M.x = 2 11(11. w)11 X1 w.

w E A*

68

In this section we will use methods similar to those used by Bjéirner and
Sagan [10] to do the same for the series Zd(11), 1\Id(u), Z%, and Ni, where
these series are defined exactly the same way as those above replacing A* by A:
in each. For the remainder of this section we will assume that d = 3 to avoid
cumbersome formulas and definitions. Everything that. is used to prove these facts
for d = 3 can be generalized to any (1.

We begin with Z3('11) and 1113(11). We remind the reader that the bijection

c6 : C —> 14* was given by rb(A') = abb. ..b. A function f : S* —+ T* where S
k 1

and T are finite sets is multiplicative if for u = 111112 . . . um E S*, we have that
f(u) = f(111)f(u2) - - - f(117-n). Let 143 = {a,ab,abb,abbb}. Let B = €+b+bb+bbb,
and notice that (6 + b + bb + bbb)(143)* = 143;. Notice that each word 11 E A; can
be broken uniquely into its maximal runs of 11’s and b’s. Define the multiplicative

function 2 : A; —> Z ((A3)) , where :3 acts on maximal runs, by

g(al“) = (A3)" — 1a,
z(b) = (B — ()a*,
z(bb) = (B — e)a+ba* + (B — b — e)a*,

z(bbb) = (B — e)a+ba*ba* + (B — b — 6')(l+l)(l* + bbb11*.

If a run of 11‘s is at the end of the word then let 2(ak) = 2(ak)B for this run of

as. Let. pz(u) be the prefix: of Z (a) where,

B(A3)* 11 begins with a,

(B(A3)*a + (I) ‘11 begins with b.

Define the multiplicative function m : 14:; —> Z ((A3)), where m acts on maxi-

69

 

mal runs, by

[I

m(ak) = ((ab)* — (1)111 + (ab)+(e — 11..)11)A _1(a + (ab)+a)
m(b) = b((ab)* — a — b),
m(bb) = (b(a.b)*)2(e — b),

m(bbb) = (b(ab)*)3.

Let pm,(u) be the prefix of 111(11) where,

(ab)* 11 begins with a,
Pmlul =
(ab)*a it begins with b.

Lemma 3.4.1 For any 11 E A; we have that

23111) = Mum).

and

1113(11) = pm(u)m(u).

Proof: We begin by proving the statement for Z3(u). We must show that the
function 2 will produce each word that contains 11 exactly once. This is done by
showing that for w 2 u, 2(u) produces the right most embedding of u in w. We
will explain how this works for z(ak), how these go together with z(b£) and how
the prefixes work. The remaining cases are similar.

The last a in the run ak is given by the a at the end of z(ak). This is clearly

under the right-most possible a if we focus on 2(ak). The preceding k — 1 as are

each followed by B = e + b + bb + bbb. If there were an a between any of the k‘

70

a’s, then the preceding as could be shifted to the right, and hence the embedding
would not be the right-most one.

The only place that any as could be placed is at the beginning of the run. The
reader will notice that this is not. encorporated in 2(ak). This issue is resolved in

k is preced by a run of b’s, then the a* at the end

the following two ways. If this a
of each of z(b), 2(bb), and z(bbb) places as many as as one would like before the
first a of ak. If this ak is at the beginning of the word the the prefix pz(u) takes
care of the problem.

The same arguments as above, minding the fact that there can be no more
than three b’s in a run explain z(b), z(bb), and 2(bbb). The prefix pz(u), when u
begins with a, is clear. Let’s briefly discuss the prefix, when u begins with b. If we
are considering the right most embedding of u in w and we are trying to generate
any w, then each w can begin with any word from 14;. Hence, pg(u) must begin
with B(143)* regardless of the first letter of u. If u begins with b, we must be
careful not to create a run of more than three b’s. To avoid this, we put a at the
end of B (A3)* and add 6 to take into consideration the fact that the first letter of
u could be the first letter of w.

After a close look at z(b€) for 1 g t” S 3, the reader will see that 3(a) produces
w only as a right-most embedding, and hence each w 2 u is generated once.

Now, we turn our attention to m(u). Again, we will explain m(ak), how it
works together with m(bf) and how the prefixes work. We show that each w E A};
appears (_1)|w| + [All (5)3” times in m(u).

We begin with an explanation of m(ak). At. the beginning is ((ab)* —a). Notice
that an a (respectively b) does not have to be part of a 3—normal embedding if it is
immediately preceded by a b (respectively a). This means that we can begin with
a run of alternating as and b’s. Since we are appending two letters at a time, the

Sign of our word isn’t changing. The —a in this first part. describes the option of

placing an unsupported a at the beginning of a run of as.

71

Each of the first A‘ — 1 as in this run is taken care of by (a + ab+(e - a)a).
The first 0. covers the option of just having an a. The next portion places at least
one copy of ab followed by nothing or an extra (1. This takes care of the fact that
we can place a run of alternating as and b’s before each a in our run. As long as
there is at least one copy of ab before the a then we could place another —a before
the next a. The final portion forces m(ak) to end in a so as not to create a run of
more than three b’s.

This description shows that each word w produced by m(u) is produced with
respect to a unique 3-normal embedding of u in w. Also, any possible 3-normal
embedding of u in a word w is produced. The prefix takes care of the beginning
of a word in which u is 3—normally embedded. Cl

The fact that 2(a), m(u), pz(u) and pm(u) are rational for each u E A; proves

the following theorem.
Theorem 3.4.2 The series Z3(u) and 1113(11) are rational. C]

The techniques used above to prove the rationality of Z3(u) and M3(u) are a
bit cumbersome. we will use finite state automata to prove that Z% and 1111,99 are
rational.

Let S be an alphabet. A finite state automaton is a digraph D, with vertex set
V and are set E, allowing loops and multi-arcs. There are unique verticies a and
11.2, where a is the inital vertex and w is the final vertex. Each arc e E E is labeled
by a monomial f(e) E Z ((S.)) A finite walk W with arcs e1,e2, . . .,ek is given

the monomial label

The series accepted by D is

where the sum us over all walks in D from a to 112.
If e ,. . . e: are all arcs from one vertex to another re lacing them I) 7 a single
1 j a o . o

are e and labeling this are

does not change the series accepted by D. For simplification we will use this
procedure.

It is a well-known fact that. a series is rational if and only if it is accepted by a
finite state automaton [5]. we will construct finite state automata accepting Z3);
and [1%, to prove the following theorem for d = 3. The pattern in the automata

will be obvious and generalizable.
Theorem 3.4.3 For any d, Z9; and Mg are rational.

Proof: The automata in Figures 4 and 5 are for Z% and M 639 respectively. We will
use them to explain why these automata accept Z 35 and 111% respectively and how
they are generalizable to any d. For clarity, we left some arcs off of the diagrams.
In Figure 4, there is an are labelled e 59 e from each node to 112. In Figure 5, there
is an are labelled e: X e from each of (12, (13, 1'32, 1'33, 134, '75, 761 7'7, (58, (59, and
610 to 11). There is also an are labelled a X a from each of ,82, 1'33, 134, '75, 76, “/7,
68, 69, and 610 to each of (12, 1'31, '71, and 151. Also in Figure 5, we separated the
node a from the rest of the digraph.

we claim that for any n = 111112...711k S w = 11.711112 . . . wn there is a unique
walk from a to w in the automaton for Z20 labelled i1.=:X)w. First, we show that there
is a walk for any 11 20 w. Consider the right-most embedding L = {711,132, . . . ,ik} of
u in w. We’ll build u «59 w from this embedding. The first i1 — 1 letters in w are
not. supported, so this portion of w is constructed using the nodes 01, 011, (112, and
(13. Notice that any word in A; can be built uniquely by using the nodes 01, al,

012, and (13. Now, if 111 = a and 111,11 is preceded by an a then we must follow the

73

are from o to 014. If 10,-, is preceded by a run of b’s then we must follow the are
from a to 62, construct this run of b’s and then go to 014. If ul = b and wil is
preceded by an a then at this point the walk follows the are from 01 to {3. If “1 = b
and wil is preceded by a run of b’s then the walk must follow the are from a to
62, build up the preceding run of unsupported b’s and then go on to either 7 or 6

from 62 or 63 respectively.

 

 

 

 

 

 

 

 

 

. . 3
Figure 4. Z50

Now, there is no way to get back to the a, (.11, (1‘2, and (.13 part of the digraph.

74

twin
.

Notice that if 111 = a. then the unsupported part of w between wil

only be a run of b’s. If 11.1 = b then the unsupported part of 10 between wil and

wi2 can only be a run of 11’s. This is forcing the embedding L to be the right-most.

and 111,-2 can

embedding. The construction continues as above for the remainder of 11 X '11).

It is important to note here that the complication of the digraph develops from
the fact that we must be careful to avoid producing a run of more than three b’s
in u or w. The portion of the digraph involving the 13’s controls the supported b’s
in w, and the portion involving the 77’s controls the unsupported b’s.

Our comments above about the automaton forcing L to be the right-most em-
bedding proves that each u X w is produced by a unique walk, and hence the
automaton accepts Zgg- To generalize this to any Z%, we would merely extend
the 01, 13 and 7 portions of the digraph appropriately.

We turn our focus to the automaton for 111%. We claim that for any walk from
a to w the monomial 11. X '10 associated to this walk is a 3-normal embedding. The
walk must begin at (1. Depending on the beginning of the embedding we select our
first destination from a. The reader will see that each possibility is represented.
Without explaining every possibility, we will begin by looking at what happens at
(12. The node (12 is building runs of as. Between any two as in a run can be
a run of alternating unsupported as and b’s. This is controled by the exchange
between 02 and 03. Notice that the only way to create a run of two or more as
in w is to make at least. one loop around 012. The automaton is assuring that an
a preceded by an a in w is supported. The automaton is forcing the embedding
that a walk generates to be 3-normal.

Now, the three legs of the diagram labeled with 13’s. 77’s and 65 respectively,
are controlling the three possibilites for a run of b’s in u. If it has a run of three
b’s, the walk producing 11 X w must pass through the 6 part of the diagram. Each

of the three different legs of the 6 portion of the diagram represents a supported

b. So once the walk is on any of the nodes 68, 69, or 610 all three b’s in this run

75

have been [norluced Notice that in this section between any two supported b’s
there can be a run of alternating as and b’s. given by the exchange between the
bottom two nodes of each leg. Also, all but one are going into 61 is labeled with a
supported a immediately preceding the portion of the word to be produced. The
only are that does not is the arc from a to 61. This again is assuring that the
embedding of any walk is 3—normal.

The portion marked with 13’s controls situations where 11. has a run of just one b
and the portion marked with 7’s takes care of two b's. This shows that every walk
from 01 to w in this automaton produces 11 X w according to a. 3-normal embedding.
It’s not hard to see from the above explanation that any normal embedding L of u
in w is given by a unique walk from a to :12.

Finally, notice that anytime a letter in a label on an arc is unsupported the

sign of the monomial label changes. This takes care of the sign of 11(11, w). Cl

76

“I raw-s.-

.u “‘1‘... u‘

8%:
@

Figure 5: 111%

 

£3 X X3

 

3 X 3

 

 

EXCIS

 

3 X 3

 

 

1

..a
e

l

 

i1
.132 (73 ”1'1 “1’

 

 

 

 

s+sxar.
ass.
GMAG dlv®
As+3a;1-v
a
$.31 1
GXGIS . 2

 

 

 

SXowleo®

 

3 ON, .vl

 

 

 

 

 

 

 

 

 

.3
.Q
2aaeae

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

hm

sail to
w

Sgul row 00
s87 - ..m
docul \4

L6
€131

W

eXoI

1H

[A
if: 1
3X31 AM.
sat: .
eXcI

6
seal -

3.5 Generating Functions in Commuting Vari-
ables

The generating functions above are quite beautiful and are rational, but they don't
emphasize the connection between words in 14:; and the compositions in Cd + 1.
To see how this all ties together we will use what we know from the previous
section to produce generating functions in commuting variables for C and 11. This
will allow us to consider the generating functions in terms of the length, 6(a), of a
compostion a or the norm of 01, [al. If "k is the number of k’s in 01 then we may
redefine l(0) = 2A? Z 1 n A' and la] 2 2A7 2 1 nkk. Let a H u, then the type of a
is 7(a) = (111,112, . . . , an, r), where r is the number of runs of as in u.

k.

Each time A7 appears in a replace A: by .17 , where .1: is a commuting variable.

Then we obtain the norm generating function

. . 13
Zd((1,.r,) = Z :17| l.
(1 g 13
If we replace each element in a by the variable t then we obtain the length gener-

at ing function

Zd((1;t)= Z tad).

a S 13
To avoid cumbersome formulas and because these generalize simply to any d
we will focus on the case when d = 3. If a E C4 corresponds to u E 145 then any
a that is not immediately followed by a b represents a 1 from a and b, bb, and bbb
represent 2,3, and 4 respectively. Let [A] 1: be the polynomial 1 +117 + . . . + .17]if _ 1.
Let z(u; a7) and [23(11; 1‘) be the formal power series in Z [[1]] obtained from 2(a)
and pz(u) respectively by replacing each letter in 3(a) by (t. Then it’s easy to see
that Z3(u;:1:) = p;('11;;r)z('11;:17). Defining m(u;.r) and pm(11.;;17) in a similar way

gives us that 1113(11; r) = p7,,(u; .1:)m(11 : :r)

78

*1... 0A1” ‘19-. .91

Suppose 11 has type r(11) = (111.172, n.3,n4. r) then Lemma 3.4.1 gives us that
Z3(11;;1‘) is one of the following rational functions. The first two correspond to 11
beginning with a and the last two correspond to '11 beginning with b. The first and
third correspond to 11 ending with b and the second and fourth correspond to u

ending with a.

. 1—.11‘3r (ifn1(l4l.17)nl" r+1) (#g)"2<(1;21%§2 + 112g?)n3
.3 - 174‘ 1' 1' "4
'<6% +16% + pi.)

—.T

. . ‘ 712 :172' r .172 r "3
° ,__1,,,,(..~11W-r)( 3-l (136W 161155)
.173 3 J. .174 2 .r .1‘3 n4
(6%6% +61?)
, 2 : 112 172' r .172 r 713
o m(1"1([1]1)"1_ F +1) ( 3fir) ((1.6%)? + 143171")
.r3[3[.r I4l2l-I‘ T3 "4
((1-1) +(1—1)2+1—-l‘l

. . 712 (_2 ‘ 172 r "3
. 13,,” (.r"'1<[41.a"1—")( 3.1;.) (5%; +195)

..3- 4 3 "4
.1 31‘ I 2.1“ .17 )
- —i—l—3+—U—7+1—
((1—1‘) (l—I) TI

Again, if 11 has type 77(11) = (111. n2, n3. n4. r) then 1113(11: .r) is one of the following.

 

 

 

 

The first corresponds to 11 beginning with a, b, or bb. The last corresponds to those

11 beginning with bbb.

3 nil ' -— .‘l‘ l—.T+.1‘3 n2
0 112(( 12)?) (1—.r+,p2)r(1_r+‘l.3)nl r(( 1+I )>

1—1‘
n. 311.
1 >71—u >7
1+.r—172—173 1—.r

 

 

 

79

 

 

3 ""1 . . _ , 3 "2
;1: :17 ,.2 r , .3 n — r 13(1 1' +17 )
.1—1772( 2)?) (1—.L+.L ) (1—.1.7+;1. ) 1 ( 1+1, )

(1—17
( )6” (__,21~. >36
1+:I:—:1:2—:173 1—:1:

The following theorem is now an immediate consequence of Lemma 4.1.

 

Theorem 3.5.1 The norm generating fuctions Z3(11;;r) and 1113(11;:17) for 11 with

type 7(11) = (111,712, 11.3.11,4.'r) are as stated above. Cl

Now, we want to consider the length generating functions for C and 11. Let
2;(11 t) and pz(11; t) be the formal power series in Z [[t]] obtained from 2(u ) and pz(u)
respectively in the following way. Replace each a that is not immediately followed
by a b by t and each maximal run of b’s by t. Then it’s easy to see that Z3(u; t) =
pg 7(113 t)2 (11; t). A similar definition gives that 1113(11; t) = pm(11; t)m(u; t).
Suppose 11 has type r(u) = (711,112,713, n.4,r) then Lemma 3.4.1 gives us that.
Z3(u; t) is one of the following with the same correspondance as in the list for

Z3(u; r).

 

—2> Wir- >
M)

3!
T—_, (
. — 31 "’2 21+12 ”3 12(4t+1)(2
'1-14r61 firrd <6‘7Pl11_a3

 

 

. (3t+1)(2 — ”(4011.1 _ .,.( 3t >712 (2t + t2 >713 (112(4): + 1)(2 _ ”>714

 

., n 2 114
2—1, ,—- 31 ”2 21+12 3 t(4t+1)(2-t)
'I-Zd“wl rif-d (0—6?) A 0-19

Again, if 11 has type r(11) = (111,112,713, n4, r) then

n —r 71,
,,_(,,.,)_( 1 )n, 2— 31+312—13 2—314-212 1 1—12+13 2
‘5’" 1:7 (1_,)2 (1_,)2 ‘7??—

n. 1. t
, 1—12+13 3( 1 )2'7'3( 1 )3774
1—1 l—t I—t '

The following theorem is now an immediate consequence of Lemma 3.4.1.

 

 

80

Theorem 3.5.2 The norm, generating factions Z301; t) and 1\[3(11; t) for 11 with

type 7(11) 2 (111.112, 113.114, r) are as stated above. Cl

We would like to extend our gratitude to Bjorner and Stanley for their work
on the composition poset C , as this chapter would not have been possible without

it.

81

BIBLIOGRAPHY

[l] ANDREWS, G. E. The theory of partitions. Cambridge lVIathematical Library.
Cambridge University Press, Cambridge, 1998. Reprint of the 1976 original.

[2] BABSON, E., AND STEINGRI’MSSON, E. Generalized permutation patterns

and a classification of the Mahonian statistics. Se’m. Lothar. Combin. Vol. 44
(2000), 18 pp. (electronic).

[3] BARCUCCI, E., DEL LUNGO, A., FEEDOU, J. M., AND PINZANI, R. Steep

polyominoes, q-lV’Iotzkin numbers and q-Bessel functions. Discrete Math. 189
(1998),21—42.

[4] BENJAMIN, A. T., AND QUINN, J. J. Proofs that really count, vol. 27 of The
Dolciani Mathematical Ezvpositions. Mathematical Association of America,
W'ashington, DC, 2003. The art of combinatorial proof.

[5] BERSTEL, J., AND REUTENAUER, C. Rational series and their languages,
vol. 12 of EATCS Monographs on Theoretical Computer Science. Springer-
Verlag, Berlin, 1988.

[6] BJoRNER, A. The Mobius function of subword order. In Invariant theory and
tableaux (Minneapolis, MN, 1988), vol. 19 of [MA Vol. Math. Appl. Springer,
New York, 1990, pp. 118—124.

[7] BJoRNER, A. The M'o'bius function of factor order. Theoret. Comput. Sci.
117, 1-2 (1993), 91—98. Conference on Formal Power Series and Algebraic
Combinatorics (Bordeaux, 1991).

[8] 8161mm, A., GARSIA, A. M., AND STANLEY, R. P. An introduction to
Cohen-Macaulay partially ordered sets. In Ordered sets (Banfi, Alta, 1981),
vol. 83 of NATO Adv. Study Inst. Ser. C: Math. Phys. Sci. Reidel, Dordrecht,
1982, pp. 583—615.

[9] 8161mm, A., AND REUTENAUER, C. Rationality of the Mbbius function of
subword order. Theoret. Comput. Sci. 98, 1 (1992), 53fi3. Second Workshop
on Algebraic and Computer-theoretic Aspects of Formal Power Series (Paris,
1990).

[10] BJDRNER, A., AND SAGAN, B. E. Rationality of the Mobius function of a
composition poset. , Preprint at arXiv: math.C0/ 0510282.

[11] BJDRNER, A., AND WACHS, M. Bruhat order of Coxeter groups and shella-
bility. Adv. in Math. 43, 1 (1982), 87-100.

[12] BJoRNER, A., AND WACHS, M. On lexicographically shellable posets. Trans.
Amer. Math. Soc. 277, 1 (1983), 323—341.

82

 

[13]

[14]

[16]
[17]

[18]

[19]

[20]

[21]

[22]
[23]

[24]

[25]

[26]

[27]

[28]

‘weA‘A-‘c d
“-1.3. .

BJDRNER, A., AND WACHS, M. L. Shellable nonpure complexes and posets.
I. Trans. Amer. Math. Soc. 848, 4 (1996), 1299—1327.

BOUSQUET-MELOU, M., AND XIN, G. On partitions avoiding 3—crossings.
Sém. Lothar. Combin. 54 (2005/06), Art. B54e, 21 pp. (electronic).

BRIGHAM, R. C., CARON, R. M., Z., G. P., AND GRIMALDI, R. P. A
tiling scheme for the fibonacci numbers. Journal of Recreational Mathematics
28 (1996-7), 10—16.

CARLITZ, L. On abelian fields. Trans. Amer. Math. Soc. 35 (1933), 122—136.

CARLITZ, L. q-Bernoulli numbers and polynomials. Duke Math. J. 15 (1948),
987—1000.

CARLITZ, L. Fibonacci notes. III. q-Fibonacci numbers. Fibonacci Quart. 12
(1974),317~322.

CARLITZ, L. Fibonacci notes. IV. q-Fibonacci polynomials. Fibonacci Quart.
13 (1975), 97—102.

CHEN, W. Y., DENG, E. Y., DU, R. R., STANLEY, R. P., AND YAN,
C. H. Crossings and nestings of matchings and partitions. , Preprint at
arXiv: math.C0/0501230.

CIGLER, J. A new class of q-Fibonacci polynomials. Electron. J. Combin. 10
(2003), Research Paper 19, 15 pp. (electronic).

CIGLER, J. q-Fibonacci polynomials. Fibonacci Quart. 41 (2003), 31—40.

CIGLER, J. Some algebraic aspects of Morse code sequences. Discrete Math.
Theor. Comput. Sci. 6 (2003), 5568 (electronic).

CIGLER, J. q-Fibonacci polynomials and the Rogers-Ramanujan identities.
Ann. Comb. 8 (2004), 269—285.

GESSEL, I., AND VIENNOT, G. Binomial determinants, paths, and hook
length formulae. Adv. in Math. 58 (1985), 300—321.

GESSEL, I., WEINSTEIN, J., AND WILF, H. S. Lattice walks in Z" and

permutations with no long ascending subsequences. Electron. J. Combin. 5
(1998), 11 pp. (electronic).

GOULD, H. W. The q-Stirling numbers of first and second kinds. Dulce Math.
J. 28 (1961), 281—289.

HATCHER, A. Algebraic topology. Cambridge University Press, Cambridge,
2002.

83

It

 

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]
[37]

[38]

[39]

[40]

[41]

KASRAOUI, A., AND ZENG, J. Distribution of crossings, nestings and
alignments of two edges in matchings and partitions. , Preprint at arXiv:
math . C0/0601081.

KLAZAR, M. On abab—free and abba-free set partitirms. European J. Combin.
17 (1996), 53—68.

KREWERAS, G. Sur les partitions non croisées d’un cycle. Discrete Math. 1
(1972),333-350.

LINDSTRDM, B. On the vector representations of induced matroids. Bull.
London Math. Soc. 5 (1973), 85—90.

MILNE, S. C. Restricted growth functions, rank row matchings of partition
lattices, and q-Stirling numbers. Adv. in Math. 43 (1982), 173—196.

SAGAN, B. E. Pattern avoidance in set partitions. , Preprint at arXiv:
math.C0/0604292.

SAGAN, B. E. A maj statistic for set partitions. European J. Combin. 12
(1991),69—79.

SIMION, R. Noncrossing partitions. Discrete Math. 217 (2000), 367—409.

SIMION, R., AND SCHMIDT, F. W. Restricted permutations. European J.
Combin. 6 (1985), 383—406.

STANLEY, R. P. Enumerative combinatorics. Vol. 1, vol. 49 of Cambridge
Studies in Advanced Mathematics. Cambridge University Press, Cambridge,
1997. With a. foreword by Gian-Carlo Rota, Corrected reprint of the 1986
original.

STANLEY, R. P. Enumerative combinatorics. Vol. 2, vol. 62 of Cambridge

Studies in Advanced Mathematics. Cambridge University Press, Cambridge,
1999.

WACHS, M., AND WHITE, D. p, q-Stirling numbers and set partition statis-
tics. J. Combin. Theory Ser. A 56 (1991), 27-46.

WERMAN, M., AND ZEILBERGER, D. A bijective proof of Cassini’s Fibonacci
identity. Discrete Math. 58 (1986), 109.

84

IIIIIIIIIIIIIII

111111111111111111111111111

3 1293 02845 9943