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!) |