Combinatorics

An Introduction

Theodore G. Faticoni

• Publisher: Wiley
• Year: 2014
• ISBN:
  9781118407486
• Edition: 1
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

Bridges combinatorics and probability and uniquely includes detailed formulas and proofs to promote mathematical thinking

Combinatorics: An Introduction introduces readers to counting combinatorics, offers examples that feature unique approaches and ideas, and presents case-by-case methods for solving problems.

Detailing how combinatorial problems arise in many areas of pure mathematics, most notably in algebra, probability theory, topology, and geometry, this book provides discussion on logic and paradoxes; sets and set notations; power sets and their cardinality; Venn diagrams; the multiplication principal; and permutations, combinations, and problems combining the multiplication principal. Additional features of this enlightening introduction include:

• Worked examples, proofs, and exercises in every chapter
• Detailed explanations of formulas to promote fundamental understanding
• Promotion of mathematical thinking by examining presented ideas and seeing proofs before reaching conclusions
• Elementary applications that do not advance beyond the use of Venn diagrams, the inclusion/exclusion formula, the multiplication principal, permutations, and combinations

Combinatorics: An Introduction is an excellent book for discrete and finite mathematics courses at the upper-undergraduate level. This book is also ideal for readers who wish to better understand the various applications of elementary combinatorics.

Chapter 1

Logic

There are several kinds of logic in mathematics. The one based in the construction of Truth tables is called formal logic. This is the logic used in Computer science to design and construct the guts of your Computer. And then there is Aristotle’s logic. This is the logic used to make arguments in court or when arguing informally with another person. This is the logic used to prove that something is, or to prove that something is not. This is the logic used to examine combinations of any of the mathematical ideas encountered in this text. While we will examine formal logic and the logic of sets and functions, we will be most interested in Aristotle’s logic of the argument in this chapter and throughout the rest of the text.

Oh, and there will be no need for a calculator in this book. I have made an effort to emphasize the important mathematical content in this book, not the superfluous, tedious practice of arithmetic. Arithmetic is important when you work with money, but in more challenging mathematical problems it only gets in the way. So cradle your electronic toy if you need to, but there will be almost no use for it as we do our counting.

1.1 Formal Logic

Formal logic is just a series of tables describing how the words and, or, not are defined. There is nothing illuminating with this approach, but it does match the operations of the inner workings of your Computer. We will minimally justify the tables used here. We will just write them down and show how they agree with your use of the words in your language.

These tables define logic. Not just in English, the language that this book is being written in, but they describe logic in every language on earth. If you are reading a Mandarin Chinese translation of this book, then the logic presented here will still be the logic of your language. It is also the binary language in which the Software in your Computer is written. Take time to savor that thought. Logic as it is applied to languages and Computers is universal. Logic is thus common to all forms of communication, analogue or digital.

To begin with we need to know what the logical operations are and what they operate on. Logic operates on statements, and ordinarily we will use the letters P, Q, and R to denote the statements that we we are working on. These statements can take on the logical states T (for True) and F (for False).

You already have an intuitive understanding’ of what it means for a statement to be True or False. You know that The sky is blue is True on earth, and you know that You and I are human is a True statement. You have five dollars might be True right now, but it might be False come late Friday evening. Of course R is raining is a False statement on a sunny day over my home, but it might be a True statement for you where you live. So let us assume that we know what T and F mean in this context.

The first logical operation that we will investigate is the Operation not. The not operation takes a statement P and changes or negates its logical states. It changes T to F and F to T. Its Truth table, the table that lists the logical states of the not operation, follows.

P	not P
T	F
F	T

This is just a tabular way of defining what not is. Notice that according to the table, if P is T then not P is F, and if P is F then not P is T. As we said, not changes a statement’s logical state to the complementary logical state.

EXAMPLE 1.1.1 1. If P is the statement The sky is blue on earth, then not P is the statement The sky is not blue on earth. We have negated P and changed its logical state from T to F.

2. If P is 1 + 2 = 3 then not P is the statement 1 + 2 ≠ 3. Again the logical state of P has been changed by an application of not from T to F.

Because of the nature of the word not, two consecutive applications of the operation not to P will leave the logical states of P unchanged. For lingual reasons we let not not P = not(not P). In tabular form the compound operation not not is written as follows.

P	not P	not (not P)
T	F	T
F	T	F

Notice that if P is T then not P is F, and then not(not P) is T, giving not(not P) the logical states of P. You know this as a double negative from your English dass.

EXAMPLE 1.1.2 1. If P is The sky is blue on earth, then the double negative not (not P) is the awkward sentence It is False that the sky is not blue on earth. Your language skills compel you to avoid the double negative and just write The sky is blue on earth.

2. Suppose P is I think this is wrong. Then not P is I think this is not wrong, and not(not P) is the very awkward I don’t think that this is not wrong. You would be advised by your language teacher to avoid the double negative and just say I think this is wrong. The statements P and not (not P) are written with different words, but logically they express the same meaning.

Thus, by applying the logic of the operator not to a lingual double negative, we can avoid the double not.

Throughout this discussion, suppose that we are given statements P, Q. Several logical operations allow us to compare the logical states of P, Q by combining them.

For instance, we can combine statements P, Q using the and operation. This is the and that you use all of the time when you write. When applied to P, Q the and operation yields the statement “P and Q”. This is just the compound statement formed by combing P, Q with the conjunction and from English.

EXAMPLE 1.1.3 1. If P is The sky is blue on Earth and if Q is You are a man then “P and Q” is the statement The sky is blue on Earth and you are a man.

2. If P is This is wrong and if Q is These are red then “P and Q” is This is wrong and these are red.

The logical states of P and Q are closely related to the way that the word and behaves in language. Thus the logical state of P and Q is T (True) exactly when both P and Q are T. In every other instance, “P and Q” is F (False). Put another way, if one or more of the logical states of P, Q are F (False) then the statement “P and Q” is a Falsehood, its logical value is F.

In the form of a Truth table the and operation is diagrammed as follows:

P	Q	P and Q
T	T	T
T	F	F
F	T	F
F	F	F

The first row states that if both P, Q have logical state T then the conjunction “P and Q” also has logical state T. Once we know that the right hand entry of the first line in the table is T then the rest of the rows follow as F.

EXAMPLE 1.1.4 1. If P is I am a human being and if Q is I am sitting in my chair then “P and Q” is T exactly when I am a human being is T and I am sitting in my chair is T. Any other combina...