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

1、Chapter 1 What is Combinatorics?,What is combinatorics?,Almost everyone has delt with the problems of combinatorics. The following are some examples: The number of games that n terms would play. Construct magic squares.,The ideas and techniques of combinatorics are widely used in: Physical science.

2、Biological science. Information theory. So many mathematical disciplines.,Two general types of problems of Combinatorics: Existence of the arrangement; Enumeration or classification of the arrangement. Two other problems in conjunction with the above: Study of the known arrangement; Construction of

3、an optimal arrangement.,The typical form of the combinatorial problem: Is it possible to arrange ? Does there exist a ? In how many ways can ? Count the number of ?,Example 1: Perfect cover of chessboard A chessboard has 64 squares in 8 rows and 8 columns. A domino has 2 adjacent squares. Is it poss

4、ible to arrange 32 dominoes to cover every square of chessboard (of course no 2 dominoes overlap)? Such an arrangement is called a perfect cover.,The number of perfect covers is 12,988,816= , which was found by Fischer in 1961.,Some generalizations: 8-by-8 to m-by-n. The perfect cover need not exist

5、 now, such as m=n=3. It is easy to know that there is a perfect cover if and only if at least one of m and n is even,II. Pruned chessboard: Cut out two diagonally opposite squares. There is no perfect cover. We can prove it by assigning them two colors: 31BW 32B+30W Perfect cover exists implies B=W.

6、 But the inverse is false. for example:,III. b-omino b-omino is b squares joined side by side consecutively. If b|m or b|n, then m-by-n board has perfect cover, and vice versa. The proof is as follows: It is obvious if b is prime. If b is not prime and b1. Then write,Suppose r s. Then we show r=0.,U

7、sing 10-by-11 as an example.,Consider the down-right r-by-s part. We have rs=rb. This means r=0.,Example 2: Cutting a cube Consider a block of wood in the shape of a cube, 3 feet on an edge. We can cut it into 27 smaller cubes, 1 foot on an edge. Of course 6 cuts can do it. The question is: What is

8、the smallest number of cuts in which this can be accomplished? The answer is 6. How about 4 feet on an edge?,The combination of example 1and 2. Consider a 4-by-4 chessboard which is perfect covered by 8 dominoes. Show that it is always possible to cut the board into two nonempty horizontal pieces or

9、 vertical pieces without cutting any of the dominoes. All the numbers of dominoes which are cut by the horizontal line or vertical line are even. So if the above conclusion is false, then the total number of dominoes which are cut by all lines is no less than 2+2+2+2+2+2=12. A contradiction!,Example

10、 3: Magic square,It is also easy to know that there is no magic square of order 2.,It is obvious that the sum is,Put 1 to into an n-by-n form such that every row sum, every column sum and every diagonal sum are all equal. Such form is called magic square of order n.,The method of consisting a magic

11、square of odd order is as follows(found by de la Loubere in 17th century): Put 1 in the middle of the top row. The successive integers are then placed along the diagonal line which slopes upward and to the right with the following modification: When the top row reached, the next integer is put in th

12、e bottom row as if it comes immediately above the top row. When the right-hand column reached, the next integer is put in the left-hand column as if it comes immediately succeeded the right-hand column. When a square is reached which has already been filled, the next integer is put in the square imm

13、ediately below the last square which was filled.,The magic square can be easily generalized to magic cube. The magic sum of magic cube of order n is,Then :,All these gives e=14. But there are so many planes. Contradiction!,Example 4: The four-color problem Consider a map on a plane where the countri

14、es are connected regions. In order to distinguish all the countries quickly, we color them with different colors if two countries are neighbors. It is not too difficult to show that 5 colors can do it. The question is: What is the smallest number of colors can do this?(First posed by Francis Guthrie

15、 in about 1850 when he was a graduate student.) 3 colors are not enough by the following graph:,In 1976, Appel and Haken announced that they have proven that the smallest number is 4 by computer which spend 1200 hours. It was simplified by N. Roberson, D.P.Sanders, P.D. Seymour, and R. Thomas. But i

16、t still requires very substantial computer verification.,Example 5: The problem of 36 officers Given 36 officers with 6 ranks and from 6 regiments, can they be arranged in a 6-by-6 form so that in each row and column there is one officer of each rank and one officer from each regiment?(posed by Swis

17、s mathematician L.Euler in 18th century.) Notice that every officer can be represent as a pair of integers (i,j). This problem can be translated into: Can the 36 ordered pairs (i,j) (i,j=1,2,6) be arranged in a 6-by-6 array so that in each row and each column all integers from 1 to 6 appear in the f

18、irst position and also appear in the second position.,If an n-by-n form consists of integers from 1 to n in each row and each column, and every integer appears only once, then we call the form Latin square of order n.,The array called the juxtaposed array of array and array .,It is easy to see that

19、there is no orthogonal Latin squares of order 2. Euler gives a method of constructing orthogonal Latin squares of order n when n is odd or divisible by 4. He conjectured that there are no orthogonal Latin squares of order n when n has the form 4k+2 with nonnegative integers k. In 1901, Tarry showed

20、that the Euler conjecture is true when k=1, that is n=6. This means that the answer to the problem of 36 officers is no. Around 1960, three mathematician-statistician Bose, Parker, and Shrikhande proved that the Euler conjecture was false when n6 by giving the construction of orthogonal Latin square

21、s of order n.,Example 6: Shortest-Route Problem Consider a system of streets and intersections. A person want to go from intersection A to intersection B. Of course he or she wishes that the distance is as short as possible. This is about the combination of Graph and Network. We will discuss it late

22、r.,Example 7: The Game of Nim The easiest case was posed in China: Given A heap of chessmen, two players take some chessmen, from 1 to 5, alternatively. The winner is the player who take the last chessman. Try to find the winning strategy. If the number of chessmen is divisible by 6, the second play

23、er will win, or else, the first player will win. The winning strategy is that any player does his or her best to guarantee that the number of remaining chessmen is divisible by 6. If so, the other player take n chessmen, he or she take 6-n chessmen.,A more difficult problem than that is the followin

24、g: Given heaps of coins which contain coins, respectively. Two players take coins alternatively. One can take any amount of coin and from any heap but from only one heap. The winner is also the player who take the last coin.,The variables in the above problem is . If k=1, then player I can win the g

25、ame since he or she can take all the coins.,The most complex case can be solved by base 2 numeral. Lets first review how to represent an integer in base 2 numeral by an example.,When k=2, player I will win if . Player II will win otherwise.,That is,and the base 2 numeral for 57 is 111001,The ith bit

26、 of a base 2 numeral is the digit in the ith position, the coefficient of,We define the game is balanced if and only if every sum of the same bit is even, that is, is even for every i from 0 to s. Otherwise, the game is unbalanced.,We can write every into base 2 numeral as following if we allow the digits to be 0s:,Conclusion: Player I can win in unbalanced Nim games, and Player II can win in balanced Nim games. To see this,one can only show the following two items: If the game is balanced, then it must be unbalanced after the taking of player I; If the game is