組合數(shù)學(xué)

前言

　　I have made some substantial changes in this new edition of Introductory Combinatorics， and they are summarized as follows:　　In Chapter 1, a new section （Section 1.6） on mutually overlapping circles has been added to illustrate some of the counting techniques in later chapters. Previously the content of this section occured in Chapter 7.　　The old section on cutting a cube in Chapter 1 has been deleted, but the content appears as an exercise.　　Chapter 2 in the previous edition （The Pigeonhole Principle） has become Chapter 3. Chapter 3 in the previous edition, on permutations and combinations, is now Chapter 2. Pascals formula, which in the previous edition first appeared in Chapter 5, is now in Chapter 2. In addition, we have de-emphasized the use of the term combination as it applies to a set, using the essentially equivalent term of subset for clarity. However, in the case of multisets, we continue to use combination instead of, to our mind, the more cumbersome term submultiset.　　Chapter 2 now contains a short section （Section 3.6） on finite probability.　　Chapter 3 now contains a proof of Ramseys theorem in the case of pairs.　　Some of the biggest changes occur in Chapter 7, in which generating functions and exponential generating functions have been moved to earlier in the chapter （Sections 7.2 and 7.3） and have become more central.　　The section on partition numbers （Section 8.3） has been expanded.　　Chapter 9 in the previous edition, on matchings in bipartite graphs, has undergone a major change. It is now an interlude chapter （Chapter 9） on systems of distinct representatives （SDRs）——the marriage and stable marriage problemsand the discussion on bipartite graphs has been removed.　　As a result of the change in Chapter 9, in the introductory chapter on graph theory （Chapter 11）, there is no longer the assumption that bipartite graphs have been discussed previously.

內(nèi)容概要

本書是系統(tǒng)闡述組合數(shù)學(xué)基礎(chǔ)、理論、方法和實例的優(yōu)秀教材，出版30多年來多次改版，被MIT、哥倫比亞大學(xué)、UIUC、威斯康星大學(xué)等眾多國外高校采用，對國內(nèi)外組合數(shù)學(xué)教學(xué)產(chǎn)生了較大影響，也是相關(guān)學(xué)科的主要參考文獻之一。    本書側(cè)重于組合數(shù)學(xué)的概念和思想。包括鴿巢原理、計數(shù)技術(shù)、排列組合、P61ya計數(shù)法、二項式系數(shù)、容斥原理、生成函數(shù)和遞推關(guān)系以及組合結(jié)構(gòu)（匹配、實驗設(shè)計、圖）等。深入淺出地表達了作者對該領(lǐng)域全面和深刻的理解。除包含第4版中的內(nèi)容外，本版又進行了更新，增加了有限概率、匹配數(shù)等內(nèi)容。此外，各章均包含大量練習(xí)題，并在書末給出了參考答案與提示。

作者簡介

Richard A．Brualdi美國威斯康星大學(xué)麥迪遜分校數(shù)學(xué)系教授（現(xiàn)已退休），曾任該系主任多年。他的研究方向包括組合數(shù)學(xué)、圖論、線性代數(shù)和矩陣理論．編碼理論等。Brualdi教授的學(xué)術(shù)活動非常豐富，擔(dān)任過多種學(xué)術(shù)期刊的主編。2000年由于“在組合數(shù)學(xué)研究中所做出的杰出終身成就

書籍目錄

Preface1  What 'Is Combinatorics?  1.1   Example: Perfect Covers of Chessboards    1.2   Example: Magic Squares  1.3   Example: The Four-Color Problem  1.4   Example: The Problem of the 36 OfFicers   1.5   ,Example: Shortest-Route Problem  1.6   Example: Mutually Overlapping Circles    1.7   Example: The Game of Nim  1.8   Exercises2  Permutations and Combinations  2.1   Four Basic Counting Principles  2.2   Permutations of Sets  2.3   Combinations (Subsets) of Sets  2.4   Permutations of Multisets  2.5   Combinations of Multisets  2.6   Finite Probability  2.7   Exercises3 The Pigeonhole Principle  3.1   Pigeonhole Principle: Simple Form  3.2   Pigeonhole Principle: Strong Form  3.3   A Theorem of Ramsey  3.4   Exercises4  Generating Permutations and Combinations  4.1   Generating Permutations  4.2   Inversions in Permutations  4.3   Generating Combinations  4.4   Generating r-Subsets  4.5   Partial Orders and Equivalence Relations  4.6   Exercises5  The Binomial Coefficients  5.1  Pascal's Triangle  5.2   The Binomial Theorem  5.3  Unimodality of Binomial Coefficients  5.4  The Multinomial Theorem  5.5   Newton's Binomial Theorem  5.6   More on Partially Ordered Sets  5.7  Exercises6  The Inclusion-Exclusion Principle and Applications  6.1   The Inclusion-Exclusion Principle  6.2  Combinations with Repetition  6.3   Derangements  6.4   Permutations with Forbidden Positions  6.5   Another Forbidden Position Problem  6.6   M6bius Inversion  6.7   Exercises7  Recurrence Relations and Generating Functions  7.1   Some Number Sequences  7.2  Generating Functions  7.3   Exponential Generating Functions  7.4   Solving Linear Homogeneous Recurrence Relations ..  7.5   Nonhomogeneous Recurrence Relations  7.6  A Geometry Example  7.7   Exercises8  Special Counting Sequences  8.1   Catalan Numbers  8.2   Difference Sequences and Stirling Numbers  8.3   Partition Numbers  8.4   A Geometric Problem  8.5   Lattice Paths and Schr6der Numbers  8.6   Exercises9  Systems of Distinct Representatives10  Combinatorial Designs11  Introduction to Graph Theory12  More ONgraph Theory13  Digraphs and Networks14 Polya CountingAnswers and Hints to ExercisesBibliographyIndex

章節(jié)摘錄

　　Chapter 3　　The Pigeonhole Principle　　We consider in this chapter an important， but elementary, combinatorial principle that can be used to solve a variety of interesting problems, often with surprising conclusions. This principle is known under a variety of names, the most common of which are the pigeonhole principle, the Dirichlet drawer principle, and the shoebox principle.1 Formulated as a principle about pigeonholes, it says roughly that if a lot of pigeons fly into not too many pigeonholes, then at least one pigeonhole will be occupied by two or more pigeons. A more precise statement is given below.　　3.1 Pigeonhole Principle: Simple FormThe simplest form of the pigeonhole principle is tile following fairly obvious assertion.Theorem 3.1.1 If n+1 objects are distributed into n boxes, then at least one box contains two or more of the objects.　　Proof. The proof is by contradiction. If each of the n boxes contains at most one of the objects, then the total number of objects is at most 1 + 1 + ... +1（n ls） = n.Since we distribute n + 1 objects, some box contains at least two of the objects.　　Notice that neither the pigeonhole principle nor its proof gives any help in finding a box that contains two or more of the objects. They simply assert that if we examine each of the boxes, we will come upon a box that contains more than one object. The pigeonhole principle merely guarantees the existence of such a box. Thus, whenever the pigeonhole principle is applied to prove the existence of an arrangement or some phenomenon, it will give no indication of how to construct the arrangement or find an instance of the phenomenon other than to examine all possibilities.

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    組合數(shù)學(xué) PDF格式下載

---