Notes on partitions and their generating functions

1 Notes on partitions and their generating these Notes we are concerned with partitions of a numbern, as opposed to partitions of a partition ofnis a combination (unordered, with repetitions allowed) of positive integers, calledtheparts, that add up ton. In other words, a partition is a multiset of positive integers, and it isa partition ofnif the sum of the integers in the multiset isn. It is conventional to write the partsof a partition in descending order, for example(7,5,2,2)is a partition of 16 into 4 parts. We write| |=nto indicate that is a partition ofn. Someauthors also use the notation `nfor define the following quantities enumerating partitions :p(n,k) = number of partitions ofnwithkpartsp(n) = total number of partitions ofnq(n,k) = number of partitions ofnwithkdistinct partsq(n) = total number of partitions ofnwith distinct partsFor example, the partitions of 5 are (5), (4,1), (3,2), (3,1,1), (2,2,1), (2,1,1,1), and (1,1,1,1,1).

2 Thusp(5) = 7,p(5,1) = 1,p(5,2) = 2,p(5,3) = 2,p(5,4) = 1, andp(5,5) = 1, whileq(5) = 3,q(5,1) = 1, andq(5,2) = diagram and conjugate partitionTheFerrers diagram, also calledYoung diagram, of a partition `nis a rectangular array ofnboxes, or cells, with one row of lengthjfor each partjof .For example, the diagram of (7,5,2,2) a partition `nis the partition ofnwhose diagram you get by reflecting thediagram of about the diagonal so that rows become columns and columns become rows. We usethe notation for the conjugate of . In our example above, with = (7,5,2,2), the diagram of is1and so we see that = (7,5,2,2) = (4,4,2,2,2,1,1).Some obvious but useful facts about are, first, ( ) = , that is, the conjugate of the conjugateis the original partition and, second, the number of parts of is equal to the largest part of.

3 Asa consequence, we see thatp(n,k), the number of partitions ofnwithkparts, is also the numberof partitions ofnwith largest part 1= conjugate can be computed directly without drawing the Ferrers diagrams. Let =( 1, 2,.., l) and denote its conjugate by = ( 1, 2,.., m). Notice thatl= 1andm= iis the length of columniin the diagram of , and there is one cell in this column for everyrow of length at leasti. Therefore iis equal to the number of parts iin , or equivalently thelargestjsuch that j i. For example, we compute(6,6,5,3,3,3,2,1,1) = (9,7,6,3,3,2)because 9is the last 1, 7is the last 2, 6is the last 3, 3is the last part 4 and also the last 5,and 2is the last 6 in .A partition is calledself-conjugateif = . This means its Ferrers diagram is symmetric, asin for example = (5,5,3,2,2).

4 We definek(n) = number of self-conjugate partitions number turns up fairly often in partition theory. One interesting fact aboutk(n) is given bythe following theorem:Theorem:k(n) is also the number of partitions ofnintodistinct, :We ll give a bijection from{self-conjugate `n}to{ `nwith distinct odd parts}.Given a self-conjugate , define ( ) to be the partition whose parts are the hooks in thediagram of , as illustrated below:=++,so that ((5,5,3,2,2)) = (9,7,1)Each hook has odd size because it is symmetric about the middle, and each hook is strictly largerthan the next one, which nests inside it. Therefore ( ) has distinct odd parts. On the other hand,given distinct odd numbers, we can form corresponding symmetric hooks and nest them togetherinto a diagram. This operation clearly defines 1and thus shows we have a functions for partitionsWe begin with the generating functionP(x) = p(n)xnwhich counts all partitions of allnumbersn, with weightxnfor a partition choose an arbitrary partition of unrestrictedn, we can decide independently for each positiveintegerihow many times to includeias a part of.

5 Each use ofias a part contributesito the total sizen. The generating function for the choiceof any number of repetitions of the partiis therefore 1 +xi+x2i+ = 1/(1 xi). Multiplyingfor alliwe getP(x) = np(n)xn= i=111 xi=1(1 x)(1 x2)(1 x3) .This infinite product need not disturb us. If we want a particular coefficientp(n) we need onlymultiply out those factors involvingxto a powernor less, and there finitely many of these. Thusthe infinite product makes sense since only a finite number of the factors contribute to any an exercise to convince yourself this works, you could multiply out the product11 x11 x211 x311 x411 x5 ,keeping track only of terms up to degreex5. Then compare the coefficients with the values ofp(0)throughp(5) which you compute by actually listing all partitions ofnforn= 0 to strategy we used to write downP(x) lends itself to endless variations.

6 Here are someexamples.(1) To count partitions whose parts are k, use only the factors fori= 1,2,..,kto getP k(x) = p k(n)xn=k i=111 xi=1(1 x)(1 x2) (1 xk).Taking the conjugate partition gives a bijection between partitions ofnwith parts kand parti-tions ofnwith at mostkparts. ThereforeP k(x) also counts partitions with at mostkparts.(2) To count partitions with exactlykparts, we can again take conjugates and count partitionswith largest part equal tok. This is almost the same problem as in (1), except that we shouldreplace the factor 1/(1 xk) withxk+x2k+ =xk/(1 xk) to account for the requirement thatwe take at least one part equal tok. This gives the generating functionPk(x) = np(n,k)xk=xk(1 x)(1 x2) (1 xk).(3) To determine the numbero(n) of partitions ofnwith only odd parts, we use only the factorsfor odd values ofito get the generating functionO(x) = no(n)xn= iodd11 xi=1(1 x)(1 x3)(1 x5).

7 (4) To count partitions with distinct parts, we must choose for eachiwhether to use the partionce, or not at all, that is, our partition is a set rather than a multiset. Thus the factor 1/(1 xi)inP(x) must be replaced by (1 +xi), giving the generating functionQ(x) = nq(n)xn= i=1(1 +xi) = (1 +x)(1 +x2)(1 +x3) .(5) To count partitions with distinct, odd parts, we combine what we did in examples (3) and(4) to get the generating functionK(x) = nk(n)xn= iodd(1 +xi) = (1 +x)(1 +x3)(1 +x5) .According to the theorem in the previous section, this is also the generating function countingself-conjugate partitions :K(x) = nk(n)xn.(6) Another way to get a generating function forp(n,k) is to use a two-variable generatingfunction for all partitions , in which we count each partition = ( 1, 2.)

8 , k)`nwith weightykxn, wherenis the size andkis the number of parts. The monomial giving the weight contributionfor a single part ofinow becomesyxiinstead of justxiand accordingly we get the generatingfunctionP(x,y) = n,kp(n,k)ykxn= i=111 yxi=1(1 yx)(1 yx2)(1 yx3) .Settingy= 1 gets us back to our original generating functionP(x). identitiesIn the last section we countedp(n,k) in two essentially different ways. One was direct, using the2-variable generating fucntionP(x,y) = n,kp(n,k)ykxn= i=111 other was indirect, using conjugation to getPk(x) = np(n,k)xn=xk(1 x) (1 xk).We can make this last equation into a 2-variable generating function by summing with a factorykfor allk:P(x,y) = n,kp(n,k)ykxn= kPk(x)yk= kykxk(1 x) (1 xk).As a result we arrive at apartition identity i=111 yxi= k=0ykxk(1 x) (1 xk)expanding an infinite product as an infinite sum of finite products.

9 Though we derived it combi-natorially, this is a purely algebraic identity. One theme in combinatorics is to find combinatorialexplanations for algebraic identities like this. Often such identities are first discovered in someentirely different context, and are understood combinatorially only can obtain further identities by more subtle combinatorial analysis of Ferrers diagrams. Asan example, we will work out an analog for partitions with distinct parts of what we just did that if haskdistinct parts, then its diagram must contain the diagram of the staircase partition (k 1,k 2,..,1). Furthermore, it is not hard to see that the rows of the difference arejust the parts of an ordinary partition withkparts, and this latter partition can be arbitrary. Thefigure below illustrates this with = (7,6,3,2).

10 The diagram of is shown on the left, with the staircase diagram contained in it marked by corresponding difference partition is shown on the right. To choose a partition withkdistinctparts, we can choose an ordinary partition withkparts and then boost it with a staircase. Thishas the effect of adding(k2)to its total size, or multiplying the generating function byx(k2). Weobtain the generating functionQk(x) = nq(n,k)xn=xk+(k2)(1 x) (1 xk).Now, proceeding just as above but for partitions with distinct parts, we arrive at the partitionidentity forQ(x,y) = n,kq(n,k)ykxn: i=1(1 +yxi) = k=0ykxk+(k2)(1 x) (1 xk)The connection between partition combinatorics and algebraic identities can also be applied inreverse, to get surprising combinatorial facts. As an example, consider the generating functionsfound in the previous section for partitions with distinct parts,Q(x) = (1 +x)(1 +x2)(1 +x3) ,and for partitions with odd parts,O(x) =1(1 x)(1 x3)(1 x5).