# Partition identities

Publié par

### opakito

Publié le :
samedi 25 juin 2011

Lecture(s) :
73

Nombre de pages :
9

Voir plus
Voir moins

Introduction

Partition Identities

Alexander D. Healy ahealy@fas.harvard.edu

May 2001

Apartitionof a positive integern(or a partition of weightn) is a non-decreasing sequenceλ= P k λisuch thatλi=n. Theλi’s are thepartsof the (λ1, λ2, . . . , λk) of non-negative integersi=1 partitionλ. Integer partitions are of particular interest in combinatorics, partly because many profound questions concerning integer partitions, solved and unsolved, are easily stated, but not easily proved. Even the most basic question “How many partitions are there of weightn?” has no simple solution. Remarkably, however, there are a variety of partition identities of the form “The number of partitions ofnsatisfying conditionAis equal to the number of partitions ofn satisfying condition B,” even though no simple formulas are known for the number of partitions ofnsatisfyingAorB. The motivating example of such a partition identity is due to Euler: The number of partitions ofninto distinct parts is equal to the number of partitions ofninto odd parts. We will start here and our ultimate goal will be to examine a very recent development in thetheoryofpartitionidentities:theso-called“LectureHallPartitions”ofBousquet-M´elouand Eriksson. Along the way, we will brieﬂy visit some earlier results such as the Rogers-Ramanujan identities which have also extended the study of partition identities.

1

Preliminaries

Deﬁnition 1.1.Apartitionof a positive integern(or a partition of weightn) is a non-decreasing P k ative integersλisuch thatλ=n sequenceλ= (λ1, λ2, . . . , λk)of non-negi=1i. The weight,|λ|, P k of the partitionλis deﬁned to beλi. i=1 For example, there are 5 partitions of 4: (1,1,1,1),(1,1,2),(2,2),(1,3),(4). The study of partitions identities begins with the following result due to Euler. The proof of this result will demonstrate the power of using generating functions to prove partitions identities. The use of generating function permeates the study of partition identities and we will again en-counter similar uses of generating functions when we examine more recent development in partition identities. Theorem 1.2 (Euler).The number of partitions ofnno part is repeatedinto distinct parts (i.e. more than once) is equal to the number of partitions ofninto odd parts. Proof.Letp(n) be the number of partitions ofninto distinct parts. For instance,p(5) = 3, D D since (1,4),(2,3) and (5) are the only partitions of 5 into distinct parts.

1

Similarly, letp(n) be the number of partitions ofninto odd parts. For instance,p(5) = 3, O O since (1,1,1,1,1),(1,1,3) and (5) are the only partitions of 5 into odd parts. We will show thatp(n) =p(n) by showing that their generating functions,P(x) andP(x), D O D O are equal:

