Essentials in Combinatorics

What is essential in Combinatorics. R. Reytor. Isbn. 9789591607430? Index. Page Foreword ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 3 An introduction necessary ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4 A little history ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6 Chapter 1. General rules of combinatorics ... ... ... ... ... ... ... ... ... ... ... ... 9 1.1 .- Principle Additive ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 10 1.2 Principle Multiplicative ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 12 1.3 .- Exercises ... ... ... ... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... 15 Chapter II .- Variations and permutations ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 18 2.1 Platform variations without repetition ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .22 Training and number of permutations without repetition ... ... ... ... ... ... ... ... ... 23 2.1 Permutations without repetition ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 28 2.3 Circular Permutations ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 34 2.4 Permutations with repetition ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 37 2.5 Training and number of permutations with repetition ... ... ... ... ... ... ... .. 38 2.6 Variations with repetition ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 40 2.6 Exercises Chapter II ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 49 Chapter III. Combinations ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 56 1.3 Training and number of combinations without repetition ... ... ... ... ... ... ... 57 3.2 Combinations with Repetition ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 61 3.3 Relationship between combinations with and without repetition ... ... ... ... ... ... .. 63 3.4 Repeated exercise in Chapter III ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 64 Solutions and Answers ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 68 Preface. The development of combinatorial thinking is hard work and patience in this sense plays a big role in the system of pulses as a spring has to teach combinatorics. On many occasions, at the end of receiving a combinatorial topic, students do not have enough weapons to cope by themselves to solving problems, because the system of impulses in the appropriation of these concepts has been insufficient. The work of the teacher is important in this regard because they highlight the characteristics that defined concepts or facilitate appropriate description or characterization of these is ensuring success in the teaching process.

This text has been intended to highlight the treatment of combinatorial concepts in order to secure them properly giving attention to the process of identifying them, especially when we are dealing with problems. There are, of course, some trends algoritmizar try to work with sequences of combinatorial problems proposed indications for its solution, but, when these signs have a strong heuristic, further activate the learning process. Success in teaching combinatorics lies essentially in the drive system is used to set these concepts. This, undoubtedly, was the character that has tried to print this text. Had he succeeded, the goal will be fulfilled. The author. An introduction necessary. The combination is a section of mathematics that is useful for various representatives of various specialties. With the combinatorial problems are faced by biologists, physicists, chemists, mathematicians, linguists, engineers and many others. The study of combinatorics is the base that supports the analysis and solution of many problems of probability theory and its practical applications. This paper explains in simple language and combinatorial methods to solve the problems on this issue are proposed.

The exhibition has been made so that it can be understood by individuals with an average instruction. It may be useful to students and teachers of secondary education institutions, students from faculties of education in the fields of Mathematics, Physics, Chemistry, Biology and Elementary Education from the Higher Pedagogical Institute of Cuba especially in the first years of their respective specialties where they must face in the practical work with various combinatorial problems. This sets out the general rules of combinatorics, additive and multiplicative Principles, variations, permutations and combinations with and without repetition. these concepts are defined and described, emphasizing the characteristics that identify them in practical work, we deduce the formulas for combinatorial and are in the form of theorems with their proofs. Special emphasis is placed on the treatment should be given to the combinatorial defined concepts and their application to solving problems. It also includes many examples and exercises to help fix and systematized. Although this text has been respected mathematical rigor in the treatment of the concepts, the main objective of this is to analyze in some ways the combinatorial nature of the elements present in the problems and show some ways to solve them.

A little history. The part of mathematics that studies the problems of how many or which combinations (under certain conditions) can be performed with certain objects is called combinatorics. Historians place the emergence of combinatorics in the early sixteenth century, and was coined almost exclusively in the aristocracy of the time, for this society, generally spent his time in games of chance in which great fortunes won or lost. Playing dice or cards were won or lost large fortunes. Playing dice or cards were won or lost bright garments valuable thoroughbreds, etc.. At this time they were released several types of lotteries which occupied his days of knights and ladies of the time. It is understandable then, that in its inception, the problems is fundamentally about gambling, trying to figure out how many ways could be obtained favorable events in a number of tests. Thus, for example tried to find out how many ways you could draw a specific number by throwing several dice or how many ways you could draw two kings in a deck of 52 cards. These and other games were the driving force of combinatorics and probability, theory that runs parallel to it.

