Integer Partitions

Cambridge University Press
0521841186 - Integer Partitions - by George E. Andrews and Kimmo Eriksson
Frontmatter/Prelims

Integer Partitions

The theory of integer partitions is a subject of enduring interest. A major research area in its own right, it has found numerous applications, and celebrated results such as the Rogers-Ramanujan identities make it a topic filled with the true romance of mathematics.

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.

The book has a short introduction followed by an initial chapter introducing Euler’s famous theorem on partitions with odd parts and partitions with distinct parts. This is followed by chapters titled Ferrers Graphs, The Rogers-Ramanujan Identities, Generating Functions, Formulas for Partition Functions, Gaussian Polynomials, Durfee Squares, Euler Refined, Plane Partitions, Growing Ferrers Boards, and Musings.

GEORGE E. ANDREWS is Evan Pugh Professor of Mathematics at the Pennsylvania State University. He is the author of many books in mathematics, including The Theory of Partitions (Cambridge University Press). He is a member of the American Academy of Arts and Sciences. In 2003, he was elected to the National Academy of Sciences (USA).

KIMMO ERIKSSON is a professor of applied mathematics at Mälardalen University in Sweden. He is the author of several matematical textbooks and popular articles in Swedish, as well as the opera Kurfursten with music by Jonas Sjöstrand. He is a member of the Västmanland Academy (Sweden).

To Joy and Charlotte

Integer Partitions

GEORGE E. ANDREWS
The Pennsylvania State University

KIMMO ERIKSSON
Mälardalen University

PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE
The Pitt Building, Trumpington Street, Cambridge, United Kingdom

CAMBRIDGE UNIVERSITY PRESS
The Edinburgh Building, Cambridge CB2 2RU, UK
40 West 20th Street, New York, NY 10011-4211, USA
477 Williamstown Road, Port Melbourne, VIC 3207, Australia
Ruiz de Alarcón 13, 28014 Madrid, Spain
Dock House, The Waterfront, Cape Town 8001, South Africa

http://www.cambridge.org

This book is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without
the written permission of Cambridge University Press.

First published 2004

Printed in the United States of America

Typeface Times Roman 10/13 pt. System LATEX 2_e [TB]

A catalog record for this book is available from the British Library.

Library of Congress Cataloging in Publication Data
Andrews, George E., 1938–
Integer partitions / George E. Andrews, Kimmo Eriksson.
p.   cm.
Includes bibliographical references and index.
ISBN 0-521-84118-6 – ISBN 0-521-60090-1 (pbk.)
1. Partitions (Mathematics)   I. Eriksson, Kimmo, 1967–   II. Title.
QA165.A55   2004
512.7′3 – dc22       2003069732

ISBN 0 521 84118 6 hardback
ISBN 0 521 60090 1 paperback

Contents

	Preface		ix

1	Introduction		1
2	Euler and beyond		5
	2.1	Set terminology	5
	2.2	Bijective proofs of partition identities	6
	2.3	A bijection for Euler’s identity	8
	2.4	Euler pairs	10
3	Ferrers graphs		14
	3.1	Ferrers graphs and Ferrers boards	15
	3.2	Conjugate partitions	16
	3.3	An upper bound on p(n)	19
	3.4	Bressoud’s beautiful bijection	23
	3.5	Euler’s pentagonal number theorem	24
4	The Rogers-Ramanujan identities		29
	4.1	A fundamental type of partition identity	29
	4.2	Discovering the first Rogers-Ramanujan identity	31
	4.3	Alder’s conjecture	33
	4.4	Schur’s theorem	35
	4.5	Looking for a bijective proof of the first Rogers-Ramanujan identity	39
	4.6	The impact of the Rogers-Ramanujan identities	41
5	Generating functions		42
	5.1	Generating functions as products	42
	5.2	Euler’s theorem	47
	5.3	Two variable-generating functions	48
	5.4	Euler’s pentagonal number theorem	49
	5.5	Congruences for p(n)	51
	5.6	Rogers-Ramanujan revisited	52
6	Formulas for partition functions		55
	6.1	Formula for p(n, 1) and p(n, 2)	55
	6.2	A formula for p(n, 3)	57
	6.3	A formula for p(n, 4)	58
	6.4	Lim_n →∞ p(n)^1/n = 1	61
