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<j => 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_i<M_i .

Then f(M,i) is in S(M) but cannot be in S(L) by this observation .

So S is injective.

Finally, we show S is surjective. For any T in X, we find a parition L
such that S(L)=T .

Suppose T has particles p_1>p_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.

A truly superlative answer from rbnn, extraordinarily thorough, and
explained in a fluent and understandable manner.  I cannot give high
enough praise!