Publié par
###
opakito

Publié le :
jeudi 21 juillet 2011

Lecture(s) :
150

Nombre de pages :
6

Publications similaires

de opakito

de opakito

A Combinatorial Proof of Andrews’ Smallest Parts Partition Function

Kathy Qing Ji Center for Combinatorics, LPMC-TJKLC Nankai University, Tianjin 300071, P.R. China ji@nankai.edu.cn

Submitted: Jan14, 2008; Accepted:Mar 19, 2008; Published: Apr 10, 2008 Mathematics Subject Classiﬁcation: 05A17, 11P81

Abstract We give a combinatorial proof of Andrews’ smallest parts partition function with the aid of rooted partitions introduced by Chen and the author.

1 Introduction We adopt the common notation on partitions as used in [1].A partitionλof a positive integernis a ﬁnite nonincreasing sequence of positive integers λ= (λ1, λ2, . . . ,λr) P r such thatλi=n.Thenλiare called the parts ofλnumber of parts of. Theλis i=1 called the length ofλ, denoted byl(λ).The weight ofλis the sum of parts, denoted by |λ|.We letP(n) denote the set of partitions ofn. Letspt(n) denote the number of smallest parts in all partitions ofnandns(λ) denote the number of the smallest parts inλ, we then have X spt(n) =ns(λ).(1.1) λ∈P(n) Below is a list of the partitions of 4 with their corresponding number of smallest parts. We see thatspt(4) = 10. λ∈ P(4)ns(λ) (4) 1 (3,1) 1 (2,2) 2 (2,1,1) 2 (1,1,1,1) 4

the electronic journal of combinatorics15(2008), #N12

1

The rank of a partitionλintroduced by Dyson [6] is deﬁned as the largest part minus the number of parts, which is usually denoted byr(λ) =λ1−l(λ).LetN(m, n) denote the number of partitions ofnwith rankm. Atkinand Garvan [4] deﬁne thekth moment of the rank by +∞ X k Nk(n) =m N(m, n).(1.2) m=−∞ In [2], Andrews shows the following partition function onspt(n) analytically: Theorem 1.1 (Andrews) 1 spt(n) =np(n)−N2(n),(1.3) 2 wherep(n)is the number of partitions ofn. At the end of the paper, Andrews states that “In addition the connection ofN2(n)/2 to the enumeration of 2-marked Durfee symbols in [3] suggests the fact that there are also serious problems concerning combinatorial mappings that should be investigated.” In this paper, we give a combinatorial proof of (1.3) with the aid of rooted partitions introduced by Chen and the author [5], instead of using a 2-marked Durfee symbols. A rooted partitionofncan be formally deﬁned as a pair of partitions (α, β), where |α|+|β|=nandβThe union of the parts ofis a nonempty partition with equal parts. αandβare regarded as the parts of the rooted partition (α, β). Example 1.2There are twelve rooted partitions of4: (∅,(4)) ((1),(3)) ((3),(1)) ((2),(2)) (∅,(2,2)) ((1,1),(2)) ((2,1),(1)) ((2),(1,1)) ((1,1,1),(1)) ((1,1),(1,1)) ((1),(1,1,1)) (∅,(1,1,1,1)) LetRP(n) denote the set of rooted partitions ofn.

2 Combinatorialproof In this section, we will ﬁrst build the connection between rooted partitions and ordinary 1 partitions, and then interpretnp(n), N2(n) in terms of rooted partitions (see Theorems 2 2.2 and 2.5).In this framework, a combinatorial justiﬁcation of (1.3) reduces to building a bijection between the set of ordinary partitions ofnand the set of the rooted partitions (α, β) ofnwithβ1> α1. We now make a connection between rooted partitions and ordinary partitions by ex-tending the construction in [5, Theorems 3.5, 3.6].

the electronic journal of combinatorics15(2008), #N12

2

Lemma 2.1The number of rooted partitions ofnis equal to the sum of lengths over partitions ofn, namely X X 1 =l(λ).(2.4) (α,β)∈RP(n)λ∈P(n)

