Combinatorics

5 Key excerpts on "Combinatorics"

• 

  eBook - ePub

  A First Step to Mathematical Olympiad Problems

  • Derek Holton(Author)
  • 2009(Publication Date)
  • WSPC

    (Publisher)

  I say it in public. That can only mean that “Combinatorics” is one of those secret words that can only be spoken in the inner mathematical holy of holies. (Wherever that is.) So it must be in a Mathematical dictionary somewhere. Surely it's on the web!

  Let's see then. “Combinatorics investigates the different possibilities for the arrangement of objects.” “Combinatorics is a branch of mathematics that studies discrete objects.”

  Well I'm not really sure that that helped any. So let me go to my own experience. Combinatorics is the mathematics of counting,…without counting. Er, Combinatorics is playing with sets of objects,…when you're not doing set theory. Er, well, er, Combinatorics is the mathematics of structure,…when you're not doing geometry or algebra or whatever that's not Combinatorics.

  I guess Combinatorics is hard to define. Possibly this is because Combinatorics is a relatively new and growing area of mathematics. Although you can probably find glimpses of it earlier, it's really only been around a couple of hundred years. Indeed the bulk of what we know on the subject has only been known since the last half of the 20th Century.

  Mathematical Reviews is a journal that tries to publish abstracts of all the latest mathematical results. The Combinatorics' (or combinatorial theory) section of Maths Review is one of the largest. There seems to be more research going on in this area than in almost any other field of mathematics.

  Now I must admit that this is partly because Combinatorics is the waste paper basket of mathematics. What I mean by that is that if its mathematics and you don't know what to call it, then call it Combinatorics. So here are some things that are Combinatorics.

  Latin squares are square arrays of numbers that have the property that no number occurs more than once in any row or column. The arrays below are Latin squares.

  Finding Latin squares and how they relate to one another is part of Combinatorics. They have important applications in designing experiments. And they are now extremely popular in the form of the Sudoku puzzles. Here we have some very special, partially filled 9×9 Latin squares, and the problem is to complete the Latin square by putting the remaining entries in.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Logic and Discrete Mathematics

  A Concise Introduction

  • Willem Conradie, Valentin Goranko(Authors)
  • 2015(Publication Date)
  • Wiley

    (Publisher)

  Chapter 6 Combinatorics  

  1. 6.1 Two basic counting principles
  2. 6.2 Combinations. The binomial theorem
  3. 6.3 The principle of inclusion–exclusion
  4. 6.4 The Pigeonhole Principle
  5. 6.5 Generalized permutations, distributions and the multinomial theorem
  6. 6.6 Selections and arrangements with repetition; distributions of identical objects
  7. 6.7 Recurrence relations and their solution
  8. 6.8 Generating functions
  9. 6.9 Recurrence relations and generating functions
  10. 6.10 Application: classical discrete probability

   

  Combinatorics is a branch of mathematics that studies finite, discrete objects. In this chapter we will mostly concern ourselves with enumerative Combinatorics, which studies ways to count sets of finite discrete objects that satisfy given constraints. This typically involves counting the number of ways in which certain patterns can be formed, and enables us to answer questions like:

  • How many possible different outcomes are there in a lottery draw and how many tickets do I need to buy to stand at least a 1% chance of winning?
  • In how many different ways can an amount of 5 euros be made up by coins?
  • How many different DNA strands consisting of a hundred nucleotides are there?
  • In how many different ways can a telephone call from Sydney to Moscow be routed through the telephone network?

  As this list of questions might suggest, Combinatorics has a wide variety of applications, both inside and outside mathematics.

  Apart from learning some fundamental and very useful counting techniques, the reader who masters the content of this chapter will also gain some valuable experience in problem solving and mathematical modelling: the two skills that mathematicians have that are probably most valuable for society. This chapter does not contain a lot of theoretical material; it rather provides some basic principles and methods and shows how they can be applied to solve a wide variety of problems. The problems are typically “word problems”, i.e. problems formulated in everyday language, rather than in mathematical symbols. Solving a problem like this requires first modelling it in some appropriate mathematical way and then finding a suitable strategy based on combinatorial principles to solve it. For these reasons, solving combinatorial problems involves quite a bit of “art”. This is something that comes with experience, and the exercises therefore take on a central role in this chapter.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Statistics and Probability

  • Britannica Educational Publishing, Nicholas Faulkner(Authors)
  • 2017(Publication Date)
  • Britannica Educational Publishing

    (Publisher)

  C ombinatorics is the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. This section also includes the closely related area of combinatorial geometry. One of the basic problems of Combinatorics is to determine the number of possible configurations (e.g. , graphs, designs, arrays) of a given type. Even when the rules specifying the configuration are relatively simple, enumeration may sometimes present formidable difficulties. The mathematician may have to be content with finding an approximate answer or at least a good lower and upper bound.

  In mathematics, generally, an entity is said to “exist” if a mathematical example satisfies the abstract properties that define the entity. In this sense, it may not be apparent that even a single configuration with certain specified properties exists. This situation gives rise to problems of existence and construction. There is again an important class of theorems that guarantee the existence of certain choices under appropriate hypotheses. Besides their intrinsic interest, these theorems may be used as existence theorems in various combinatorial problems.

  Finally, there are problems of optimization. As an example, a function f , the economic function, assigns the numerical value f (x ) to any configuration x with certain specified properties. In this case, the problem is to choose a configuration x 0 that minimizes f (x ) or makes it ε = minimal—that is, for any number ε > 0, f (x 0 ) f (x ) + ε, for all configurations x , with the specified properties.

  History Early Developments

  Certain types of combinatorial problems have attracted the attention of mathematicians since early times. Magic squares, for example, which are square arrays of numbers with the property that the rows, columns, and diagonals add up to the same number, occur in the I Ching , a Chinese book dating back to the 12th century bce . The binomial coefficients, or integer coefficients in the expansion of (a + b )n

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introductory Discrete Mathematics

  • V. K . Balakrishnan(Author)
  • 2012(Publication Date)
  • Dover Publications

    (Publisher)

  Combinatorics

  1.1    TWO BASIC COUNTING RULES

  Combinatorics is one of the fastest-growing areas of modern mathematics. It has many applications to several areas of mathematics and is concerned primarily with the study of finite or discrete sets (much as the set of integers) and various structures on these sets, such as arrangements, combinations, assignments, and configurations. Broadly speaking, three kinds of problems arise while studying these sets and structures on them: (1) the existence problem, (2) the counting problem, and (3) the optimization problem. The existence problem is concerned with the following question: Does there exist at least one arrangement of a given kind? The counting problem, on the other hand, seeks to find the number of possible arrangements or configurations of a certain pattern. The problem of finding the most efficient arrangement of a given pattern is the optimization problem. In this chapter we study techniques for solving problems that involve counting. These techniques form a basis for the study of enumerative Combinatorics, which is really the theory of counting where results involving counting are obtained without carrying out the exact counting process, which could be tedious.

  Suppose that there are 10 mathematics majors and 15 computer science majors in a class of 25 and we are required to choose a student from the class to represent mathematics and another student to represent computer science. Now there are 10 ways of choosing a mathematics major and 15 ways of choosing a computer science major from the class. Furthermore, the act of choosing a student from one area in no way depends on the act of choosing a student from the other. So it is intuitively obvious that there are 10 × 15 = 150 ways of selecting a representative from mathematics and a representative from computer science. On the other hand, if we are required to select one representative from mathematics or

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Central European Olympiad

  The Mathematical Duel

  • Robert Geretschläger, Józef Kalinowski;Jaroslav Švrček(Authors)
  • 2017(Publication Date)
  • WSPC

    (Publisher)

  Chapter 4

  Combinatorics

  4.1.Counting Problems

  In the parlance of modern mathematics competitions, the term “Combinatorics” has come to mean something slightly more general than just the study of enumerative problems. Nowadays, the term includes questions relating to winning strategies for mathematical games, problems relating to graph theory or invariant theory, and more.

  Still, even now the classic counting problem is a staple of mathematics competitions, and the Mathematical Duel is not an exception. In some problems, we count numbers, in some we count words and in some we count geometric figures with a specific property, but the answer is always a number.

  PROBLEMS

  111. A number is called bumpy if its digits alternately rise and fall from left to right. For instance, the number 36 180 is bumpy, because 3 < 6, 6 > 1, 1 < 8 and 8 > 0 all hold. On the other hand, neither 3 451 nor 81 818 are bumpy.

  (a)Determine the difference between the largest and smallest five-digit bumpy numbers. (b)How many five-digit bumpy numbers have the middle digit 5? (c)Determine the total number of five-digit bumpy numbers.

  112. A Goodword is a string of letters, in which there is always at least one vowel between any two consonants, i.e., in which no two consonants appear next to each other. We wish to form Goodwords from the letters of the word “duel”.

  (a)How many different four-letter Goodwords can be formed using all four letters? (b)How many different four-letter Goodwords can be formed with these letters if they can each be used more than once (and therefore not all letters must be used in any specific Goodwords)?

  113. A square ABCD of the size 7 × 7 is divided into 49 smaller congruent squares using line segments parallel to its sides. Determine the total number of paths from the vertex A to the vertex C along lines of the resulting grid, if we are only allowed to move in the directions of the vectors

  114. One large cube ABCDEFGH is formed from eight small congruent cubes. Determine the total number of paths from the vertex A to the vertex G along the edges of the small cubes, if we are only allowed to move in the directions of the vectors

  Sign up to read

  Learn more about book