°¡¹þ,Áé»úÒ»¶¯

°¡¹þ,Áé»úÒ»¶¯ ½ÚÑ¡

Chapter 1 Combinatorial aha£¡ ×éºÏ Puzzles about arrangements Combinatorial analysis£¬ or combinatorics is the study of how things can be arranged. In slightly less general terms£¬ combinatorial analysis embodies the study of the ways in which elements can be grouped into stes subject to various specified rules£¬ and the properties of those groupings. For example£¬ our first problem is about the ways in which differently colored balls can be grouped together. This problem asks the reader to find the smallest sets of colored balls that have certain properties the second problem concerns ways in which players can be grouped on a chart for an elimination tournament¡ªa problem with important counterparts in the computer sorting of data. Combinatorial analysis often asks for the total number of different ways that certain things can be combined according to certain certain rules. The ¡°enumeration problem¡±£¬ as this is called£¬ is introduced in the episode about the number of ways that Susan can walk to school. In this case£¬ the elements to be combined are the segments of a path along the edges of a matrix. Since geometrical figures are involved£¬ we are in area of ¡°combinatorial geometry¡±. Every branch of mathematics has its combinatorial aspects£¬ and you will find combinatorial problems in all the sections of this book. There is combinatorial arithmetic£¬ combinatorial topology£¬ combinatorial logic£¬ combinatorial set theory-even combinatorial linguistics£¬ as we shall see in the section on word play. Combinatorics is particularly important in probability theory where it is essential to enumerate all possible combinations of things before a probability formula can be found. There is a famous collection of probability problems called Choice and Chance. in the refers to the book¡¯s combinatorial aspect. ÿһÕ¿ªÍ·µÄÎÄ×ÖÒ»°ãÊÇÊ®·Ö¸ÅÀ¨µÄ£¬ÊÂÏÈ¿ÉÒÔ´Ö¿´Ò»±é£¬¶ÁÍêºóÔÙ×ÐϸÁì»á»á¸üÓÐÊÕ»ñ£¡×éºÏÎÊÌâÓÐÐí¶à£¬*»ù±¾µÄ¾ÍÊÇ¡°¼ÆÊý¡±£¬Ò²¾ÍÊÇÿÖÖģʽÓжàÉÙÖÖ£¿ÕâÎÊÌâ¿´À´¼òµ¥£¬Êµ¼ÊÉϲ¢²»¼òµ¥£¬ÌرðÊÇÒªÇø·Ö¿ª²»Í¬µÄÀàÐÍ£¬²»ÒªÖظ´¼ÆÊý£¬Ò²²»ÒªÂ©µôÌÖÊý£¬¡°ÍêÈ«ÐÔ¡±ÊÇÊ®·ÖÖØÒªµÄ¡£ Our very first problem concerns probability because it asks for an arrangement of colored balls that makes certain (that is have a probability equal to 1) a specified task. The text suggests how endless other probability questions arise from such simple questions as the number of ways objects can be put together. Enumerating Susan's paths to school provides a close link to Pascal's triangle and its use in solving elementary probability questions. The number of arrangements that solve a given combinatorial problem obviously can be none£¬ one£¬ any finite number£¬ or an infinite number. There is no way to combine two odd integers so that their sum is odd. There is only one way to combine two prime numbers so that their product is 21. There are just three ways to combine two positive integers their sum is 7. (They are the pairs of opposite faces on a die.) And there is an infinite number of combinations of two even numbers that have an even sum. Very often in combinatorial theory it is extremely difficult to find an ¡°impossibility proof¡± that no combination will meet what is demanded. For example£¬ it was not until recently that a proof was found that there is no way to combine the planar regions of a map so that the map requires five colors. This had been a famous unsolved problem in combinatorial topology. The impossibility proof required a computer program of great complexity. On the other hand£¬ many combinatorial problems that seem at first to be difficult to prove impossible can sometimes be proved easily if one has the right aha£¡insight. In the problem of ¡°The Troublesome Tiles¡±£¬ we see how a simple ¡°parity check¡± leads at once to a proof of combinatorial impossibility that would be hard to obtain in any other way. The second problem about the defective pills ties combinatorial thinking into the use of different base systems for arithmetic. We see how numbers themselves and the way in which there are represented in positional notation by numerals depend on combinatorial rules. Indeed£¬ all deductive reasoning£¬ whether in mathematics or pure logic£¬ deals with combinations of symbols in a ¡° string¡± £¬ according to the rules of a system that decides whether the string is a valid or invalid assertion. This is why Gottfried Leibniz£¬ the seventeenth-century father of combinatorics£¬ called the art of reasoning an ars combinatoria. A Sticky Gum Problem ÅÝÅÝÌÇÎÊÌâ ÕâÎÊÌâÊǺõÄÊýѧÓÎÏ·ÎÊÌ⣬Õâ±íÏÖÔÚËü¿ÉÒÔÍƹ㵽¸ü°ãµÄÇéÐΣº¢ÙÌǵÄÑÕÉ«¿ÉÒÔÊÇ2ÖÖ£¬3ÖÖ£¬ £¬nÖÖ¡£¢Úº¢×ÓÊý¿ÉÒÔÊÇ2ÈË£¬3ÈË£¬ £¬mÈË8¢ÛµÃÖÖÑÕÉ«ÌǸ÷Óв»Í¬µÄÊýÄ¿¡£ How Many Pennies? The second gum ball problem is an easy variation of the first one£¬ and is solved by the same insight. In this case the first three balls could be of different colors~red£¬ white and blue. This is the "worst" case in the sense that it is the longest sequence of drawings that fail to achieve the desired result. The fourth ball will necessarily match one of the three. Since it could be necessary to buy four balls to get a matching pair£¬ Mrs. Jones must be prepared to spend four