History records the name of Tartaglia as one of the pioneers in combinatorics. This famous Italian compiled a table showing all the ways you can fall "n? given, but did not anticipate that the same amount of points could be obtained in different ways (eg 4 +1 +3 = 4 +2 +2). The theoretical study of combinatorics is considered a fact from the year 1600 (XVII century) when the French Blaise Pascal and Fermat began collecting samples of experiments performed at the gaming tables and statistically recorded to study the laws and regularities in the which were governed. A particularly important role was played here the problem of the division of a wager Pascal proposed by a friend named Mere, passionate player by others. The problem was this: if a coin is tossed, the championship will continue until one player has won 6 games, but is interrupted when one won 5 and the other 4. How to split bet then? It was evident that the 5:4 ratio was not fair. Pascal solved the problem using some combinatorial methods and also proposed a solution method for the general case, when a player will remain "r" games to win and the other player will remain "s" matches.

A similar solution to this problem was given by Fermat. The subsequent development of combinatorics is linked to the names of famous mathematicians and Jacob Bernoulli, Leibniz and Euler. However, for these, also the fundamental role it were the applications to different types of games. Already in recent years, combinatorial entered a period of intense development related to the general growth of interest in the problems of discrete mathematics. Combinatorial methods are used to solve transportation problems, timetabling problems on, production plans and the mechanization of these and to determine the genetic characteristics in obtaining laboratory animal breeds. The combination is used for making and deciphering codes and to solve problems of information theory. And also, why not? To decide not too distant future the most effective way of preserving life on our planet. Chapter I. General rules of combinatorics. Combinatorial problems are classified according to the number of operations needed to solve to make: • Combinatorial Problems simple: those who are resolved by combining a single operation. • Problems combinatorial compounds are those which are resolved by using more than one operation combinations.

In the development of the following chapters exemplify these classifications. In discrete mathematics there are problems that are resolved by using certain formulas (depending on the combinatorial nature of the elements present in them) but most can be solved by two general principles: 1. The additive principle or rule of Sum. 2. The Multiplication Principle or Rule of the Product. The Multiplication Principle is generally associated with the procedure used in the early school years to find the number of items containing certain set, hence the majority of teachers recognize it as "Counting Method?. As is often the number of combinations or arrangements can be made with the elements of a set admits that appear in every election one and only one class of combinations, then the additive principle can be expressed as follows: '1.1.-Principle Additive "The total number of combinations that can be done with all kinds of items in a set is equal to the sum of the combinations of each of the classes?. Note: Class is defined as all subsets that form the elements of the set in question. Through the analysis and solution of the following example can be seen the application of this method.

Example 1: Mark has 3 shirts and 4 pants. Mark how many ways you can combine the shirts and pants? Denote the shirts with the letters a, b, c. pants and the x, y, z, u. if we set the distribution can be made between the shirts and pants can be seen that: Look at you that each sample consisting appears once and only once. The total number of samples are easily obtained by adding all combinations obtained by the above process: 1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 +1 = 12 12 times because the number of combinations each class is one. Example 2: In a study team there are 3 girls and 2 boys. How many different pairs can be formed to study? Similar to the above, we can form two sets of different nature: all the girls: Diana, Claudia, Susan and the children: Rafael, Alejandro. The selection of duets can be performed using a network diagram as follows: The lines connecting the circles is 10. Obviously the total number of possible samples is obtained by counting the lines formed. 1 +1 +1 +1 +1 +1 +1 +1 +1 +1 = 10 10 times Example 3: How many three-digit numbers must not repeat?

a) Start with 23. Previously analyzed the place of the units may be occupied in each sample by one and only one of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8.9. If we form each sample is obtained: 230, 231, 234, 235, 236, 237, 238, 239. As can be seen the number of combinations of each class is 1 so the total number of combinations of all classes is 8. The additive principle? provides information about the composition of all samples from an experiment? issue that is important, especially in the early grades of education for the contribution they make in the field of combinatorial development of thinking in schoolchildren. Obviously "their inconvenience is that its application is rational only in cases where the total number of samples that make up the experiment is not very high?. The above examples can be addressed by further analysis, in which you can get to know the total number of samples that make up an experiment without having to form each of the samples that comprise them. In this sense we state the following principle. 1.2 .- Multiplication Principle. "If any one thing can happen in m different ways and if it occurred after any of these ways, anything can happen in n ways, then the two things in that order, m can occur n ways?.

