Vilenkin Combinatorial Mathematics | N. Vilenkin

In the present book, the aim has been to set forth a variety of combinatorial problems in popular form and understandable language. At the same time, an attempt is made to present some rather involved combinatorial problems and to give the reader an idea of the methods of recurrence relations and generating functions.  The first chapter is devoted to the general rules of combinatorics, the rules of sum and product. In the second chapter we investigate permutations and combinations. This traditionally grade-school material is accompanied by an analysis of some amusing examples. In the third chapter, a study is made of combinatorial problems in which certain restrictions are imposed on the combinations. Chapter IV considers problems involving partitions of numbers into integers and- contains a description of certain geometrical methods in combinatorics. Chapter V is devoted to random-walk problems and to a variety of modifications of the arithmetic triangle. Chapter VI takes up recurrence relations, and Chapter VII discusses generating functions and, in particular, the binomial formula. The last section of the book is devoted to combinatorial problems of which there are over 400.  This material has been taken from a variety of sources, including Whitworth's Choice and Chance (London, 1901), John Riordan's An Introduction to Combinatorial Analysis (New York, 1958), an interesting book by A. M. Yaglom and I. M. Yaglom entitled Nonelementary Problems in an Elementary Exposition (Moscow, 1954), and various collections of problems given at mathematical Olympiads in the USSR.

This book was translated from the Russian by George Yankovsky. The   book was published by first Mir Publishers in 1972.

Preface
CHAPTER I.
THE GENERAL RULES OF COMBINATORICS

Superstitious cyclists 9
Permutations with repetitions 9
Number systems 10
Secret lock 11
Morse code 11
Wigwag code 11
Electronic digital computer 12
Genetic code 13
General rules of combinatorics 13
Domino problem 15
The crew of a spaceship 15
Checkerboard problems 16
How many people don't know foreign languages? 17
The principle of inclusion and exclusion 18
Where's the mistake? 20
The sieve of Eratosthenes 20

CHAPTER II. PERMUTATIONS AND COMBINATIONS

Football championship 22
Permutations without repetitions 22
A science club 22
Permutations of n elements 23
The pr oblem of the rooks 23
Linguistic problems 24
Round dance 25
Permutations with repetitions 25
Anagrams 26
Combinations 27
Genoese lottery 29
Buying cakes 30
Combinations with repetitions 31
The football championship again 32
Properties of combinations 33
A particular case of the principle of inclusion and exclusion 37
Alternating sums of combinations 37

CHAPTER III. COMBINATORIAL PROBLEMS WITH RESTRICTIONS
Lions and tigers 39
Building a stairway 39
A bookshelf problem 40
61 61 61  63 64 65 65 67 67 70  71 72  74

King Arthur's Round Table  40
She's got a date  41
A session in telepathy 42
General problem of derangements 44
Subfactorials 45
Caravan in the desert 46
Merry-go-round 47
Standing in line at a ticket office 48
The problem of the two ranks 51
New properties of combinations 51

CHAPTER IV.
THE COMBINATORICS OF PARTITIONS

Dominoes 54
Placing objects into cells 55
A bouquet of flowers 55
The number-of-divisors problem 56
Picking apples 56
Hunting mushrooms 57
Mailing photographs 57
Flags on masts 58
Total number of signals 59
Particle statistics 59
Partitions of integers 59
Mailing packages 60
General problem of postage stamps
Combinatorial problems of information theory
Entrance-exams problem
Paying money
Buying candy
Getting change
Partitioning integers
Arrays of dots
Dual arrays
Euler's formula

CHAPTER V. COMBINATORICS AND CHESS

Wandering about town
The arithmetic square
Figurate numbers
The arithmetic triangle
The extended arithmetic triangle
The chess king
The generalized arithmetic triangle 74
Generalized arithmetic triangles and base-m number system 75
Some properties of the numbers C m (k, n) 75
A checker in the corner 77
The arithmetic pentagon 78
Geometric proof of properties of combinations 79
Random walks 80
Brownian motion 81
The queen' s realm 82
Absorbing barriers 83
Random walks on an infinite plane 84
The general problem of the rocks 84
Symmetric arrangements 85
Two knights 87 89 91 91 92 93 94 96 97

CHAPTER VI. RECURRENCE RELATIONS

Fibonacci numbers
An alternative proof
The process of successive partitions
Multiplying and dividing numbers
Problems involving polygons
Difficulties of a majordomo
Lucky trolleybus tickets
Recurrence tables
Alternative solution of the majordomo problem
Solution of recurrence relations
Linear recurrence relations with constant coefficients
98
99
100
The case of equal roots of a characteristic equation 102
Application of the theory of recurrence relations to problems of
transmitting information 103
A third solution to the majordomo problem 103

CHAPTER VII. COMBINATORICS AND SERIES

Dividing polynomials 104
Algebraic fractions and power series 104
Operations on power series 107
Using power series to prove identities 108
Generating functions 109
Newton's binomial theorem 109
The multinomial theorem 111
Newton's series 112
Extracting square roots 114
Generating functions and recurrence relations 116
Decomposition into partial fractions 116
On a single nonlinear recurrence relation 118
Generating functions and partitions of integers 119
Summary of the combinatorics of partitions 122
Combinatorial Problems 123
Solutions and Answers 152
Index 205