Proof.For a given partitionλ= (λ1, λ2, . . . ,λl)∈ P(n), we could getl(λ) distinct rooted partitions (α, β) ofnby designating any part ofλas the part ofβand keep the remaining parts ofλas parts ofα. Assumethatdis a part that appearsmdtimes (md≥2) in λ, we then chooseβas the partition withdrepeateditimes, wherei= 1,2, . . . , md. Conversely, for a rooted partition (α, β), we could get an ordinary partitionλby uniting the parts ofαandβ. It’sclear to see that there areexactlyl(λ) distinct rooted partitions corresponding toλinRP(n). For example, there are ﬁve partitions of 4:(4),(3,1),(2,2),(2,1,1),(1,1,1,1), and the sum of lengths is twelve.From Example 1.2, we see that there are also twelve rooted partitions of 4. We are ready to interpretnp(n) in terms of rooted partitions using the construction in Lemma 2.1.

Theorem 2.2np(n)is equal to the sum ofβ1over all rooted partitions(α, β)ofn, that is X np(n) =β1.(2.5) (α,β)∈RP(n) P Proof.Asnp(n) =|λ|, it suﬃces to prove λ∈P(n) X X |λ|=β1.(2.6) λ∈P(n) (α,β)∈RP(n)

From Lemma 2.1, one sees that forλ∈ P(n), there exists exactlyl(λ) distinct rooted partitions (α, β) corresponding to it inRP(nthe sum of). Furthermore,β1over thesel(λ) distinct rooted partitions equals to|λ|, this is because thatβis obtained by designating some equal parts ofλThus we get the identity (2.6).as its parts. 1 For the combinatorial explanation ofN2(n) in terms of rooted partitions, we ﬁrst rein-2 1 terpretN2(nHere we need to deﬁne the conjugate of the) in terms of ordinary partitions. 2 0 00 0 partition. Fora partitionλ= (λ1, . . . ,λr),the conjugate partitionλ= (λ ,λ. . . ,λ ,) of 1 2t 0 λby settingλto be the number of parts ofλthat are greater than or equal toi. Clearly, i 0 0 l(λ) =λandλ1=l(λtherefore straightforward to verify the following partition). It’s 1 identity: X X 2 2 λ=l(λ).(2.7) 1 λ∈P(n)λ∈P(n) We have the following lemma:

the electronic journal of combinatorics15(2008), #N12

3

Lemma 2.3 X X 1 2 N2(n) =l(λ)−[λ1∙l(λ)].(2.8) 2 λ∈P(n)λ∈P(n) Proof.From the deﬁnition of rank and the moment of rank, we know that X 2 1 (λ1−l(λ)) N2(n) =,(2.9) 2 2 λ∈P(n) and X XX X 2 (λ1−l(λ1)) 1 2 2 =λ1+l(λ)−[λ1∙l(λ)].(2.10) 2 22 λ∈P(n)λ∈P(n)λ∈P(n)λ∈P(n) 1 Thus we obtain the combinatorial explanation (2.8) forN2(n) when substitute (2.7) into 2 (2.10). We next transform Lemma 2.3 on ordinary partitions to the following statement on rooted partitions by the construction in Lemma 2.1. Lemma 2.4 X X 1 N2(n) =[l(α) +l(β)]−h(α, β),(2.11) 2 (α,β)∈RP(n) (α,β)∈RP(n) whereh(α, β)denote the largest part of the rooted partition(α, β), that ish(α, β) =β1if α1≤β1; otherwiseh(α, β) =α1. Proof.From Lemma 2.1, it’s known that forλ∈ P(n), we will get exactlyl(λ) distinct rooted partitions (α, β) corresponding to it inRP(nfor each of these). Furthermorel(λ) distinct rooted partitions (α, β), we havel(α) +l(β) =l(λ) andh(α, β) =λ1. 2 Therefore, the sum ofl(α) +l(β) over alll(λ) rooted partitions (α, β) is equal tol(λ) , and we deduce that X X 2 l(λ[) =l(α) +l(β)].(2.12) λ∈P(n) (α,β)∈RP(n) Furthermore, the sum ofh(α, β) over alll(λ) rooted partitions (α, β) is equal toλ1∙l(λ), so we have X X [λ1∙l(λ)] =h(α, β).(2.13) λ∈P(n) (α,β)∈RP(n) Hence we deduce (2.11) from Lemma 2.3, (2.12), and (2.13).

the electronic journal of combinatorics15(2008), #N12

4

