View Question
 Question
 Subject: Partitions Category: Science > Math Asked by: dubois-ga List Price: \$50.00 Posted: 20 Nov 2002 17:40 PST Expires: 20 Dec 2002 17:40 PST Question ID: 111628
 ```I was given a large set of practice problems to prepare for a standardized combinatorics exam, and I have managed to complete all but one, which is on partition theory, a subject in which I have had very little experience. I would be most grateful for a solution to this problem. I will type out the problem exactly as written, with some notational clarifications in brackets. Although it looks long, each of these problems are designed to take one hour to complete, and for the other problems which looked equally long, I found that an hour wasn't too far off. Anyway, here goes: If lambda [I will abbreviate L = lambda] is a partition, let L' denote the conjugate partition and let p(L) = L'_{1} [that is, L' with 1 as a subscript] denote the number of parts of L. Associate a set S(L) of integers to a partition L by taking the set of all numbers of the form (L_{i}-i) for all i (by convention, L_{k} = 0 for k > p(L)). Given a subset S of the integers, call a non-negative element of S a particle, and call a negative integer not contained in S a hole. (a) If T is a set of integers with a finite number of particles and holes, show that the following number: |{x e S(L) : x !e T}| - |{x e T : x !e S(L)}| is well-defined and independent of L [I write e instead of epsilon for inclusion, and !e is a crossed-out epsilon, that is, "not a member of"] b. Show that the map L -> S(L) gives a bijection between partitions and sets of integers such that the number of particles is finite and equal to the number of holes. Give a combinatorial interpretation of the number of particles of S(L) in terms of the Ferrers diagram of L; give a formula for |L| in terms of the locations of the particles and holes of S(L). c. Show that S(L') = {-1-x : x e Z | x !e S(L)}; in other words, conjugation switches particles and holes. Use this to show that the number of self-conjugate partitions of n equals the number of partitions of n into distinct odd parts. (Hint: What happens to S(L) when the Ferrers diagram of L is enlarged by one square?) And that's it. The problem is titled "Frobenius notation for partitions" if that helps. Thanks again for any replies.```
 ```Thank you for your question. I was quite interested in this question because in my dissertation I needed to compute representations of the symmetric group, for which one uses Ferrers (or Young) diagrams. I had never done real combinatorics on them, however. Unfortunately, I was due to catch a plane to fly cross-country not long after I saw your question. I had to solve some parts of your question on the plane, and am now painfully typing in the results on an emacs-less and expensive Kinko's computer far from home. Therefore, I will be a little more concise than I like to be; and there are likely to be some formatting problems. As always, I will be happy to answer requests for clarifications; however, as I have limited access to a computer, I may not be able to reply as quickly as as I would like. I will assume that you are familiar already with the representation of a partition as a Ferrers diagram, and I will not expand on that here. Definition: If L is a partition and i a positive integer, let f(L,i) be L_i - i . Lemma: If L is a partition, then f(L,i) and f(L,j) are distinct for i not equal to j. Proof: Suppose i>j. Then f(L,i) = L_i - i <=L_j - i < L_j - j We will be doing "Ferrers induction" several times: in order to prove something is true about S for all partitions, we show it is true for the empty partition of 0, and then show that if it is true for a partition it is true for another partition formed from the first by adding a dot to its Ferrers diagram. Formally: Definition: If M is a partition, we say that the partition L is equal to Q(M,i) if the Ferrers diagram for L is formed from that for M by adding a single dot in row i. That is: L_j = M_j if j not equal i L_i = M_i + 1 Whenever we write Q(M,i), we will assume i is chosen so that Q(M,i) is a partition. Notation: I use "+" for set union and "-" for set difference. Lemma: Let L=Q(M,i) . Then S(L)=S(M)+{f(L,i)}-{f(M,i)}, where f(L,i) is not in S(M) and f(M,i) is not in S(L). Proof: Note that f(L,i)=f(M,i)+1 . The lemma follows from the earlier definitions and the definition of S. Specifically, since f(L,i) is in S(L) because of the contribution of the i'th row of i, by the first lemma, it cannot be equal to another f(L,j)=f(M,j), so that f(L,i) is not in S(M). Similarly, f(M,i) is not equal to any other f(M,j) so is not equal to any other f(L,j) so the result follows. ----- Part a ----- By Ferrers induction. Fix T and let A(L) be S(L)-T and B(L) be T-S(L) . Let phi(T,L) be |A(L)| - |B(L)| If L is the empty partition (), then S(L) is the negative numbers, so that A(L) is the particles of T and B(L) the holes of T. Hence, phi(T) is the difference in the number of particles and holes of T, and is finite. Now let L=Q(M,i) . Then S(L)= S(M)+{f(L,i)}-{f(M,i)}. Let n=f(L,i) and m = f(M,i), so that S(L)=S(M)+{n} - {m} . By inspection, if T contains n and m, then A(L)=A(M) and B(L)=B(M), so phi(T,L)=phi(T,M). If T contains n and not m, then A(L)=A(M)-{m} and B(L)=B(M)-{n}, so again phi(T,L) is unchanged. If T contains m and not n, then A(L)=A(M)+{n} and B(L)=B(M)+{m} . Finally, if T contains neither m nor n, then A(L)=A(M)-{m}+{n} and B(L)=B(M) . In each case the unions with singleton sets are disjoint, as are the singleton sets given; the result now follow by Ferrers induction. Definition: We let phi(T) be the above difference between numbers of particles and holes of T. ----- Part b ----- Let X be the set of subsets of the integers with finite and equal numbers of particles and holes. We show first the the range of S is contained in X. It is clear that the number of particles and holes of S(L) is finite. Equality follows because, in the notation of part a and letting T be S(L), A(L) = S(L)-T=S(L)-S(L)={} B(L)=T-S(L)={} So phi(T)=phi(T,L)=0-0=0. This proves that the range of S is contained in X . To show S is injective, observe that i f(L,i)>f(L,j) for any partition L by the proof of the first lemma . Suppose S(M) = S(L) and let i be the smallest positive integer for which L_i is not equal to M_i, say L_ip_2>p_3...>p_k>0 and holes 0>h_k>h_{k-1}>...>h_1 . Enumerate the integers less than zero that are not holes by 0>a_1>a_2>.... We let L be the partition such that L = p + i for i=1,...,k . i i L = a + j for j > k j j-k Clearly the L_i are nonincreasing and the L_j are nonincreasing. The smallest L_k can be is k, since the p's are nonnegative, and the largest L_j can be -1+k+1=k. Hence, all the L are nonincreasing. For high values of j, a = -(k+j) j so that for high enough j (when there are no holes smaller than a_j) we have L = -(j-k+k)+j = 0 j Hence, L forms a partition, and S(L)=T. We have now shown that S has range within X and is injective and surjective. S is therefore a bijection onto X. -------- Part (b) note i Since S(L) enumerates the number of elements to the right of the main diagonal of the Ferrers diagram for L, the number of particles of S(L) is the number of rows that intersect the main diagonal. Here, the main diagonal of a Ferrers diagram is the elements whose column and row indices are the same. For example, consider the partition: L=(5,3,2,1,1) with diagram (main diagonal is x'd out) x.... .x. .. . . S(L) is {4,1,-1,-3,-4} with particles {4,1}, as can be seen from by looking at the right of the x's. ---------- Part (b) note ii Claim: The total number of elements in L, that is the total number of dots in the Ferrers diagram for L, is the sum of the absolute values of the holes and particles of S(L) . By Ferrers induction. The claim is certainly true for L=(), as here S(L) has no holes and no particles. Suppose the claim is true for M and let L=Q(M,i) . Then by the second lemma, S(L)=S(M)+{n}-{m} where n=m+1 . It is easy to see that this means the sum of the absolute values of the particles and holes in S(L) is one greater than the corresponding sum for S(M). Indeed, if m>=0, then the sum of the particles increases by 1 and that of the holes is unchanged. If m<-1, then the sum of the particles is unchanged and the sum of the absolute values of the holes increases by 1, since the S(L) replaces the hole at n in S(M) by a hole at m. Finally, if m=-1, then the sum of the particles is unchanged but S(L) gains a new hole at -1. The result follows. ---- Part (c) ---- Recall that the Ferrers diagram for L' is formed from the Ferrers diagram for L by reflecting the Ferrers diagram for L about the main diagonal. We use Ferrers induction again. For the base case L=L'=(), and since S(L) is the negative integers, as we saw earlier, {-1-x: x not in S(L)} ={-1-x:x>=0} ={y:y<0} =S(L') Suppose the claim is true for partition M with conjugate M'. Let L=Q(M,i) . Let j=M_i+1, so that the Ferrers diagram for L is formed from that of M by putting a dot in row i and column j of the diagram for M. Then it is not difficult to see that the Ferrers diagram for L' is formed from that of M' by adding a dot to row j and column i of the Ferrers diagram for M'. That is: L'=Q(M',j) Note as well that M'_j=i-1 and that L'_j=i . Hence, by the second lemma, S(L)=S(M)+{f(L,i)}-{f(M,i)} = S(M)+{j-i} - {j-1-i} Similarly, S(L') = S(M')+{f(L',j)}-{f(M',j)} = S(M') + {i-j} - {i-1-j} Now, by the induction hypothesis and the expression for S(L), S(M')={-1-x: x not in S(M)} ={-1-x: x not in S(L)} +{-1 - (j-i)} - {-1 - (j-1-i)} ={-1-x: x not in S(L)} - {i-j} + {i-1-j} If we substitute this expression for S(M') into the earlier expression for S(L'), we obtain: S(L')= {-1-x: x not in S(L)} and the result follows. [Note that we are overloading + for numeric addition and set union; and overloading '-' for numeric subtraction and set difference] Note also that this result can be rephrased as: The particles of S(L') are {-1-x: x is a hole in L} The holes of S(L') are {-1-x: x is a particle in L} ---- Part (c) final note ---- We now show that the number of partitions L of n such that L=L' equals the number of partitions M of n such that the nonzero M_i are odd and distinct. Fix n>0, and let V be the set of self-conjugate partitions of n, and let W be the set of partitions of n with distinct odd parts. We give a bijection R:V->W as follows. Given a self-conjugate partition L, suppose S(L) has particles p_1>p_2>...>p_k and holes 0>h_k>h_{k-1}>...>h_1 . Then by the above proof in part (c), since the particles of L' are -1-h_1, -1-h_2, ..., -1-h_k, and since L'=L, it follows that p_i= -1-h_i . Now let R(L) be the partition with k parts, whose i'th part has value R(L)_i = p_i+(-h_i) = 2*p_i + 1 Each part of R(L) is odd, and the parts are distinct since the p_i are decreasing . Finally, R(L) is a partition of L since the sum of the parts equals the sum of the absolute values of the holes and the parts of L, which equals n by the result of part (b). Thus, R:V->W . To show that R is a bijection, we give an inverse R':W->V . Given M in W, let the parts of M be M_1, M_2, ..., M_k be distinct and odd and positive, with sum n. Let p_i be (M_i-1)/2 for i=1,...,k . Let h_i be -1-p_i . Let T be the set of integers that has particles {p_i} and holes {h_i} , i=1,..,k . By part (b), there is a unique partition L such that T=S(L) ; L is a partition of L by the condition on |L| . Clearly R(R'(M))=M and R'(R(L))=L and the bijection follows, as does the result. --- I hope that this is helpful to you and I wish you the best of luck on the combinatorics exam (on which, I should remark, it is most unlikely any problem as hard as this would appear!)``` Clarification of Answer by rbnn-ga on 22 Nov 2002 17:07 PST ```I would like to take this opportunity to correct a couple of errors in my answer, to expand the analysis of part(c) final note, and finally to offer some intuitive justification for some of the algebraic notation throughout the answer. First, in the analysis in part (a), I stated that if L is the empty partition, then A(L) is the particles of T and B(L) is the holes. Actually, A(L) is the holes of T and B(L) is the particles. phi(T) is thus the difference between the number of holes and number of particles of T, rather than the negative. This error does not affect the proof or any other results, since we are only concerned with T with equal numbers of particles and holes. Second, a couple of times in part (c) I wrote " a partition of L" where L is a partition. I meant here "a partition of n". Third, the explicit definition of R' in part (c) final note is missing. After the sentence beginning "By partt (b), there is a unique partition L..." the sentence "We define R'(M) to equal L" should be inserted. Fourth, I would like to expand a bit on the proof that R(R'(M)) =M for a partition of distinct odd parts M. Let us observe first of all that R'(M) is indeed in V, that is R'(M)'=R'(M) . Indeed by construction and the earlier result, the particles of S(R'(M)' ) equals {-1-x: x is a hole of S(R'(M))} = {-1-h_i: i=1,..,k} ={p_i=1,...k} =particles of S(R'(M)). Similarly, the holes of S(R'(M))= the holes of S(R'(M)') . Hence, S(R'(M))=S(R'(M)'); by the bijectivity of S, R'(M)=R'(M)' and therefore R'(M) is indeed self-conjugate. Now we show that R(R'(M))=M. By the construction of the R'(M), S(R'(M)) has particles p_1,...,p_k and holes h_1,...,h_k. By the definition of R, R(R'(M)) has k parts, the i'th of which has length p_i-h_i =(M_i-1)/2 - -1 -(M_i-1)/2 = M_i Hence, R(R'(M))=M . The proof that R'(R(L))=L for a self-conjugate partition is similar, relying again on the bijectivity of S. That R is a bijection now follows. Finally, I would like to provide an intuitive analysis of what is going on here. The "rank" of a Ferrers diagram for a partition L is the length of the main diagonal in the diagram; that is, the maximum i such that there is a dot at the intersection of row i and column i of the diagram. The particles of S(L) are the number of dots to the right of the main diagonal in the first r rows. The holes of S(L) are the negatives of the number of dots on or below the main diagonal in the first r rows. (Thus, it is now clear why the number of dots in the diagram is the sum of the particles and the negatives of the number of holes) If L is self-conjugate, then R(L) is constructed by grabbing all the dots below the diagonal in the i'th column, rotating them 90 degrees, and appending them to the i'th row, for i=1,...,r . The geometrical description of holes here is all that is needed to really understand the intution; the technical device of "Ferrers induction" is just a way to formalize things. I think also this exercise may have almost intentionally obscured the simple geometric intution by its "holes" notation. I hope that this clarification was helpful.``` Request for Answer Clarification by dubois-ga on 23 Nov 2002 00:04 PST ```rbnn, I cannot thank you enough for yet another excellent answer. Your solution and clarification were immensely helpful. Would you be kind enough to tell me how much you spent at Kinko's in conjunction with the write-up for this problem? You went out of your way to help me in a timely manner and you should not be paying for that. Thanks.``` Clarification of Answer by rbnn-ga on 24 Nov 2002 10:55 PST ```Thanks for the comments; they are appreciated. It's not necessary to reimburse for Kinko's: it turned out not to cost much, and was offset anyway by the money saved by my being able to work on this problem on the plane and thus not having to purchase a book to amuse myself. I'm glad you found the answer useful, though.```
 dubois-ga rated this answer: and gave an additional tip of: \$5.00 ```A truly superlative answer from rbnn, extraordinarily thorough, and explained in a fluent and understandable manner. I cannot give high enough praise!```