Integer Partitions / Edition 2

Paperback (Print)
Buy New
Buy New from BN.com
$42.53
Used and New from Other Sellers
Used and New from Other Sellers
from $25.00
Usually ships in 1-2 business days
(Save 44%)
Other sellers (Paperback)
  • All (8) from $25.00   
  • New (5) from $43.37   
  • Used (3) from $0.00   

Overview

The aim of this introductory textbook is to provide an accessible and wide-ranging introduction to partitions, without requiring anything more of the reader than some familiarity with polynomials and infinite series. Many exercises are included, together with some solutions and helpful hints.
Read More Show Less

Editorial Reviews

From the Publisher
"...until now there has not been a good introduction to the subject at an elementary level. Integer Partitions...is written at a level that most undergraduates, and even many high school students, could follow quite easily."
-MAA Reviews, Darren Glass, Columbia University

"This book is written in a very easy and friendly style. The authors start from scratch and lead the readers from the easy to the unsolved problems. It is really a pleasure to read."
-Mathematical Reviews

Read More Show Less

Product Details

  • ISBN-13: 9780521600903
  • Publisher: Cambridge University Press
  • Publication date: 5/28/2010
  • Edition description: New Edition
  • Edition number: 2
  • Pages: 152
  • Sales rank: 1,430,062
  • Product dimensions: 5.98 (w) x 8.98 (h) x 0.35 (d)

Meet the Author

George E. Andrews is Evan Pugh Professor of Mathematics at the Pennsylvania State University. He has been a Guggenheim Fellow, the Principal Lecturer at a Conference Board for the Mathematical Sciences meeting, and a Hedrick Lecturer for the MAA. Having published extensively on the theory of partitions and related areas, he has been formally recognized for his contribution to pure mathematics by several prestigious universities and is a member of the National Academy of Sciences (USA).

Kimmo Eriksson is Professor of Mathematics at Mälardalen University College, where he has served as the dean of the Faculty of Science and Technology. He has published in combinatorics, computational biology and game theory. He is also the author of several textbooks in discrete mathematics and recreational mathematics, and has received numerous prizes for excellence in teaching.

Read More Show Less

Read an Excerpt


Cambridge University Press
0521841186 - Integer Partitions - by George E. Andrews and Kimmo Eriksson
Excerpt



Chapter 1

Introduction


Mathematics as a human enterprise has evolved over a period of ten thousand years. Rock carvings suggest that the concepts of small counting numbers and addition were known to prehistoric cavemen. Later, the ancient Greeks invented such things as rational numbers, geometry, and the idea of mathematical proofs. Arab and Chinese mathematicians developed the handy positional system for writing numbers, as well as the foundation of algebra, counting with unknowns. From the Renaissance and onward, mathematics has evolved at an accelerating pace, including such immensely useful innovations as analytical geometry, differential calculus, logic, and set theory, until today's fruitful joint venture of mathematics and computers, each supporting the other.

We will delve into, or at least touch upon, many of these modern developments - but really, this book is about mathematical statements of a kind that would have made sense already to the cavemen! One could imagine a petroglyph or cave painting of the following kind:


The concepts involved here are just small counting numbers, equality of numbers, addition of numbers, and the distinction between odd and even numbers. What is shown in the table is that for at least up to four animals, they can be lined up in rows of odd lengths in as many ways as in rows of different lengths. Written on today's blackboard instead of prehistoric rock, the table would have a more efficient design:

1 + 1 2
1 + 1 + 1
3
3
2 + 1
1 + 1 + 1 + 1
3 + 1
4
3 + 1

The fact that there will always be as many items in the left column as in the right one was first proved by Leonhard Euler in 1748. But it is quite possible that someone observed the phenomenon earlier for small numbers, since it takes no more advanced mathematics than humans have accessed since the Stone Age. Nowadays, objects such as 3 + 1 or 5 + 5 + 3 + 2 are called integer partitions. Stating it differently, an integer partition is a way of splitting a number into integer parts. By definition, the partition stays the same however we order the parts, so we may choose the convention of listing the parts from the largest part down to the smallest.

