La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

Partition Identities
Alexander D. Healy
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-calledLectureHallPartitionsofBousquet-M´elouand Eriksson. Along the way, we will briefly visit some earlier results such as the Rogers-Ramanujan identities which have also extended the study of partition identities.
Definition 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 defined 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.
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 coefficient 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 coefficient 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 i2i1 1x1x ioddioddi=1
and then
∞ ∞ Y Y 2i2 4 6 1x(1x)(1x)(1x)∙ ∙ ∙ i P(x(1 +) = x=) = D i2 3 1x(1x)(1x)(1x)∙ ∙ ∙ i=1i=1 Y 1 1 = = =P(x) O 3 5 2i1 (1x)(1x)(1x)∙ ∙ ∙1x 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:
Proposition 2.1 (The First Rogers-Ramanujan Identity).The number of partitions ofn such that the difference 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 differs 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 difference 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 differs 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 thani1of the parts are1and whereλjλjk+12is equal to the number of partitions ofninto parts not congruent to0or±imodulo2k+ 1.
Example 2.6.Lettingi= 2andk= 2Letting, we obtain the first Rogers-Ramanujan identity. i= 1andk= 2, we obtain the second Rogers-Ramanujan identity.
Example 2.7.Lettingi= 1andk= 3, we find that the number of partitions ofnsuch that λjλj22and 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].
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 thedifferenceFor example, thebetween parts in partitions. distinctness condition in Theorem 1.2 is equivalent to requiring that all parts differ by at least 1, whereas one of the conditions of the Rogers-Ramanujan identities is that all parts differ 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,andtheyhavedevelopedthetheoryofLectureHall Partitions” as a very different generalization of Theorem 1.2.
Definition 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. Therstresultistheso-calledLectureHallTheorem,rstpresentedbyBousquet-Me´louand Eriksson in [2]. Theorem 3.2 (Lecture Hall Theorem).LetLnbe the set of lecture hall partitions of lengthn. Then n1 X Y 1 |λ| q= 2i+1 1q λ∈Lni=0 The left-hand side of this expression is simply the weight generating function of lecture hall N partitions. That is, the coefficient 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 1n1 1 2i+1was the weight generating function for partitions with odd parts,2i+1is i=0 1q i=0 1q the weight generating function for partitions with small odd parts: 1,3,5, . . . ,2n1. 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, . . . ,2n1.” 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 = 231: (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 (Refined Lecture Hall Theorem).Given a lecture hall partitionλ, define its even weight,|λ|eand itsodd weight,|λ|o, by n1n b c b c−1 2 2 X X |λ|e=λn2k|λ|o=λn2k1 k=0k=0 Then n1 X Y 1 |λ|e|λ|o x y= i+1i 1x 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´louandErikssonsworkin[3]:a-lecture hall partitions.
a-Lecture Hall Partitions
Thus far, we have looked at lecture hall partitions as defined in Definition 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 definition seems somewhat arbitrary. To generalize this definition of lecture hall partitions, we introduce thea-lecture hall partitions:
Definition 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 Definition 3.1 are simply the (1,2,3, . . . , n)-lecture hall partitions according to this new definition. We will denote the weight generating function ofa-lecture hall 1 partitions bySa(q), so for example,S(1,2,3,...,n)(q) =3 2n1, by Theorem 3.2. (1q)(1q)∙∙∙(1q) The main objective of this generalization will be to find other sequencesa= (a1, a2, . . . , an), such thatSa(q) has the form 1 Sa(q) =ei6=ej(1) e1e2en (1q)(1q)∙ ∙ ∙(1q)
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´louandErikssonsresultsconcerning aSince our main objective is to understand the novel aspects of Bousquet--lecture hall partitions. M´elouandErikssonsapproach,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) Definition 4.2.Given a sequencea= (a1, a2, . . . , an), thestandarda-lecture hall partitions,λ, are defined by: (i) λ= (0, . . . ,0, ai, ai+1, . . . , an) Definition 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 (finite) 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.
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 first 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
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 1x 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 formxy, 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 termxyfrom (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 1x y µ∈Ri=1 Now, since we would like to computeSa(x, y), we need to find 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 specific type of sequence for which both these factors can be computed more easily. Definition 4.4.A sequencea= (a1, a2, . . . , an)is called a(k, `)-sequenceif it satisfies the following recursion relation:
a2n=`a2n1a2n2 (4) a2n+1=ka2na2n1 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=F2i1whereFidenotes 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 finite(k, `)-sequence of lengthnand letabe the(k, `)-∗ ∗ sequence defined bya= 0,a= 1. Ifnis even, then 1 2 n Y 1 Sa(x, y) =a a 1x y i i i=1