Combinatorial Methods
It is not a large overstatement to claim that mathematics has traditionally arisen from attempts to understand quite concrete events in the physical world. The accelerated sophistication of the mathematical community has perhaps obscured this fact, especi
- PDF / 8,688,580 Bytes
- 203 Pages / 504.567 x 720 pts Page_size
- 99 Downloads / 282 Views
J. K. Percus
Combinatorial Methods With 58 Illustrations
Springer-Verlag New York· Heidelberg· Berlin
1971
Jerome K. Percus New York University Courant Institute of Mathematics and Sciences New York, New York
All rights reserved. No part of this book may be translated or reproduced in any form without written permission from Springer-Verlag. ©1971 by Springer-Verlag New York Inc. Softcover reprint of the hardcover 1st edition 1971 Library of Congress Catalog Card Number 78-152001.
ISBN-13: 978-0-387-90027-8 001: 10.1007/978-1-4612-6404-0
e-ISBN-13: 978-1-4612-6404-0
PREFACE
It is not a large overstatement to claim that mathematics has traditionally arisen from attempts to understand quite concrete events in the physical world.
The
accelerated sophistication of the mathematical community has perhaps obscured this fact, especially during the present century, with the abstract becoming the hallmark of much of respectable mathematics.
As a result of the inaccessibility of such work,
practicing scientists have often been compelled to fashion their own mathematical tools, blissfully unaware of their prior existence in far too elegant and far too general form.
But the mathematical sophistication of scientists has grown rapidly
too, as has the scientific sophistication of many mathematicians, and the real world suitably defined - is once more serving its traditional role.
One of the fields
most enriched by this infusion has been that of combinatorics.
This book has been
written in a way as a tribute to those natural scientists whose breadth of vision has inparted a new vitality to a dormant giant. The present text arose out of a course in Combinatorial Methods given by the writer at the Courant Institute during 1967-68.
Its structure has been determined
by an attempt to reach an informed but heterogeneous group of students in mathematics, physics, and chemistry.
Its lucidity has been enhanced immeasurably by the need to
satisfy a very resolute critic, Professor Ora E. Percus, who is responsible for the original lecture notes as well as for their major modifications.
The writer would
like to thank Professor James steadman for the arduous task of proof-reading, establishing consistency of notation, and making a number of revisions to improve clarity.
J. K. Percus New York June 30, 1971
v
TABLE OF CONTENTS
PREFACE
v
CRAnER I.
A.
B.
COUNTING AND ENUMERATION ON A SET Introduction
1
1.
Set Generating Functions
1
2.
Numerical Generating Functions
3
Examples
4
Fibonacci Numbers
4
Counting with Restrictions -- Techniques
7
1.
Inclusion - Exclusion Principle
7
The Euler Function
8
Rencontres, Derangement or Montmort Problem
9
The Menage Problem 2.
C.
10
Permutations with Restricted Position. Master Theorem
The 12
Exercises
13
Example
18
Rencontre Problem
19
Menage Problem
21
3. Extension of the Master Theorem
27
Partitions, Compositions and Decompositions ••
31
1.
31
2.
3.
Permutation Counting as a Partition Problem a)
Counting with allowed transitions
Data Loading...
