Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/ium/postscript/s01/notes/scomb01.ps Дата изменения: Thu Jan 23 16:43:48 2003 Дата индексирования: Sat Dec 22 19:28:43 2007 Кодировка: Поисковые слова: южная атлантическая аномалия

S. V.Duzhin
COMBINATORICS OF SYMMETRIC GROUPS
Lecture 1: Partitions
A partition of a non-negative integer n is a nonincreasing sequence of positive integers
 = [ 1 ;  2 ; : : : ;  k ] such that  1 +  2 +


+  k = n. In case of repeating elements,
exponential notation is used: [2,1 2 ]=[2,1,1]. For example, there are 5 partitions of 4; we list
them below together with their graphical representation by means of Young diagrams:
[4] [3,1] [2,1 ] [1 ]
[2 ]
2 2 4
The Young diagram of a partition [ 1 ;  2 ; : : : ;  k ] is made up of  1 cells in the first row,
 2 cells in the second row, etc., all left justified. It is merely a graphical means to visualize
the partition.
Let p(n) be the number of partitions of n. Here is the table of values of p(n) for small
n:
n 0 1 2 3 4 5 6 7 8 9 10
p(n) 1 1 2 3 5 7 11 15 22 30 42
(The value p(0) = 1 has the following meaning: there is a unique partition of 0 into
positive integers, viz. the partition into an empty set of parts.)
The generating function of the sequence p(n) can be written as an infinite product
invented by L. Euler:
Theorem 1.
1
X
n 0
p(n)x n
=
1
Y
k=1
1
1 x k
(1)
Exercise 1. Prove this formula.
Hint. Expand each factor 1=(1 x k ) as a series and think about the coefficient of x n in
the infinite product.
Exercise 2. Prove that the number of partitions of a given number n into odd parts is
equal to the number of partitions of n into different parts. (For example, #{[5],[3,1 2 ],[1 5 ]}
= #{[5],[4,1],[3,2]}.)
Hint. Modify appropriately the proof of Theorem 1.
The denominator in the right hand side of equation 1 expands as follows.
1

Theorem 2. (Euler's pentagonal theorem.)
1
Y
k=1
(1 x k ) =
1
X
k=1
( 1) k x
k(3k+1)
2 = 1 +
1
X
k=1
( 1) k (x k(3k 1)
2 + x
k(3k+1)
2 ): (2)
Idea of the proof. The coefficient of x n in the expansion of the left side product is equal
to #E n #O n , where E n is the set of partitions of n into an even number of different
summands, while O n is the set of partitions of n into an odd number of different summands.
The crucial observation is that for almost all n (in fact, for all n except the pentagonal
numbers n = k(3k + 1)=2, k 2 Z) there is a one-to-one correspondence between E n and
O n established by either cutting off the base of the Young diagram and attaching it to
its slope or, vice versa, cutting off the slope and attaching it to the base:
base
slope
Corollary (recurrent formula for the number of partitions). For any n > 0 we have:
p(n) =
1
X
k=1
( 1) k
h
p n
k(3k 1)
2


+ p n
k(3k + 1)
2

i
= p(n 1) + p(n 2) p(n 5) p(n 7) + p(n 12) + : : : ;
where p(n) = 0, if n < 0.
Exercise 3. Let (n) denote the sum of all divisors of n. Find a relation between (n)
and p(n) and deduce a recurrent formula for (n), similar to the previous Corollary.
Euler's identity 2 inspired a lot of investigations on combinatorial identities that led
to a host of beautiful formulas. For example:
Jacobi's triple identity.
1
Y
k=1
(1 x k y k
)(1 x k 1 y k
)(1 x k y k 1
) =
1
X
n=1
( 1) n x n(n+1)=2 y n(n 1)=2 : (3)
Exercises. (a) Prove Jacobi's identity using Eq. (2). (b) Vice versa, deduce the pen-
tagonal theorem as a special case of Jacobi's identity. (c) Differentiate (3) over y at y = 1
and write the result as a formula for
Q 1
k=1
(1 x k ) 3 .
Definition. A plane partition of the number n is a set of positive integers with total
sum n, arranged as a Young diagram with nonincreasing rows and columns.
Example. 1 1
3
1
2
2
2
4 4
1
is a plane partition of 21.
2

Denote by (n) the number of plane partitions of n. For example, p(0) = p(1) = 1,
p(2) = 3, p(3) = 6.
Theorem 3. (MacMahon).
1
X
n=0
(n)x n =
1
Y
k=1
1
(1 x k ) k
:
3