2 2 P(x) =p(0) +p(1)x+p(2)x+∙ ∙ ∙=p(0) +p(1)x+p(2)x+∙ ∙ ∙=P(x) D D D D O O O O Q ∞ i Consider the productF(x(1 +) = x). When this product is expanded, every term has i=1 i1+i2+∙∙∙+i` the formxwhere theijFurthermore, for any set of distinct’s are distinct. ij’s, the term i1+i2+∙∙∙+i`n i1+i2+∙∙∙+i` xTherefore, the number of occurrences ofoccurs only once. x=xis exactly n the number of ways to partitionninto distinct parts. So the coeﬃcient ofxinF(x) isp(n). D Q ∞ i ThereforeP(x(1 +) = x). i=1 D Q ∞ i2i3i Similarly, we consider the productG(x(1 +) = x+x+x+∙ ∙ ∙). If we expand this iodd n k1i1+k2i2+∙∙∙+k`i` product, each term has the formx=xterm represents a natural partition. This ofninto odd parts; in particular, if we construct a partition withk1parts equal toi1, andk2 parts equal toi2and so forth, we have a partition ofninto odd parts (since all theij’s are odd). Conversely, if we take any partition ofninto odd parts, we can write that partition (uniquely) as k1i1+k2i2+∙ ∙ ∙+k`i`, where theij’s are the (odd) parts that occur and thekj’s are the number of n times eachijoccurs. Therefore, the coeﬃcient ofxinG(x) is equal to the number of partitions ofninto odd parts, orp(nfollows that). It G(x) =P(x). O O To prove thatP(x) =P(x) we must show that D O ∞ ∞ Y Y i i2i3i (1 +x(1 +) = x+x+x+∙ ∙ ∙) i=1iodd This can be achieved by manipulatingP(x) as follows: O ∞ ∞ ∞ Y Y Y 1 1 i2i3i P(x(1 +) = x+x+x+∙ ∙ ∙=) = O i2i−1 1−x1−x ioddioddi=1

2

and then

∞ ∞ Y Y 2i2 4 6 1−x(1−x)(1−x)(1−x)∙ ∙ ∙ i P(x(1 +) = x=) = D i2 3 1−x(1−x)(1−x)(1−x)∙ ∙ ∙ i=1i=1 ∞ Y 1 1 = = =P(x) O 3 5 2i−1 (1−x)(1−x)(1−x)∙ ∙ ∙1−x i=1 ThusP(x) =P(x) and sop(n) =p(n) for alln. D O D O

Some Generalizations of Euler’s Theorem

Now it is natural to ask whether there exist other similar partition identities, and indeed there are many. TheRogers-Ramanujan identites, stated here without proof, are two other examples of this type of partition identity:

2

Proposition 2.1 (The First Rogers-Ramanujan Identity).The number of partitions ofn such that the diﬀerence between any two parts is at least2is equal to the number of partitions ofn such that each part is congruent to1or4modulo5.

Example 2.2.There are4partitions of9such that each part diﬀers by at least2:(1,3,5),(1,8), (2,7),(3,6)are also exactly. There 4partitions of9such that each part is congruent to1or4 modulo5:(1,1,1,1,1,1,1,1,1),(1,1,1,1,1,4),(1,1,1,6),(9).

Proposition 2.3 (The Second Rogers-Ramanujan Identity).The number of partitions ofn such that1is not a part and the diﬀerence between any two parts is at least2is equal to the number of partitions ofnsuch that each part is congruent to2or3modulo5.

Example 2.4.There are2partitions of9such that each part diﬀers by at least2and where1is not a part:(2,7),(3,6)are also exactly. There 2partitions of9such that each part is congruent to 2or3modulo5:(2,2,2,3),(2,7).

It turns out that the Rogers-Ramanujan identities can be generalized even further, as is demon-strated by the following result due to Gordon from which the Rogers-Ramanujan identities follow as corollaries. Again, the proof is omitted.

Theorem 2.5.The number of partitions(λ1, λ2, . . . , λr)ofnsuch that no more thani−1of the parts are1and whereλj−λj−k+1≥2is equal to the number of partitions ofninto parts not congruent to0or±imodulo2k+ 1.

Example 2.6.Lettingi= 2andk= 2Letting, we obtain the ﬁrst Rogers-Ramanujan identity. i= 1andk= 2, we obtain the second Rogers-Ramanujan identity.

Example 2.7.Lettingi= 1andk= 3, we ﬁnd that the number of partitions ofnsuch that λj−λj−2≥2and where1is not a part is equal to the number of partitions ofninto parts not congruent to0or±1modulo7.

The proof of Theorem 2.5 is similar to that of Theorem 1.2 in that two generating functions are shown to be equal in order to show that these partitions are equinumerous for alln. However, the generating functions for the proof of Theorem 2.5 are considerably more complicated than those of Theorem 1.2 and the manipulations are far from trivial. The proof and necessary background material are developed in [1].

3

Lecture Hall Partitions

Thus far, there has been a common theme among the generalizations of Theorem 1.2: all these identities have been concerned with thediﬀerenceFor example, thebetween parts in partitions. distinctness condition in Theorem 1.2 is equivalent to requiring that all parts diﬀer by at least 1, whereas one of the conditions of the Rogers-Ramanujan identities is that all parts diﬀer by at least 2. However, one could just as easily interpret the distinctness condition in Theorem 1.2 to require that the quotient of successive parts be greater than 1. This is exactly the approach that Bousquet-M´elouandErikssonhavetaken,andtheyhavedevelopedthetheoryof“LectureHall Partitions” as a very diﬀerent generalization of Theorem 1.2.

3

Deﬁnition 3.1.Alecture hall partition of lengthnis a partitionλ= (λ1, λ2, . . . , λn)satisfying λ1λ2λn 0≤ ≤ ≤ ≤∙ ∙ ∙ 1 2n Such partitions are calledlecture hall partitionbecause they correspond to all the possible ways in which an n-row lecture hall can be constructed such that every seat has a clear view of the lecturer (assuming that all rows are at integer heights). If a person in rowjis to have an unobstructed view of the lecturer (at height 0), thenh(j)/jmust be greater than or equal toh(i)/ifor alli < j whereh(i) denotes the height of theiHowever, we will see that the applications of lecture-th row. hall partitions are far more interesting than simply enumerating possible lecture hall designs. Theﬁrstresultistheso-calledLectureHallTheorem,ﬁrstpresentedbyBousquet-Me´louand Eriksson in [2]. Theorem 3.2 (Lecture Hall Theorem).LetLnbe the set of lecture hall partitions of lengthn. Then n−1 X Y 1 |λ| q= 2i+1 1−q λ∈Lni=0 The left-hand side of this expression is simply the weight generating function of lecture hall N partitions. That is, the coeﬃcient ofqis the number of lecture hall partitions of lengthnand weightNright-hand side should look familiar from Theorem 1.2; for the same reason that. The Q Q ∞1n−1 1 2i+1was the weight generating function for partitions with odd parts,2i+1is i=0 1−q i=0 1−q the weight generating function for partitions with small odd parts: 1,3,5, . . . ,2n−1. Therefore, Theorem 3.2 can be interpreted as saying: “The number of lecture hall partitions of lengthnand weightNis equal to the number of partitions ofN1into small odd parts: ,3,5, . . . ,2n−1.” Example 3.3.There are4lecture hall partitions of length3and weight7: (0,0,7),(0,1,6),(0,2,5),(1,2,4) There are also exactly4partitions of7into odd parts no greater than5 = 2∙3−1: (1,1,1,1,1,1,1),(1,1,1,1,3),(1,1,5),(1,3,3) Infact,Bousquet-Me´louandErikssonprovethefollowingmoregeneralresult. Theorem 3.4 (Reﬁned Lecture Hall Theorem).Given a lecture hall partitionλ, deﬁne its even weight,|λ|eand itsodd weight,|λ|o, by n−1n b c b c−1 2 2 X X |λ|e=λn−2k|λ|o=λn−2k−1 k=0k=0 Then n−1 X Y 1 |λ|e|λ|o x y= i+1i 1−x y λ∈Lni=0 The usefulness of this bivariate generating function identity will become clearer when we exam-ine the theory ofaFor the moment, we will simply note that the substitution-lecture hall partitions. ofq=x=yyields Theorem 3.2. Now, with this background in the basic ideas of lecture hall partitions, we will study the most generalandmostpowerfulaspectofBousquet-Me´louandEriksson’sworkin[3]:a-lecture hall partitions.

4

4

a-Lecture Hall Partitions

Thus far, we have looked at lecture hall partitions as deﬁned in Deﬁnition 3.1. However, since we are not very interested in using lecture hall partitions to enumerate lecture hall designs, the choice of the values 1,2,3, . . .as the denominators in the deﬁnition seems somewhat arbitrary. To generalize this deﬁnition of lecture hall partitions, we introduce thea-lecture hall partitions:

Deﬁnition 4.1.Letabe a non-decreasing sequence of positive integers,a= (a1, a2, . . . , an). An a-lecture hall partition of lengthnis a partitionλ= (λ1, λ2, . . . , λn)satisfying λ1λ2λn 0∙ ∙ ∙ ≤ ≤ ≤ ≤ a1a2an So the lecture hall partitions of Deﬁnition 3.1 are simply the (1,2,3, . . . , n)-lecture hall partitions according to this new deﬁnition. We will denote the weight generating function ofa-lecture hall 1 partitions bySa(q), so for example,S(1,2,3,...,n)(q) =3 2n−1, by Theorem 3.2. (1−q)(1−q)∙∙∙(1−q) The main objective of this generalization will be to ﬁnd other sequencesa= (a1, a2, . . . , an), such thatSa(q) has the form 1 Sa(q) =ei6=ej(1) e1e2en (1−q)(1−q)∙ ∙ ∙(1−q)

for ifSa(q) is of this form, then we may conclude that the number ofa-lecture hall partitions of lengthnand weightNequals the number of partitions ofNinto elements of{e1, e2, . . . , en}. WewillnowstudythemajoraspectsofBousquet-Me´louandEriksson’sresultsconcerning aSince our main objective is to understand the novel aspects of Bousquet--lecture hall partitions. M´elouandEriksson’sapproach,theproofsofseveralresultswillbeomittedinordertoavoid obfuscating the overall structure of their work. Any omitted details are available in [3]. Ultimately we wish to understand the weight generating function,Sa(q), ofa-lecture hall par-titions. For this pursuit to be fruitful, however, it is better to consider the bivariate case, as in Theorem 3.4. In particular, we will study X |λ|e|λ|o Sa(x, y) =x y λ∈L

(i) Deﬁnition 4.2.Given a sequencea= (a1, a2, . . . , an), thestandarda-lecture hall partitions,λ, are deﬁned by: (i) λ= (0, . . . ,0, ai, ai+1, . . . , an) Deﬁnition 4.3.Ana-lecture hall partitionλ= (λ1, λ2, . . . , λn)is said to bereducedif, for alli, (i)n λ−λ(as elements ofZ) is not ana-lecture-hall partition. We will denote the (ﬁnite) set of reduceda-lecture hall partitions byR.

It can be shown that anya-lecture hall partition of lengthncan be uniquely decomposed as P n (i) (i) λ=µ+kiλ, where theµarereducedlecture hall partitions, where theλarestandard i=1 lecture hall partitions and where thekiare positive integers. The proof of this fact is routine and available in either [2] or [3]. P n (i) Furthermore, eachµ+kiλwill constitute ana-lecture hall partition, since a sum of i=1 a-lecture hall partitions is clearly also anaTherefore, there is a natural-lecture hall partition.

5

bijection betweena-lecture hall partitions of lengthnand (n+ 1)-tuples, (µ, k1, k2, . . . , kn) where µis a reduced partition and where theki’s are non-negative integers. P n (i) Since we will be working in the bivariate case, let us ﬁrst note that|λ|o=|µ|o+ki|λ|oand i=1 P P n n (i) (i) similarly|λ|e=|µ|e+ki|λ|e, wheneverλ=µ+kiλwe are ready to consider. Now i=1i=1 the following sum and product (whereRdenotes the set of reduceda-lecture hall partitions):

X |µ|e|µ|o x y µ∈R

(2)

n n Y Y 1(i) (i) (i) (i) (i) (i) |λ|e|λ|o2|λ|e2|λ|o3|λ|e3|λ|o = (1 +x y+x y+x y+∙ ∙ ∙) (3) (i) (i) |λ|e|λ|o 1−x y i=1i=1 P n When the product in (3) is expanded, for every linear combinationkiλ(i) there will be i=1 P P n(i)n(i) ki|λ|oki|λ|e a term of the formx∙y, and furthermore, each such term will arise exactly i=1i=1 once. So if we expand the product of equations (2) and (3), every term will be constructed by P P n(i)n(i) |µ|e|µ|oki|λ|oki|λ|e choosing a termx yfrom (2) and by choosing a termx∙yfrom (3). i=1i=1 P n (i) Therefore, by the uniqueness of the decompositionλ=µ+kiλ, everya-lecture hall partition i=1 λis accounted for exactly once in the product of equations (2) and (3). So we may write: ! n X Y 1 |µ|e|µ|o Sa(x, y) =x y∙(i) (i) |λ|e|λ|o 1−x y µ∈Ri=1 Now, since we would like to computeSa(x, y), we need to ﬁnd a way to compute the two factors of the above expression. Unfortunately, it is not clear how to compute both these factors for arbitrary sequencesa= (a1, a2, . . . , anaerrdesf,oBroeu,fprooimnttohniwsleuoqseu-.t)´hMT and Eriksson restrict their study to a speciﬁc type of sequence for which both these factors can be computed more easily. Deﬁnition 4.4.A sequencea= (a1, a2, . . . , an)is called a(k, `)-sequenceif it satisﬁes the following recursion relation:

a2n=`a2n−1−a2n−2 (4) a2n+1=ka2n−a2n−1 Example 4.5.An interesting example of a(k, `)-sequence is the sequence of every other Fibonacci number. If we choosea1= 1,k= 3and`= 3then(a1, a2, a3, . . .) = (1,3,8, . . .)and in general ai=F2i−1whereFidenotes theiWe will see this sequence again shortly-th Fibonacci number. when we examine a limit theorem concerninga-lecture hall partitions.

Under the assumption thatais a (k, `)-sequence, the following theorem is proved in [3]. ∗ Theorem 4.6.Fixk, `≥2. Letabe a ﬁnite(k, `)-sequence of lengthnand letabe the(k, `)-∗ ∗ sequence deﬁned bya= 0,a= 1. Ifnis even, then 1 2 n Y 1 Sa(x, y) =∗ a a 1−x y i i i=1

6

Soyez le premier à déposer un commentaire !

Vous aimerez aussi

### Partition algorithms

de opakito

### Partition complète, junkspace—progress, junkspace hyphen progress questionmark

de PSIMIKAKIS-CHALKOKONDYLIS

### Chanson à boire et chansons paillardes

de opakito

### Le nouvel opium du peuple russe

de opakito

suivant