Combinatorics deals with simple combinatorial problems, recurrence relations, and generating functions, particularly the binomial expansions. The book expounds on the general rules of combinatorics, the rule of sum, the rule of product, samples, permutations, combinations, and arrangements of subjects with various restrictions. The text also explains ordered or unordered partitions of numbers, geometric methods, random walk problems, and variants of the arithmetical triangle. One example of the use of combinatorics is the choice of the number 3 in the genetic code. Another example involves the choice of crew for a spaceship where it is necessary to consider the psychological conditions of the applicants for space travel. The text also investigates the sieve of Erastothenes whose problem concerns finding all the primes in the sequence of natural numbers from 1 to N. The book also tackles the application of power series to proof of identities, the binomial series expansion, decomposition into elementary fractions, and nonlinear recurrence relation. The book can be highly educational and interesting to students or academicians involved in mathematics, algebra, and statistics.
Inhalt
Foreword
Preface to the Russian Edition
I. General Rules of Combinatorics
Superstitious Cyclists
Samples with Repetitions
Systems of Numeration
Combination Lock
The Morse Code
Signaling at Sea
Electronic Computers
Genetic Code
General Rules of Combinatorics
A Domino Problem
Crew of a Spaceship
A Checkers Problem
How Many People Do Not Know a Foreign Language?
The Principle of Inclusion and Exclusion
Find the Error!
The Sieve of Erastothenes
II. Samples, Permutations, and Combinations
Soccer Tournament
Samples without Repetitions
Learned Society
Permutations
A Rook Problem
Linguistic Problems
Dancing in a Circle
Permutations with Repetitions
Anagrams
Combinations
The Genoa Lottery
Buying Pastry
Combinations with Repetitions
The Soccer Tournament Revisited
Properties of Combinations
Special Case of the Inclusion and Exclusion Formula
Alternating Sums of Combinations
III. Combinatorial Problems with Restrictions
Lions and Tigers
Construction of a Staircase
A Bookshelf
Knights of the Round Table
A Girl Has a Date
A Telepathic Séance
Derangements
Subfactorials
Caravan in the Desert
On the Merry-Go-Round
Queue at the Box Office
Problem of Two Rows
Additional Properties of Combinations
IV. Distributions and Partitions
A Domino Game
Putting Things in Boxes
A Bouquet
The Number of Divisors
Picking Apples
Picking Mushrooms
Sending Photographs
Flags on Masts
Count of All Signals
Various Statistics
Partitions of Numbers
Mailing of Printed Matter
The General Postage Problem
Combinatorial Problems in Information Theory
Problem of the University Applicant
Paying for a Purchase
Purchase of Candy
Getting Change
(Unordered) Partitions of an Integer
Use of Graphs
Dual Graphs
Euler's Formula
V. Combinatorics on a Chessboard
Walking in a Town
The Arithmetical Square
Figurate Numbers
Arithmetical Triangle
The Extended Arithmetical Triangle
Chess King
The Generalized Arithmetical Triangle
Generalized Arithmetical Triangles and Numbers to the Base m
Some Properties of the Numbers Cm(k, n)
Checker in a Corner
The Arithmetical Pentagon
Geometric Proofs of Properties of Combinations
Random Walk
Brownian Motion
In the Realm of the Tsarina of Shemakhan
An Absorbing Wall
Roaming on an Infinite Plane
The General Rook Problem
Symmetric Arrangements
Two Knights
VI. Recurrence Relations
Fibonacci Numbers
Another Method of Proof
Successive Partitions
Multiplication and Division of Numbers
Polygon Problems
The Head Steward Faces a Difficulty
Lucky Bus Ticket Numbers
Recurrent Tables
Another Solution of the Problem of the Chief Steward
Solution of Recurrence Relations
Linear Recurrence Relations with Constant Coefficients
The Case of Equal Roots of the Characteristic Equation
Application of the Theory of Recurrence Relations to Information Theory
Third Solution of the Problem of the Chief Steward
VII. Combinatorics and Series
Division of Polynomials
Algebraic Fractions and Power Series
Operations on Power Series
Application of Power Series to Proofs of Identities
Generating Functions
The Binomial Expansion
The Multinomial Expansion
The Binomial Series Expansion
Computation of Square Roots
Generating Functions and Recurrence Relations
Decomposition into Elementary Fractions (Partial Fraction Decomposition)
On a Certain Nonlinear Recurrence Relation
Generating Functions and Partitions of Numbers
Summary of Results on Combinatorial Distributions
VIII. Problems in Combinatorics
Answers and Hints
Index