Introduction to Combinatorics

Walter D. Wallis, John C. George

• Éditeur: Chapman and Hall/CRC
• Année: 2016
• ISBN:
  9781498777629
• Édition: 2
• Sujet: Mathematics
• Sous-sujet: Mathematics General

What Is Combinatorics Anyway?

Broadly speaking, combinatorics is the branch of mathematics dealing

with different ways of selecting objects from a set or arranging objects. It

tries to answer two major kinds of questions, namely, counting questions: how many ways can a selection or arrangement be chosen with a particular set of properties; and structural

questions: does there exist a selection or arrangement of objects with a

particular set of properties?

The authors have presented a text for students at all levels of preparation.

For some, this will be the first course where the students see several real proofs.

Others will have a good background in linear algebra, will have completed the calculus

stream, and will have started abstract algebra.

The text starts by briefly discussing several examples of typical combinatorial problems

to give the reader a better idea of what the subject covers. The next

chapters explore enumerative ideas and also probability. It then moves on to

enumerative functions and the relations between them, and generating functions and recurrences.,

Important families of functions, or numbers and then theorems are presented.

Brief introductions to computer algebra and group theory come next. Structures of particular

interest in combinatorics: posets, graphs, codes, Latin squares, and experimental designs follow. The

authors conclude with further discussion of the interaction between linear algebra

and combinatorics.

Features

• 
  
  

• Two new chapters on probability and posets.

• 
  
  

• Numerous new illustrations, exercises, and problems.

• 
  
  

• More examples on current technology use

• 
  
  

• A thorough focus on accuracy

• 
  
  

• Three appendices: sets, induction and proof techniques, vectors and matrices, and biographies with historical notes,

• 
  
  

• Flexible use of MapleTM and MathematicaTM

Chapter 1

Introduction

Broadly speaking, combinatorics is the branch of mathematics that deals with different ways of selecting objects from a set or arranging objects. It tries to answer two major kinds of questions, namely the existence question (Does there exist a selection or arrangement of objects with a particular set of properties?) and the enumerative question (How many ways can a selection or arrangement be chosen with a particular set of properties?). But you may be surprised by the depth of problems that arise in combinatorics.

The main point to remember is that it really doesn’t matter what sort of objects are being discussed. For example, we shall often assume that we are talking about sets of numbers, and sometimes use their arithmetical or algebraic properties. But these methods are used to prove results that we then apply to all sorts of objects.

In the first section we shall show you a few examples of combinatorial problems. In Section 1.2 we briefly summarize some ideas of and notations of set theory (if you need to review this material, see Appendix A). The remainder of the chapter introduces some basic combinatorial ideas.

1.1 Some Combinatorial Examples

Some of these problems have a recreational flavor, puzzles and so on, because they will be more familiar; but all these ideas have very serious applications. We address many of them in more detail in subsequent chapters.

Passwords

We start with an enumerative problem. Enumeration (the theory of counting) is an important part of combinatorics.

Most computer systems require passwords, in order to protect your information and your privacy. For example, the social networking program Youface™ requires everybody to have an eight-character password made up of letters and digits. The passwords are case-sensitive, but the letter O is not allowed (to avoid confusion with zero), so there are 60 symbols available. How many different passwords could you choose?

There are 60 choices for the first character. For each of those there are 60 possible second characters, for 3600 possible 2-character starts, and so on. In all, there are 60⁸, or about 168 trillion, passwords. This calculation is an example of the multiplication principle, which we’ll discuss further in Section 1.3, later in this chapter.

Suppose a hacker wants to break into your Youface account. She has a program that can generate and test a thousand passwords per second. Is she dangerous?

Well, if she tests every possibility, it will take her over 5,000 years. So no, your password is pretty secure.

However, you need to be careful about passwords. Dr. John Walters, a computer science professor that we shall meet again in this volume, always uses the login jwalters. Having a poor memory, he always starts his password with his initials, jw, and ends with the last two digits of the year. The hacker found this out, so in 2009 she worked out that his password had the form jw****09. There are 60⁴ = 12, 360, 000 passwords of this form. That sounds like a lot, but in 3.6 hours she could run every possible password. Even if she is very unlucky, and her computer does not find the actual password until very late in the run, she could still hack into his account in an afternoon.

In order to protect people like Dr. Walters, Youface introduced some further requirements. Your password cannot begin with the same two symbols as your username, and the last two digits cannot be the last two digits of the year. In 2010, when he rebuilt his account, Dr. Walters could not choose any password of the form jw****** or ******10.

How many possible passwords remained? We start with 60⁸ possibilities, and subtract the number of passwords that were banned. There were 60⁸ passwords originally. There are 60⁶ passwords of type jw******, and 60⁶ of type ******10. Subtracting these numbers leaves 60⁸ − 2 × 60⁶. However, we have taken away some passwords twice: those of form jw****10. There are 60⁴ passwords like this, so we have “oversubtracted” 60⁴ from the total. So the final result is 60⁸ − 2 × 60⁶ + 60⁴.

This method of counting—subtract all objects in one class, do the same with those in another class, then add back those that were common to both classes—is the first case of the Principle of Inclusion and Exclusion. We shall deal with this further in Chapter 5.

The Pancake Problem

Another good example of a combinatorial problem is this: Into how many regions can the plane be divided by n straight lines, given that no lines are parallel and at most two lines intersect at any point? These conditions ensure the maximum number of regions. This is sometimes called the Pancake Problem because we may draw a large enough circle (the “pancake”) surrounding all points of intersection of the lines, so that the problem may be described as: What is the maximum number of pieces remaining after cutting a pancake with n cuts (none parallel and no three concurrent)?

FIGURE 1.1: Pancake with three slices.

The first thing we do is define a notation and try a few examples. This is almost always a good start to any kind of problem. We let P_n be the maximum number of pieces. Then it is easy to see that P₀ = 1 (with no cuts, the pancake is still one piece) and P₁ = 2. When we notice that P₂ = 4, we see the progression 1, 2, 4 and wonder whether we might have powers of two; perhaps, we think, P_n = 2ⁿ? This would make sense if each cut passes through every region, so that each region is cut into two. However, this does not happen, and we find P₃ = 7, as we can see from Figure 1.1. A few more tries will give us P₄ = 11 and P₅ = 16. Clearly, another approach is needed.

How many new regions do we get by adding a new cut? If we have n−1 cuts in the pancake, and add another cut, the rules require that the new cut must intersect each of the n−1 old cuts. If we start the cut on the edge of the pancake in the middle of a region, we cut along the pancake and cut off a new region when we reach the first of the n−1 old cuts. Then as we continue cutting in a straight line, we intersect each of the other old cuts, cutting off a new region when we do. Then at the end, we reach the edge of the pancake, and we cut off a final piece. This means that we have added n pieces; one for each of the original n−1 cuts, and one when...