Euler's surprising result can now be given a more precise formulation: Every number has as many integer partitions into odd parts as into distinct parts. The table continues for five and six:

1 + 1 + 1 + 1 + 1
3 + 1 + 1
5
5
4 + 1
3 + 2
1 + 1 + 1 + 1 + 1 + 1
3 + 1 + 1 + 1
3 + 3
5 + 1
6
5 + 1
4 + 2
3 + 2 + 1

EXERCISES

1. Continue the table from seven up to ten and check for yourself that Euler was correct! See if you can obtain some intuition for why the numbers of integer partitions of the two kinds are always equal. (Difficulty rating: 1)

Statements of the flavor "every number has as many integer partitions of this sort as of that sort" are called partition identities. The above partition identity of Euler was the first, but there are many, many more. It is an intriguing fact that there are so many different and unexpected partition identities. Here is another, very famous, example: Every number has as many integer partitions into parts of size 1, 4, 6, 9, 11, 14,... as into parts of difference at least two.

The numbers 1, 4, 6, 9, 11, 14,... are best described as having last digit 1, 4, 6, or 9. Another way to put it is that when these numbers are divided by 5, the remainder is 1 or 4. Counting with remainders is called modular arithmetic and will appear several times in this book. In fact, it is striking that partition identities, their proofs and consequences, involve such a wide range of both elementary and advanced mathematics, and even modern physics. We hope that you will find integer partitions so compellingly attractive that they will lure you to learn more about these related areas too.

The last identity above was found independently by Leonard James Rogers in 1894 and Srinivasa Ramanujan in 1913. The tale of this identity is rich and has some deeply human aspects, one of which is that Rogers was a relatively unknown mathematican for a long time until the amazing prodigy Ramanujan rediscovered his results twenty years later, thereby securing eternal fame (at least among mathematicians) also for Rogers. The field of integer partitions comes with an unusually large supply of life stories and anecdotes that are romantic or astonishing, or simply funny. They are best presented, and best appreciated, in conjunction with the mathematics itself. Welcome to the wonderful world of integer partitions!





Chapter 2

Euler and beyond


In this chapter, we will show how identities such as Euler's, and many more, can be proved by the bijective method. However, although the bijective method is elegant and easy to understand, it is not the method Euler himself used. Euler worked with an analytic tool called generating functions, which is very powerful but demands a bit more mathematical proficiency. We will return to Euler's method in Chapter 5.

Highlights of this chapter
  • We introduce basic set theory: union, intersection, and cardinality of sets.
  • We show how bijections (one-to-one pairings of two sets) can be used to prove identities.
  • A bijective proof of Euler's identity is given (the number of partitions into distinct parts equals the number of partitions into odd parts) using merging of equal parts, the inverse of which is splitting of even parts.
  • Euler's identity is generalized to other "Euler pairs," that is, sets M and N such that the number of partitions into distinct parts in M equals the number of partitions into parts in N.

2.1 Set terminology

We will need some concepts from set theory. In particular, a set is a collection of distinct objects, usually called elements. We can describe a set by listing its elements within curly brackets. For example, {1, 2, 4, 5} is a set of four elements, all of which are integers. It is important to remember that the order of the elements implied by the list is not part of the set; thus the lists {4, 5, 2, 1} and {1, 2, 4, 5} describe the same set.

If you discard some elements of a set and retain the rest, you obtain a subset. The symbol ⊂ means "is a subset of." For instance, {2, 5} ⊂ {1, 2, 4, 5}.