This principle states that if two things happen one after the other, the total number of ways that can occur both by multiplying the number of ways from the first by the number of ways in the second. Example 4: How many syllables of two letters, beginning with a consonant, in Spanish there? In this case the method of counting additive slows down the work by the number of samples that have the experiment. The first thing is choosing the first letter (a consonant) and the second, the choice of a vowel. And Spanish are 24 consonants and 5 vowels only, the second choice may occur of 5 ways. In total can be obtained from 24 × 5 = 120 syllables. The multiplicative principle can be extended to more than two things. Example 5: "The numbers 2, 3, 4 and 5 can be multiplied for each other in different orders. Write down all the possible ways of considering the 2 as the first facto?. In this case we have 3 different things. The first is to place the second factor of the product (considering the order from left to right), for which there are three possibilities, the second place the third factor, we can have a chance.

Depending on the multiplicative principle we can multiply the numbers of 3 × 2 × 1 = 6 different ways. Clearly, they can easily see that all samples obtained up this experiment. Sometimes both methods can be applied to solve certain problems. Example 6: How many numbers of two or three non-repeating numbers can be formed with the digits 1 to 4? Applying the Multiplication Principle, to determine all 2-digit numbers we do not repeat the approach: 4 × 3 = 12 2-digit numbers are not repeated. Similarly to determine the amount of 3-digit numbers do not get repeated (4 × 3) × 2 = 24 numbers. Then applying the additive principle gives: 12 +24 = 36 numbers in two or three figures are not repeated. The combinatorial stranded allows the application of analytical methods for the solution of problems in the following example shows one way in which a problem can be solved. Example 7: To make a trip from city A to city B can be used three buses and to go from city B to city C only 2. How many different ways you can travel from city A to city C?

The following diagram shows how you can make the trip. In this diagram each segment represents a journey between two cities mentioned in the problem. To make the full trip is necessary to select two segments. Can be clearly seen that there are many possibilities as there are segments between city A and C, ie 6th this result is easily reached using the Multiplication Principle. In practice it is necessary to use a diagram like this, but if it does, it helps to understand the problem, which in more complex cases is essential. This type of diagram is called a diagram? Tree branches because every point in the same way as does a tree. Exercises. 1. How many ways can you choose a vowel and a consonant of the word number? 2. At the top of a mountain roads lead 5. How many ways can upload and download a camper using these roads? What if the ascent and descent are carried on different paths? 3. How many ways can choose two dominoes, of the 28's in a game table, so that can be applied with each other?

4. At a meeting there are 18 people. All greet each other and no two people greet each other more than once. How many hands greetings given? 5. In a clothing store there are men's shirts in 4 different sizes and three different colors in each size. How many different types of shirts in the store? 6. Of copies of a text after Algebra 2 Geometry Trigonometry and 2 must choose a copy of each. How many ways there are to do? 7. How many different ways can write the letters A, B, C, D, one after another without repeating any? 8. How many two digit numbers can be formed with the numbers 1, 2, 3, 4, 5, 6, 7? How many of them have their two numbers equal? 9. How many three-digit numbers can be formed with the figures of the number 24 356? How many are even? 10. How many are three-digit numbers that are multiples of two? 11. How many 4-digit numbers are there? 12. How many 4-digit natural numbers exist that do not contain the number 7? 13. How many odd numbers are 3 digits and are less than 500? 14. How many natural numbers between 100 and 999 have their different figures?

