Partitions
This chapter studies partitions, and shows how the techniques presented throughout the book can be applied for this purpose. First we study partitions of integers, and their Ferrer diagrams. Then, we present the Stirling numbers of the first kind by their
- PDF / 268,089 Bytes
- 7 Pages / 477 x 684 pts Page_size
- 28 Downloads / 273 Views
Partitions
7.1
Partitions
This chapter deals with theory that is not frequently encountered in olympiad problems. However, this is a very good example of how the tools we have developed so far can be used. The theory presented here can still be useful when solving problems. Given a set A, a partition of A is a family of non-empty pairwise disjoint subsets of A whose union is A. In what follows we are going to assume that A is a finite set. A partition of A into k parts can be represented as a distribution of the elements of A in k indistinguishable bins (the elements of A are distinguishable), where in every bin there is at least one element. For example, the partitions of {1, 2, 3} are {{1}, {2}, {3}}, {{1}, {2, 3}}, {{1, 3}, {2}}, {{1, 2}, {3}} and {{1, 2, 3}}. Given a positive integer n, a partition of n is an ordered list of positive integers (n1 , n2 , . . . , nk ) such that n1 ≥ n2 ≥ n3 ≥ · · · ≥ nk and n1 + n2 + · · · + nk = n. That is, the partitions of n are the ways to see n as a sum of positive integers regardless of the order. For example, the partitions of 4 are (4), (3, 1), (2, 2), (2, 1, 1), (1, 1, 1, 1). The partitions of n into k parts can be represented as a distribution of n indistinguishable elements in k indistinguishable bins, so that each bin contains at least one element. Partitions of integers are much harder to count than partitions of sets. However, we can find many relations of the following type. Example 7.1.1 The numberof partitions of n with exactly k parts is equal to the number of partitions of n + k2 with exactly k parts, all of them different. Solution To each partition (n1 , n2 , . . . , nk ) of n with k parts we are going to assign the sequence (m1 , m2 , . . . , mk ) so that mi = ni + k − i for all i. It is clear that (m1 , m2 , . . . , mk ) is a partition of n + (k − 1) + (k − 2) + · · · + 1 + 0 = n + k2 and that all its elements are different. Also, the function thus defined is bijective, which gives us what we wanted. Given a partition (n1 , n2 , . . . , nk ), we can give it a graphic representation. This is known as the Ferrer diagram of the partition. To do this, we place in the plane n1 squares in a column. Then we place a column of n2 squares so that the lowest one is P. Soberón, Problem-Solving Methods in Combinatorics, DOI 10.1007/978-3-0348-0597-1_7, © Springer Basel 2013
93
94
7
Partitions
to the right of the lowest square of the original n1 squares, and so on. For example, if n = 8, the Ferrer diagram of the partition (3, 2, 2, 1) is:
Given a partition (n1 , n2 , . . . , nk ) we can reflect its Ferrer diagram across the diagonal. What we obtain is the Ferrer diagram of a new partition (n1 , n2 , . . . , nt ) of n, called the conjugate partition of (n1 , n2 , . . . , nk ). We say that (n1 , n2 , . . . , nk ) is self-conjugate if (n1 , n2 , . . . , nk ) = (n1 , n2 , . . . , nt ).
In the figure we show that the conjugate partition to (3, 2, 2, 1) is (4, 3, 1). Several properties of partitions can be deduced by conjugating Ferrer diagrams. Examp
Data Loading...
