E-Book Overview
This material is intended for a course that will combine a study of combinatorial structures with introductory recursive programming in Maple.
E-Book Content
East Side, West Side . . . an introduction to combinatorial families–with Maple programming Herbert S. Wilf University of Pennsylvania Philadelphia, PA, USA
May 28, 2002
1
2
Contents 1 Introduction 1.1 What this is about . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 4
2 About programming in Maple 2.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 8
3 Sets and subsets 3.1 What they are . . . . . . . . . . . . . . 3.2 How many there are . . . . . . . . . . 3.3 Probabilities and averages . . . . . . . 3.4 k-subsets . . . . . . . . . . . . . . . . . 3.5 East side, west side,. . . (I) . . . . . . . 3.6 Making lists and random choices of sets 3.7 Ranking sets and subsets . . . . . . . . 3.8 Unranking sets and subsets . . . . . . 3.9 Exercises . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . and subsets . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .
4 Permutations and their cycles 4.1 What permutations are . . . . . . . . . . . . . . . . . 4.2 What cycles are . . . . . . . . . . . . . . . . . . . . . 4.3 Counting permutations by cycles . . . . . . . . . . . 4.4 East side, west side ... (II) . . . . . . . . . . . . . . . 4.5 The generating function . . . . . . . . . . . . . . . . 4.6 The average number of cycles . . . . . . . . . . . . . 4.7 An application . . . . . . . . . . . . . . . . . . . . . 4.8 Making lists and random choices of permutations and 4.9 Ranking permutations by cycles . . . . . . . . . . . . 4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 4.11 Maple Programming Exercises . . . . . .