The intersection of two sets N and N′ is the set of those elements that lie in both sets, denoted by NN′. Two sets are disjoint if they have no element in common, that is, if their intersection is empty. The union of two sets N and N′ is the set NN′ containing all elements found in any or both of these sets. Thus if N = {1, 4} and N′ = {2, 4, 5}, then their intersection is NN′ = {4} and their union is NN′ = {1, 2, 4, 5}. Intersections and unions are conveniently illustrated by so-called Venn diagrams, such as:

The number of elements in a set N is denoted by |N| and is often called the cardinality (or just the size) of the set.


EXERCISE

2. In the above example, we had |N| = 2, |N′| = 3, |NN′| = 1, and |NN′| = 4. It is no coincidence that 2 + 3 = 1 + 4; in fact, for any sets N and N′, it is always true that |N| + |N′| = |NN′| + |NN′|. Why? Draw the conclusion that the size of the union of two sets equals the sum of their respective sizes if, and only if, the two sets are disjoint. (Difficulty rating: 1)



2.2 Bijective proofs of partition identities

In order to formulate partition identities precisely and concisely, some notation is needed. Let p(n) denote the number of integer partitions of a given number n. The function p(n) is called the partition function. For example, we have p(4) = 5, since there are five partitions of the number four:

4, 3+1, 2+2, 2+1+1 and 1+1+1+1.

In partition identities, we are often interested in the number of partitions that satisfy some condition. We denote such a number by p(n | [condition]). For example, Euler's identity takes the form

p(n | odd parts) = p(n | distinct parts) for n ≥ 1. (2.1)

Now let us reflect a moment on how such an identity can be proved. For every single value of n, we can verify the identity by listing the partitions of both kinds, counting them, and finding the numbers to be equal. But the identity is stated for an infinite range of values of n, so we cannot verify it case by case; instead we must find some general argument that holds for each and every positive value of n. A natural idea would be to find a general way of counting the partitions, yielding an explicit expression, the same for both sides of the identity. In other words, if we could show that p(n | odd parts) equals, say, n2 + 2 (or some other expression), and if we likewise could show that p(n | distinct parts) equals the same number, then we would of course have proved that the identity holds. But can we find such an expression for these functions? From the partition tables in the previous chapter, including Exercise 1, we can compute the first few values:

The tabulated values do not seem to suggest any simple function such as a polynomial in n. Consequently this approach fails to prove the identity. But we fail because we try to accomplish more than we actually need! If we want to verify that the number of objects of a type X is equal to the number of objects of a type Y, then we do not need to find the actual numbers - it is enough to pair them up and show that every object of type X is paired with a unique object of type Y and vice versa. The "cave paintings" of Chapter 1 constitute such a pairing between partitions of n into odd parts and partitions of n into distinct parts, for n = 2, 3, 4. Such a one-to-one pairing between two sets is called a bijection. Hence, in order to prove a partition identity, we just need to find a bijection between the partitions in question.

It is not obvious what a bijection between partitions could look like. An integer partition of n is just a collection of parts summing up to n, so a bijection between partitions must be described in terms of operations on parts. A simple operation is splitting an even part into two equal halves. The inverse of this operation is merging two equal parts into one part twice as large. This gives an immediate bijective proof of a partition identity:

p(n | even parts) = p(n | even number of each part) for n ≥ 1. (2.2)

Study how the bijection works for n = 6:

(2.3)



EXERCISE

3. For odd n, there can be no partitions into even parts, nor into parts with an even number of each size. Why? For even n ≥ 2, find an alternative bijective proof of the above identity by finding bijections for each of the two equalities
p(n | even parts) = p(n/2) = p(n | even number of each part). (2.4)
(Difficulty rating: 2)



2.3 A bijection for Euler's identity

Returning to Euler's identity, what must a bijection look like? It must have the property that when we feed it a collection of odd parts, it delivers a collection of distinct parts with the same sum. Its inverse must do the converse.

