离散数学引论

离散数学引论"

作者:影印
ISBN:9787302214823
定价:¥34
字数:千字
页数:
出版时间:2009.11.01
开本:
版次:1-1
装帧:
出版社:清华大学出版社
简介

本书以简洁和通俗的形式介绍组合数学的一些本质性内容:图论的重要问题,计数方法和试验设计,其中图论约占一半篇幅。书中有大量习题和例题,习题附有部分解答和提示,适于自学。本书可用作数学、计算机科学、信息科学专业大学本科生的组合数学教材,可在大学一年级讲授。

前言

  Preface

This addition to the SUMS series of textbooks is an introduction to various as-

pects of discrete mathematics. It is intended as a textbook which could be used

at undergraduate level, probably in the second year of an English undergradu-

ate mathematics course. Some textbooks on discrete mathematics are written

primarily for computing science students, but the present book is intended for

students following a mathematics course. The place of discrete mathematics in

the undergraduate curriculum is now fairly well established, and it is certain

that its place in the curriculum will be maintained in the third millennium.

  Discrete mathematics has several aspects.  One fundamental part is

enumeration, the study of counting arrangements of various types. We might

count the number of ways of choosing six lottery numbers from 1, 2,... , 49, or

the number of spanning trees in a complete graph, or the number of ways of

arranging 16 teams into four groups of four. We develop methods of counting

which can deal with such problems.

  Next, graph theory can be used to model a variety of situations   road

systems, chemical molecules, timetables for examinations. We introduce the

basic types of graph and give some indication of what the important properties

are that a graph might possess.

  The third area of discrete mathematics to be discussed in this book is that of

configurations or arrangements. Latin squares are arrangements of symbols

in a particular way; such arrangements can be used to construct experimental

designs, magic squares and tournament designs. This leads us on to have a look

at block designs, which were discussed extensively by statisticians as well as

mathematicians due to their usefulness in the design of experiments. The book

closes with a brief introduction to the ideas behind error-correcting codes.

  The reader does not require a great deal of technical knowledge to be able

to cope with the contents of the book. A knowledge of the method of proof by

induction, an acquaintance with the elements of matrix theory and of arithmetic

modulo n, a familiarity with geometric series and a certain clarity of thought

                                               ix

x                                            Preface

should see the reader through. Often the main problem encountered by the

reader is not in the depth of the argument, but in looking at the problem in

the "right way". Facility in this comes of course with practice.

  Each chapter ends with a good number of examples. Hints and solutions to

most of these are given at the end of the book. The examples are a mixture of

fairly straightforward applications of the ideas of the chapter and more chal-

lenging problems which are of interest in themselves or are of use later on in

the book.

  My hope is that this text will provide the basis for a first course in discrete

mathematics. Obviously the choice of material for such a course is dependent

on the interests of the teacher, but there should be enough topics here to enable

an appropriate choice to be made. The text has been influenced in countless

ways by the many texts that have appeared over the years, but ultimately

it is determined by my own preferences, likes and dislikes, and by my own

experience of teaching discrete mathematics at different levels over many years,

from masterclasses for 14-year-olds to final year honours courses.

  I would like to thank the Springer staff for their encouragement to write this

book and for their help in its production. Thanks is also due to G ail Henry for

converting my manuscript into a ITEX file, and to Mark Thomson for reading

and commenting on many of the chapters.

                                                      University of Glasgow, June 2000

目录

Contents

1.  Counting and Binomial Coefficients.........................   1

     1.1  Basic Principles ..........................................  1

                                                                                                                     Imlmlffim  41lin

     1.2  Factorials................................................  2

     1.3  Selections ...............................................  3

     1.4  Binomial Coefficients and Pascal's Triangle ..................  6

     -1.5  Selections with- --Repetitions ................................-lO

     1.6  AUsefulMatrixInversion................................. 13

2.  Recurrence.................................................  19

     2.1  Some Examples .. .. . . . ... .. .. .. .. . . .. .. ..... . . . . .. .. .. . . . 19

     2.2  The Auxiliary Equation Method............................ 23

     2.3  Generating Fhnctions ..................................... 26

     2.4  Derangements............................................ 28

     2.5  Sorting Algorithms ....................................... 32

     2.6  Catalan Numbers......................................... 34

3.  Introduction to Graphs..................................... 43

     3.1  The Concept of a Graph .................................. 43

     3.2  Paths in Graphs.......................................... 46

     3.3  Trees ................................................... 47

     3.4  Spanning Trees........................................... 50

     3.5  Bipartite Graphs ......................................... 52

     3.t5  Planarity................................................ b4

     3.7  Polyhedra............................................... 60

4.  Travelling Round a Graph.................................. 60

     4 1  Hamiltonian Graphs                         69

     4.2  Planarity and Hamiltonian Graphs ......................... 71

     4.3  The Travelling Salesman Problem .......................... 74

                                                   xi

xii                                           Contents

     4.4  Gray Codes.............................................. 76

     -4.",5  Eulerian'Graphs.-..........................................--78

     4.t5  EulerianDigraphs........................................ 81

15.  Partitions and Colourings................................... 80

     15.1  Partitions of a Set ........................................ 80

     15.2  StirlingNumbers......................................... 91

     15.3  Counting Functions....................................... 04

     15.4  Vertex Colourings of Graphs ............................... 015

     15.5  Edge Colourings of Graphs ................................ 99

6   The Inclusion-Exclusion Principle                 107

                                                                                                                                                                                                                                                                                                                                  m                        

     t5.1  The Principle ............................................ 107

     15.2  Counting Surjections...................................... 112

     t5.3  Counting Labelled Trees................................... 113

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             Il

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             ,al

     6.4  Scrabble................................................. 114

     15.5  The MSnage Problem ..................................... 1115

7.  Latin Squares and Hall's Theorem.......................... 121

     -7.-1  Latin-Squares and - --Orthogonality ...........................-12-1

     7.2  Magic Squares ........................................... 125

     7.3  Systems of Distinct Representatives......................... 127

     7.4  From Latin Squares to Affine Planes ........................ 131

8   Schedules and 1-Factorisations                     137

                                                                                                                                                                                                                                                                  O                    4)                    S                              O                    G                             II,                                                  ii                                                                                

     8.1  The Circle Method ....................................... 137

     8.2  Bipartite Tournaments and 1-Factorisations of Kn,, .......... 142

     8.3  Tournaments from Orthogonal Latin Squares ................ 145

9.  Introduction to Designs..................................... 140

     9.1  Balanced Incomplete Block Designs......................... 14[}

     0.2  Resolvable Designs ....................................... 156

     0.3  Finite Projective Planes................................... 1150

     0.4  Hadamard Matrices and Designs ........................... 1t51

     0.15  Difference Methods ....................................... 165

     9.15  Hadamard Matrices and Codes............................. 1t5-7

Appendix....................................................... 170

Solutions ....................................................... 183

Further Reading                                   195

                                                                                                                                                                                                                                                                                                                                             II,                                                                                                                                                                                                                                                                                        

Bibliography.................................................... 197

Index                   ....................... 199

作者简介

编辑推荐

作者寄语

电子资料

www.luweidong.cn

下一个