7	Gaussian polynomials		64
	7.1	Properties of the binomial numbers	64
	7.2	Lattice paths and the q-binomial numbers	67
	7.3	The q-binomial theorem and the q-binomial series	69
	7.4	Gaussian polynomial identities	71
	7.5	Limiting values of Gaussian polynomials	74
8	Durfee squares		75
	8.1	Durfee squares and generating functions	75
	8.2	Frobenius symbols	78
	8.3	Jacobi’s triple product identity	79
	8.4	The Rogers-Ramanujan identities	81
	8.5	Successive Durfee squares	85
9	Euler refined		88
	9.1	Sylvester’s refinement of Euler	88
	9.2	Fine’s refinement	90
	9.3	Lecture hall partitions	92
10	Plane partitions		99
	10.1	Ferrers graphs and rhombus tilings	99
	10.2	MacMahon’s formulas	101
	10.3	The formula for π_r (h, j_i ; q)	103
11	Growing Ferrers boards		106
	11.1	Random partitions	106
	11.2	Posets of partitions	107
	11.3	The hook length formula	110
	11.4	Randomly growing Ferrers boards	113
	11.5	Domino tilings	115
	11.6	The arctic circle theorem	116
12	Musings		121
	12.1	What have we left out?	121
	12.2	Where can you go to undertake new explorations?	123
	12.3	Where can one study the history of partitions?	124
	12.4	Are there any unsolved problems left?	125

A	On the convergence of infinite series and products		126
B	References		129
C	Solutions and hints to selected exercises		132

	Index		139

Preface

This is a book about integer partitions. If you have never heard of this concept before, we guess you will nevertheless be quite familiar with what it means. For instance, in how many ways can 3 be partitioned into one or more positive integers? Well, we can leave 3 as one part; or we can take 2 as a part and the remaining 1 as another part; or we can have three parts of size 1. This extremely elementary piece of mathematics shows that the answer to the question is: “There are three integer partitions of 3.”

All existing literature on partition theory is written for professionals in mathematics. Now when you know what integer partitions are you probably agree with us that one should be able to study them without advanced knowledge of mathematics. This book is intended to fill this gap in the literature.

The study of partitions has fascinated a number of great mathematicians: Euler, Legendre, Ramanujan, Hardy, Rademacher, Sylvester, Selberg and Dyson to name a few. They have all contributed to the development of an advanced theory of these simple mathematical objects. In this book we start from scratch and lead the readers step by step from the really easy stuff to unsolved research problems. Our choice of topics was motivated by our desire to get to the meat of the subject directly. We wanted to move quickly to one of the most magnificent and surprising results of the entire subject, the Rogers-Ramanujan identitities. After that we introduce enough about generating functions to enable us to touch on the beginnings of the many fascinating aspects of the subject.

The intended audience is fairly broad. Obviously this should be the ideal textbook for a course on partitions for undergraduates. We have tried to keep the book to a modest length so that its topics would fit within one semester. Also there are often people with mathematical interests who do not have an advanced mathematics education. We hope these people will find this book tailor-made for them. Finally we believe that anyone with basic mathematics knowledge will find this book a solid introduction to integer partitions.

In order to make the text both easier and more stimulating to read, many arguments have been omitted and left as exercises at the end of sections. To many of these exercises you can find solutions and hints at the back of the book. The exercises vary in difficulty. We have tried to inform you of what to expect from the exercises by giving our estimate of the difficulty according to the following scale: 1 means straightforward, 2 means that you need a bit of problem solving skills, and 3 means that you are in for quite a challenge.

The idea for this book came up when the authors met at a conference in Philadelphia in 2000. Since then, all work has been carried out via mail and e-mail between Sweden and the United States. We are grateful to a number of people for assistance. Art Benjamin and Carl Yerger read the entire book, caught many mistakes, and made helpful suggestions. Kathy Wyland did some typing at Penn State. Brandt Kronholm, James Sellers and Ae Ja Yee read the galley proofs. Cambridge provided careful editorial advice, and Jim Propp made helpful and extensive comments on Chapter 11.

George E. Andrews
Kimmo Eriksson