15. How many of the first 1000 positive integers are all different numbers? 16. How many three-digit natural numbers are such that the sum of its digits is 5? What are they? 17. How many ways can be indicated on a chessboard two squares: one white and one black? 18. In a corporation employed 67 people. Of these, 47 are fluent in English, 35 French and 23 in both languages. How many people do not speak of the corporation or English or French? 19. From a group of 19 young people like mathematics, plastic arts 17, 11 history, 12 prefer math and fine arts, history and mathematics 7, 5 visual arts and history. 2 people like the three subjects and 5 none of them. How many young people are in the group? 20. to transmit information by telegraph using Morse code. In this code the letters, numerals and punctuation marks are represented by dots and dashes. For example, the letter t is represented by a dot (.) And L for three points and a line (.-.). Using up to two signs, how many letters can be encoded? 21. there are three types of envelopes without stamps and four types of stamps of the same value.

How many ways you can choose an envelope and a stamp to send a letter? 22. How many ways can you choose a vowel and a consonant in the word Martí? 23. How many ways can you choose a vowel and a consonant in the word Maceo? 24. On a shelf there are three copies of a text in Spanish, 7 and 6 math history. How many ways you can choose a copy? 25. A person has 8 copies of a book of arithmetic and the other has 9 books of algebra. How many ways you can choose a copy? Chapter II. Variations and permutations. Previously studied combinatorial principles used to solve most problems that arise in combinatorial theory, however, there are some special cases that occur frequently and for which it is possible to obtain simple formulas. But if it is true that these formulas expedite the calculation, it is necessary to establish a prior work of identifying combinatorial experiment present in the problem. In this sense we may include combinatorial problems into two groups: the problems dealing with variations and combinations that address. Establishing this division, we will study each concept separately, highlighting the characteristics of the term that defines the specific purpose of identifying them in solving problems.

Of the anterior division first study the variations. This set of variations, in turn divide into 2 subgroups: without repeating variations and variations with repetition. The strategy we use to identify randomized experiments represent it in the following scheme: • Strategy for the Identification of a random experiment. The logic of the proposed strategy is based on the existence of a combinatorial experiment of unknown nature. To identify those parts of the formation of some samples of the same (at most 3) and analyze their characteristics, focusing our attention in order. The analysis leads to decision making related to the type of random experiment: if the distinctive element in the analysis of samples is the order, the experiment deals with random variations, otherwise, is about combinations. Once the decision is analyzed if the samples were again supported by repetition and decide: is a variation with repetition or a combination with repetition. This decision marked the combinatorial experiment samples and allows us to identify. If the random experiment was made, because he was formed by several simple random experiments, we start again and repeat the cycle analysis. With this logic will be discussed the concepts of combinatorial analysis.

For its part, the solution of combinatorial problems has been one of the most difficult barriers to overcome for the students because they do not use an appropriate strategy for solving them. The strategy for solving the combinatorial problems expressed in the following scheme: General scheme for solving a combinatorial problem. The logic of the strategy is the first time the identification of random experiment to implement the Strategy for Identification. The second step is to select the path to calculate the number of samples that make up the experiment using any of the calculation procedures known in the combinatorial theory: use of diagrams, general principles or formulas. The third stage is the implementation of the selected route calculation, with which we know the number of samples that make up the experiment. Validation of the way of calculation applied to the solution of the problem is the fourth moment of the strategy. This step takes on characteristics peculiar to the problems of discrete mathematics because it is very difficult to check the solution in relation to the text of the problem, except in very simple cases. Validation should be performed using a route other than the one chosen to give the solution and compare the results.

On the above conditions, we will treat the random experiments and solving problems on Combinatorial Theory. II.I. - Variations without repetition. Definition. Variations are called without repetition of n objects taken pap (or variations of order p) all p possible orderings of n objects taken from the given objects where repetition is not supported. The characteristics that identify the signs of an experiment without repetition variations are: Two different samples: • Or in the order of its elements. • Or at least one item. • Items not repeated in the same sample. Example 1: Train all numbers from 2 different numbers with the digits 1,2, 3, 4. 12 21 31 41 13 23 32 42 14 24 34 43 As can be seen, it is easy to analyze the samples made using the standard features mentioned. Samples 12 and 21 are different, since the order of the items taken is essential (obviously the numbers 12 and 21 are different). If we select the samples 12 and 14 the difference is an element (2 and 4) and samples 12 and 43 differ in its entirety. It is essential to the mastery of these characteristics for subsequent application to the analysis of combinatorial problems.

