Solutions to problems in Introduction to Combinatorial Mathematics

✍ Scribed by Murray Edelberg, C. L. Liu

• Publisher: McGraw-Hill
• Year: 1968
• Tongue: English
• Leaves: 403
• Edition: 1
• Category: Library

✦ Table of Contents

Cover
Title page
Date-line
Preface
Contents
1 Permutations and Combinations
1-1 Introduction
1-2 The Rules of Sum and Product
1-3 Permutations
1-4 Combinations
1-5 Distributions of Distinct Objects
1-6 Distributions of Nondistinct Objects
1-7 Stirling's Formula
1-8 Summary and References
2 Generating Functions
2-1 Introduction
2-2 Generating Functions for Combinations
2-3 Enumerators for Permutations
2-4 Distributions of Distinct Objects into Nondistinct Cells
2-5 Partitions of Integers
2-6 The Ferrers Graph
2-7 Elementary Relations
2-8 Summary and References
3 Recurrence Relations
3-1 Introduction
3-2 Linear Recurrence Relations with Constant Coefficients
3-3 Solution by the Technique of Generating Functions
3-4 A Special Class of Nonlinear Difference Equations
3-5 Recurrence Relations with Two Indices
3-6 Summary and References
Appendix 3-1 Uniqueness of the Solution to a Difference Equation
4 The Principle of Inclusion and Exclusion
4-1 Introduction
4-2 The Principle of Inclusion and Exclusion
4-3 The General Formula
4-4 Derangements
4-5 Permutations with Restrictions on Relative Positions
4-6 The Rook Polynomials
4-7 Permutations with Forbidden Positions
4-8 Summary and References
5 Polya's Theory of Counting
5-1 Introduction
•5-2 Sets, Relations, and Groups
5-3 Equivalence Classes under a Permutation Group
5-4 Equivalence Classes of Functions
5-5 Weights and Inventories of Functions
5-6 Polya's Fundamental Theorem
5-7 Generalization of Polya's Theorem
5-8 Summary and References
6 Fundamental Concepts in the Theory of Graphs
6-1 Introduction
6-2 The Connectedness of a Graph
6-3 Euler Path
6-4 Hamiltonian Path
6-5 Summary and References
7 Trees, Circuits, and Cut-sets
7-1 Trees and Spanning Trees
7-2 Cut-sets
•7-3 Linear Vector Spaces
7-4 The Vector Spaces Associated with a Graph
7-5 The Bases of the Subspaces
7-6 Matrix Representation
7-7 Summary and References
Appendix 7-1 The Number of Vectors in the Bases of a Vector Space
8 Planar and Dual Graphs
8-1 Introduction
8-2 Euler's Formula
8-3 Kuratowski's Theorem
8-4 Dual Graphs
8-5 Summary and References
9 Domination, Independence, and Chromatic Numbers
9-1 Dominating Sets
9-2 Independent Sets
9-3 Chromatic Numbers
9-4 The Chromatic Polynomials
9-5 The Four-color Problem
9-6 Summary and References
10 Transport Networks
10-1 Introduction
10-2 Cuts
10-3 The Max-flow Min-cut Theorem
10-4 An Extension
10-5 Summary and References
11 Matching Theory
11-1 Introduction
11-2 Complete Matching
11-3 Maximal Matching
11-4 An Alternative Approach
11-5 Summary and References
12 Linear Programming
12-1 Introduction
12-2 Optimal Feasible Solutions
12-3 Slack Variables
12-4 The Simplex Method
12-5 The Tableau Format
12-6 Complications and Their Resolutions
*12-7 Duality
12-8 Summary and References
13 Dynamic Programming
13-1 Introduction
13-2 The Principle of Optimality
13-3 Functional Equations
13-4 Summary and References
14 Block Designs
14-1 Introduction
14-2 Complete Block Designs
14-3 Orthogonal Latin Squares
14-4 Balanced Incomplete Block Designs
14-5 Construction of Block Designs
14-6 Summary and References
Index