From odd to distinct parts: If parts are distinct, there are no two copies of the same part. Hence, if the input to the bijection contains two copies of a part, then it must do something about it. As we have seen above, a natural thing to do is to merge the two parts into one part of double size. We can repeat this procedure until all parts are distinct - since the number of parts decreases at every operation, this must occur at the latest when only one part remains. For example,

Tracing our steps back to odd parts: The inverse of merging two equal parts is the splitting of an even part into two equal halves. Repeating this procedure must eventually lead to a collection of odd parts - since the size of some parts decreases at every operation, this must occur at the latest when all parts equal one. For example,

It might seem that there is an arbitrariness in the order in which we choose to split (or merge) the parts. However, it is clear that splitting one part does not interfere with the splitting of other parts, so the order in which parts are split does not affect the result. Neither does the order of merging, since merging is the inverse of splitting.

Above, we have described a procedure of repeated merging of pairs of equal parts that we can feed any partition into odd parts, and that will result in a partition into distinct parts. Inverting every step gives a procedure of repeated splitting of even parts that takes any partition into distinct parts and results in a partition into odd parts. Hence, this procedure is a bijection proving Euler's identity. For n = 6, the bijection works as follows:

(2.5)

A common feeling among combinatorial mathematicians is that a simple bijective proof of an identity conveys the deepest understanding of why it is true. Test your own understanding on a few exercises!


EXERCISES

4. Why does the same bijection also prove the following stronger statement for n ≥ 1?
p(n | even number of odd parts) = (2.6)
p(n | distinct parts, number of odd parts is even), (2.7)
as well as the same statement with both "even" changed to "odd." (Difficulty rating: 2)
5. In the bijection, we are merging pairs of equal parts. Change "pairs" to "triples"! If we merge triples of equal parts until no such triples remain, how can we describe the resulting partitions? The inverse would be to split parts that are divisible by three into three equal parts. When does this process stop? What identity is proved by this new bijection? (Difficulty rating: 1)
6. Generalize the idea of the previous exercise and show that for any integers k ≥ 2 and n ≥ 1,
p(n | no part divisible by k) = p(n | less than k copies of each part). (2.8)
(Difficulty rating: 1)



2.4 Euler pairs

The merging/splitting technique for proving Euler's identity is versatile. We can let it operate on other sets of partitions, say A and B, as long as the splitting process takes all partitions in A to partitions in B and the merging process takes all partitions in B to A.

For instance, let A be the set of partitions of n into parts of size one. The number of partitions in A is p(n | parts in {1}) = 1, since the only partition of n satisfying the condition is the sum 1 + 1 + ⋯ + 1 of n ones. The merging process will merge pairs of ones into twos, then merge pairs of twos into fours, then merge pairs of fours into eights, and so on until all parts are distinct. Consequently, the corresponding set B must be the set of partitions of n into distinct parts in {1, 2, 4, 8, ...} (powers of two). Now we must check that the splitting process will take every partition in B to A. Clearly any power of two (say 2k) is split into a pair of powers of two (2k-1 + 2k-1). Since the only power of two that is odd is 20 = 1, the process will go on until all remaining parts are ones.

Hence, we have a bijection that proves that for any n ≥ 1,

p(n | parts in {1}) = p(n | parts are distinct powers of two). (2.9)

And since the left-hand expression has the value one, we have proved that every positive integer has a unique partition into distinct powers of two. This is called the binary representation of integers. For example,

(2.10)

where (bkbk-1... b0)2 is the number written with binary digits (bits). This is the common mode for computers to store numbers in memory.



© Cambridge University Press
Read More Show Less

Table of Contents

1 Introduction 1
2 Euler and beyond 5
3 Ferrers graphs 14
4 The Rogers-Ramanujan identities 29
5 Generating functions 42
6 Formulas for partition functions 55
7 Gaussian polynomials 64
8 Durfee squares 75
9 Euler refined 88
10 Plane partitions 99
11 Growing Ferrers boards 106
12 Musings 121
A On the convergence of infinite series and products 126
Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)