When applying the conjugation intoαin the rooted partition (α, β), we see that each 0 00 rooted partition (α, β) withl(α) corresponds to a rooted partition (βα ,) withαsuch 1 0 thatl(α) =αwe obtain the following partition identity:. Thus 1 X X l(α) =α1.(2.14) (α,β)∈RP(n) (α,β)∈RP(n) Similarly, when employing the conjugation toβin (α, β), we ﬁnd that each rooted 0 00 partition (α, β) withl(β) corresponds to a rooted partition (βα ,) withβsuch that 1 0 l(β) =βwe have:. So 1 X X l(β) =β1.(2.15) (α,β)∈RP(n) (α,β)∈RP(n) When subscribe (2.14) and (2.15) into (2.11), we obtain the following combinatorial 1 interpretation forN2(n) in terms of rooted partitions. 2 1 Theorem 2.5N2(n)is equal to the sum ofα1over all rooted partitions(α, β)ofnwith 2 α1< β1, add the sum ofβ1over all rooted partitions(α, β)ofnwithα1≥β1, namely X X 1 N2(n) =α1+β1.(2.16) 2 (α,β)∈RP(n) (α,β)∈RP(n) α1<β1α1≥β1 Based on Theorems 2.2 and 2.5, we may reformulate Andrews’ smallest parts partition function (1.3) as the following theorem: Theorem 2.6 X XX X ns(λ) =β1−α1+β1.(2.17) (α,β)∈RP(n) (α,β)∈RP(n) λ∈P(n) (α,β)∈RP(n) α1<β1α1≥β1 Proof.Evidently, the proof of this theorem is equivalent to the proof of the following partition identity: X X ns(λ) =[β1−α1].(2.18) (α,β)∈RP(n) λ∈P(n) α1<β1 We now build a bijectionψbetween the set of ordinary partitions ofnand the set of rooted partitions (α, β) ofnwithα1< β1for. Furthermore,λ∈ P(n) and (α, β) =ψ(λ), we havens(λ) =β1−α1. The mapψ:Forλ∈ P(n), we will construct a rooted partition (α, β) whereβ1> α1. 0 00 00 Assume thatl(λ) =landλ1=a, consider its conjugateλ= (. . . , λλ , λ ,) whereλ=l. 1 2a1 0 Supposed that the largest part ofλrepeatsmltimes, that is, there aremlparts of size 0 00 linλ .We then havens(λ) =λ−λ. Deﬁneβas the partitions with parts of sizel 1ml+1 0 repeatedmltimes, and keep the remaining parts ofλas parts ofα.

the electronic journal of combinatorics15(2008), #N12

5

0 0 From the above construction, one could see thatα1=λandβ1=λ, that is ml+1 1 0 0 β1> α1. Also,ns(λ) =λ−λ=β1−α1. Hencethe mapψsatisﬁes the conditions 1ml+1 and one can easily see that this process is reversible.Thus we complete the proof of Theorem 2.6. For example, there are ﬁve partitions of 4:(4),(3,1),(2,2),(2,1,1),(1,1,1,1). We also have ﬁve rooted partitions (α, β) withα1< β1.

(∅,(4)) ((1),(3)) (∅,(2,2)) ((1,1),(2)) (∅,(1,1,1,1)).

Applying the above bijection, we get the following correspondence:

(4)(∅,(1,1,1,1)) (2,1,1)((1),(3))

(3,1)((1,1),(2)) (1,1,1,1)(∅,(4)).

(2,2)(∅,(2,2))

Acknowledgments.I would like to thank the referee for helpful suggestions.This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, the Ministry of Science and Technology, and the National Science Foundation of China.

References [1] G.E. Andrews, The Theory of Partitions, Addison-Wesley Publishing Co., 1976. [2] G.E. Andrews, The number of smallest parts in the partitions ofn, J. Reine Angew. Math., to appear. [3] G.E. Andrews, Partitions, Durfee symbols and the Atkin-Garvan momemts of ranks, Invent. Math., to appear. [4] A.O.L.Atkin and F. Garvan, Relations between the ranks and cranks of partitions, Ramanujan J.7(2003) 343–366. [5] WilliamY. C. Chen and Kathy Q. Ji, Weighted forms of Euler’s theorem, J. Combin. Theory Ser. A 114 (2007) 360–372. [6] F.J. Dyson, Some guesses in the theory of partitions,Eureka(Cambridge) 8 (1944) 10–15.

the electronic journal of combinatorics15(2008), #N12

6

Partagez cette publication