Introduction to Combinatorial Analysis

John Riordan

• Publisher: Dover Publications
• Year: 2012
• Print ISBN: 9780486425368
• eBook ISBN: 9780486154404
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

This introduction to combinatorial analysis defines the subject as "the number of ways there are of doing some well-defined operation." Chapter 1 surveys that part of the theory of permutations and combinations that finds a place in books on elementary algebra, which leads to the extended treatment of generation functions in Chapter 2, where an important result is the introduction of a set of multivariable polynomials.
Chapter 3 contains an extended treatment of the principle of inclusion and exclusion which is indispensable to the enumeration of permutations with restricted position given in Chapters 7 and 8. Chapter 4 examines the enumeration of permutations in cyclic representation and Chapter 5 surveys the theory of distributions. Chapter 6 considers partitions, compositions, and the enumeration of trees and linear graphs.
Each chapter includes a lengthy problem section, intended to develop the text and to aid the reader. These problems assume a certain amount of mathematical maturity. Equations, theorems, sections, examples, and problems are numbered consecutively in each chapter and are referred to by these numbers in other chapters.

CHAPTER 1

Permutations and Combinations

1. INTRODUCTION

This chapter summarizes the simplest and most widely used material of the theory of combinations. Because it is so familiar, having been set forth for a generation in textbooks on elementary algebra, it is given here with a minimum of explanation and exemplification. The emphasis is on methods of reasoning which can be employed later and on the introduction of necessary concepts and working tools. Among the concepts is the generating function, the introduction of which leads to consideration of both permutations and combinations in great generality, a fact which seems insufficiently known.

Most of the proofs employ in one way or another either or both of the following rules.

Rule of Sum: If object A may be chosen in m ways, and B in n other ways, “either A or B” may be chosen in m + n ways.

Rule of Product: If object A may be chosen in m ways, and thereafter B in n ways, both “A and B” may be chosen in this order in mn ways.

These rules are in the nature of definitions (or tautologies) and need to be understood rather than proved. Notice that, in the first, the choices of A and B are mutually exclusive; that is, it is impossible to choose both (in the same way). The rule of product is used most often in cases where the order of choice is immaterial, that is, where the choices are independent, but the possibility of dependence should not be ignored.

The basic definitions of permutations and combinations are as follows:

Definition. An r-permutation of n things is an ordered selection or arrangement of r of them.

Definition. An r-combination of n things is a selection of r of them without regard to order.

A few points about these should be noted. First, in either case, nothing is said of the features of the n things; they may be all of one kind, some of one kind, others of other kinds, or all unlike. Though in the simpler parts of the theory, they are supposed all unlike, the general case is that of k kinds, with n_j things of the jth kind and n = n₁ + n₂ + · · · + n_k. The set of numbers (n_l, n₂, · · · , n_k) is called the specification of the things. Next, in the definition of permutations, the meaning of ordered is that two selections are regarded as different if the order of selection is different even when the same things are sel...

Table of contents

• Cover
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• 1 Permutations and Combinations
• 2 Generating Functions
• 3 The Principle of Inclusion and Exclusion
• 4 The Cycles of Permutations
• 5 Distributions: Occupancy
• 6 Partitions, Compositions, Trees, and Networks
• 7 Permutations with Restricted Position I
• 8 Permutations with Restricted Position II
• Index