• Training and number of permutations without repetition. Variations without repeating a certain number of given objects, for example, the numbers 1, 2, 3, 4, you can go in succession, ie, first appears variations where only one element (Monari variations), then the binary the tertiary, etc.. The method involves adding a certain order every variation of each of the numbers not listed. The variations are evidently Monari: 1, 2 3, 4. To form the binary variation is added to each Monari, the remaining numbers, we get: 12 21 31 41 13 23 32 42 14 24 34 43 They are now ternary, adding to each binary numbers that do not appear in them. Applying the Principle Multiplicative we have: there are 12 binary variations and each one can add 4-2 numbers, thus obtaining 12 × 2 = 24 ternary variations. 123 231 321 412 124 213 312 421 132 241 342 423 134 214 324 432 142 234 314 413 124 243 341 431 Similarly the analysis is performed for variations quaternary or fourth order. In variations without repeating the training process concludes when sample order (p, number of elements in the sample) matches the number of elements in the set (N). Following the procedure described above can be variations without repetition of n objects taken pa p.

Theorem: The number of permutations without repetition of "n" objects taken pap is: • V (N) = N (N-1) (N-2) ... (N-p +1) with n ≥ p, N p are natural numbers, N ≥ 1. Demonstration. (Complete induction on n) • For n = p = 1 we have V (1,1) = 1. • For N = p is: V (p, p) = p (p-1) (p-2) ... (p-(p +2)) (p-(p +1)) are obtained without repeating variations of p elements from pap, for which it holds for n = p. • Suppose that is true for n = k. V (k, p) = k (k-1) (k-2) ... (k - (p +2)) (k - (p +1)) • validity for n = k it follows the validity for n = k +1 V (K +1, p) = (k +1) K (k-1) (k-2) (k-3) ... (k - (p +2)) (k - (p +1)) The formula is composed of p factors arranged in descending order starting with n and terminated by p. The following example shows the process of solving a combinatorial problem. Example 2: How many different three-digit numbers can be formed with the digits making up the number 24756? In this problem we have as elements the digits 2, 4, 7, 5, 6, a total of 5 elements and 3 samples must be different elements, it is important to note the fact of non-repetition of the elements the samples.

Formed a few samples of the experiment. 247, 724.245. It is easy to observe compliance with the relevant characteristics to changes without repeating two samples differ: • Or in the order of its elements (247, 724) • Or at least one item. (247 and 245) • The elements are not repeated in the same sample. Found that the combinatorial element present in the problem without repeating variations undoubtedly we can easily determine the number of elements in the set (N = 5) and the number of elements with the samples (p = 3). Applying the formula for calculating and making them get V (5.3) = 5x4x3 = 60 three-digit numbers. To validate the result we can apply the Multiplication Principle: We can designate the hundreds place by the variable m, n and the dozens of units by p. The site can be occupied m 5 forms, n and p 4 ways 3 ways. The number of times that can occur in that order of things is: = 5x4x3 = 60 mxnxp Analysis of combinatorial problems is the key to determine the nature of this random experiment in it. Sometimes the difference between combinational elements is so subtle that it is not easy to determine whether the analysis is superficial.

Example 3: In a group of 8 people have to choose a president, vice president and secretary. How many ways can you do? They form groups of three people to whom to be designated responsibilities, no matter the order of choice of people and if the order in which they are appointed positions. We form three samples of the experiment. As the charges are not repeated and the designation of responsibilities differs in each sample formed, the experiment shows that variation is not repeated. N = 8 and p = 3 V (8.3) = 8x7x6 = 336. The validation and retrospective analysis of the problem we can make it similar to Example 2. If you change slightly the structure of the problem such as: In a group of 8 people have to choose a group of three to participate in an event. How many ways can you do? Formed a few samples of this experiment. First group: Paul, John, Jonah. Second group: John, Paul, John. Third group: Paul, Rachel, John. No matter what order to take the members of the groups, since if they have the same members, it is the same group is what happens with the first and second groups.

In the analysis of samples we can realize that they are different the first and third groups or the second and third.

















3!























1. 2. 3. 4.

5. 6. 7. 8. 9. 10. 11. 12. 13. 14.

16. 19. 20.

21. 22. 23. 24. 25. 26. 1.

3.