1. Set notation and basic counting#
Combinatorics is all about counting objects. We introduce the notation for “containers” of objects a.k.a. sets and define operations on sets. Next, we study the first two counting methods: the sum rule and product rule.
1.1 Set notation#
A set is a collection of distinct objects. We usually denote a set by a capital letter, such as , and an element of a set by a lowercase letter, such as . The notation means that is an element of , while means that it is not. We can describe a set by listing its elements surrounded by braces.
Example 1 (The decimal-digit set)#
is the set of decimal digits.
Because a set records membership rather than order, . Repeating an element also does not change a set: . We can also describe a set by a property its elements satisfy. If is a specified universe of possible elements, then we use the notation The colon is read as “such that”.
Example 2 (Sets described by a property)#
is the set of even integers, where denotes the integers.
If , then
The symbol denotes the empty set, the set with no elements.
1.1.1 Set operations#
Let and be subsets of the same universe.
The intersection of and consists of the elements belonging to both sets:
The union of and consists of the elements belonging to at least one of the sets:
Here “or” is inclusive: an element belonging to both and belongs to their union.
The set difference, also called the relative complement, consists of the elements of that do not belong to :
The Cartesian product of two sets and is the set of ordered pairs with chosen from and chosen from :
For more than two sets we can write . If all the sets are the same we write and so on.
Two sets are disjoint if they have no elements in common; equivalently, .
Example 3 (Operations on two finite sets)#
If and , then
1.1.2 Cardinality and inclusion#
For a finite set , its cardinality is the number of elements in .
Example 4 (Cardinalities of finite sets)#
and .
We write if every element of is also an element of :
We write if but . Two sets are equal precisely when they have the same elements: Thus, to prove , it is enough to prove both and .
1.1.3 Logical quantifiers and summation notation#
The symbol means “for every”. The symbol means “there exists”.
Example 5 (Reading quantifiers)#
means that every element of is nonnegative.
says that at least one element of has square .
The symbol means “there exists a unique.” Thus asserts two things: at least one element of satisfies , and no two different elements of both satisfy .
The notation means that we add the terms as the integer index runs from through :
Example 6 (The sum-of-squares formula in summation notation)#
An important formula we will prove later in the course is
1.2 Introduction to counting#
1.2.1 What is a counting problem?#
A counting problem asks for the cardinality of a finite set. The first task is therefore to identify that set. We need to know:
what one outcome is;
when two outcomes are considered different;
what restrictions an outcome must satisfy.
Example 7 (Distinguished dice summing to ten)#
Consider two ordinary six-sided dice, one red and one blue. How many ways can one obtain a roll whose sum is
Because the dice are distinguished by color, an outcome is an ordered pair , where is the red result and is the blue result. We can list all of them The outcomes whose sum is are , so there are three.
Now let us change the problem in two different ways:
Example 8 (What counts as a reroll outcome?)#
Variant 1 Consider two ordinary six-sided dice, one red and one blue. If a roll results in both dice having the same number, we reject the roll and try again.
How many ways can one obtain a roll whose sum is .
Variant 2 Consider two ordinary six-sided dice, one red and one blue. If a roll results in both dice having the same number, we reroll the red die until the two numbers are not the same. How many ways can one obtain a roll whose sum is .
It is not fully clear what the problem is asking us. If a “way” records the entire history of rolls, then, in variant 1, rolling and then rerolling and obtaining is different from rolling . Actually, arbitrarily many ties can occur before an accepted result, so there are infinitely many possible histories. Moreover, in variant 2, if one first rolls there is actually no way to ever get as a sum.
However, if we count only the final accepted ordered pair, then the problem becomes simple: is not allowed, and the two outcomes with sum are and just as before. This is true whether we reroll both dice (variant 1) after a tie or keep the red die and reroll only the blue die (variant 2).
This example shows that it is important to clearly understand what the problem, written in English, means at a precise mathematical level.
Next, we will develop tools that will help us solve the following challenge problem. You can try to solve it on your own, or come back to it once we covered the necessary counting techniques. For now, you should read and understand it, and use it as a motivating example for the things we will learn next
Problem 9 (Committees with and without a chair)#
A company has 20 employees and they need to form a committee of 4 people. How many ways can this be done?
A company has 20 employees and they need to form a committee of 4 people: 1 chair and 3 other general committee members. How many ways can this be done?
1.2.2 The sum rule#
Suppose one object is chosen from either of two finite sets and . If the sets are disjoint, then every object in belongs to exactly one of the two sets. We may therefore add their cardinalities.
Theorem 10 (Sum rule)#
If and are finite disjoint sets, then
Example 11 (Lowercase letters or decimal digits)#
A single character may be either a lowercase English letter or a decimal digit. How many allowed characters are there?
Solution: Let , and . There are lowercase letters and digits. No character is both a lowercase letter and a digit, so . The sum rule gives
If uppercase English letters are also allowed, let be their set. The sets , , and are pairwise disjoint, and the number of allowed characters is
The same reasoning extends to any finite number of cases.
Theorem 12 (General sum rule for disjoint sets)#
Let be finite pairwise disjoint sets. Pairwise disjoint means that
Then
We can rephrase the sum rule in terms of outcomes of procedures, rather tnan sets.
Theorem 13 (General sum rule for mutually exclusive cases)#
Suppose the outcomes of a task are divided into mutually exclusive cases , and every outcome belongs to exactly one case. The total number of outcomes is the sum of the numbers in the cases.
Problem (Check yourself)#
In the character example, identify , , and in the general sum rule, and verify pairwise disjointness.
Disjointness is important!
In the next example, let us see why checking disjointness is very important.
Example 14 (Overlapping brands at two stores)#
Suppose Amazon sells three brands of juice and Walmart sells five brands. How many different brands can a shopper choose from if they may shop at either store?
Wrong solution: The number of brands at amazon is and the number of brands at Walmart is , we need to find the total number of brands . The sum rule tells us that
The problem with this solution is that if the stores carry some of the same brands, adding gives duplicates. is the correct answer only if and do not carry brands in common, that is if . Depending on the overlap, the available information permits any total from through .
Warning 15 (Check the sum-rule hypotheses)#
Before using the sum rule, check that the cases are disjoint and that together they include every outcome being counted.
1.2.3 The product rule#
Suppose an outcome is constructed through a fixed sequence of choices. If
every complete sequence of choices produces exactly one outcome
different choices produce different outcomes,
the number of options at each step of the sequence of choices is fixed and does not depend on the choices made in the other steps,
then the total number of outcomes is obtained by multiplying the numbers of options at each step.
Example 16 (Two-character lowercase strings)#
A two-character string is an ordered sequence in which each entry is one of the 26 lowercase letters a-z.
Solution: There are choices for and, after any first choice, choices for . Therefore there are such strings. Note: The strings and are different because their entries occur in different positions.
The argument allows multiple steps and also allows the specific choices at each step to depend on the other choices made. It is important that the total number of choices at each step remains the same.
Theorem 17 (Product rule)#
Suppose every outcome is constructed uniquely by a fixed sequence of steps. Assume that, after any valid choices in the earlier steps, step has exactly valid options. Then the number of outcomes is The available options may depend on the earlier choices; what must remain fixed is their number .
Example 18 (Three-letter strings with repetition)#
How many strings of length 3 made with letters a-z are there?
Solution: A string can be specified by first choosing the letter in position 1 (step 1), then the letter in position 2 (step 2), then in position 3 (step 3). For each of the steps there are 26 choices. Every string is obtained from exactly one sequence of such choices (different choices give different strings), so the product rule gives
Example 19 (Three-letter strings without repetition)#
How many strings of length 3 made with letters a-z are there such that no letter appears more than once?
Solution: A string can be specified by first choosing the letter in position 1 (step 1), then the letter in position 2 (step 2) and making sure that it is not the same as the letter chosen in position 1, then choosing a letter in position 3 (step 3) while making sure that it is not the letter chosen in position 1 nor in position 2.
Step 1: 26 choices
Step 2: 25 choices (26 letters except the one chosen in step 1)
Step 3: 24 choices (26 letters except the one chosen in step 1 and the one chosen in step 2)
Every valid string is obtained from exactly one sequence of such choices (different choices give different strings), so the product rule gives
It is important to note that in this example the specific choices at steps 2 and 3 depend on the choices made in the previous step but the number of possible choices does not! This allows us to apply the product rule.
Example 20 (Three-letter strings with no symbol appearing three times)#
How many strings of length 3 made with letters a-z are there such that no letter appears more than twice?
Wrong/Incomplete solution: A string can be specified by first choosing the letter in position 1 (step 1), then the letter in position 2 (step 2) (without any restrictions, because the second letter can be the same as the first one and not lead to a forbidden outcome)
In step 3 we choose the letter for position 3.
Step 1: 26 choices
Step 2: 26 choices
Step 3: ?? choices (it depends, if in step 1 and 2 we chose the same letter then we cannot choose it again so we have 25 choices; if we did not choose the same letter we can choose any letter, so 26 choices. )
Possible correct solution: A string can be specified by choosing by first choosing the letter in position 1 (step 1), then the letter in position 2 (step 2), then the letter in position 3 (step 3), all while making sure not to choose a string with the same letter repeated 3 times.
Let us distinguish 2 cases:
D: In step 1 and step 2 we choose different letters
S: In step 1 and step 2 we choose the same letter
By the sum rule, the total amount of strings is going to be since (we cannot both select the same and different letters in step 1 and 2).
Let us compute . Since the first two letters are different we have the following options:
Step 1: 26 choices
Step 2: 25 choices (cannot be the same as step 1)
Step 3: 26 choices (since the first are different, there are no restrictions)
so by the product rule
Let us compute . Since the first two letters are the same we have the following options:
Step 1: 26 choices
Step 2: 1 choice (must be the same letter as step 1)
Step 3: 25 choices (since the first two letters are the same we cannot choose that letter again)
so
The final answer is .
1.3 Strings: an important type of counting problems#
The preceding examples illustrate an important type of counting problem: counting ordered sequences of symbols.
Definition 21 (String over an alphabet)#
Let be a finite set of symbols that we call an alphabet. A string of length over an alphabet is an ordered sequence where each .
Using set notation, a string of length is an element of the Cartesian product .
The position of each symbol is important. For example, ab and ba are different strings. Two strings are equal precisely when they have the same symbol in every position. Repetition is allowed unless the problem states otherwise.
There is also one string of length , called the empty string. It contains no symbols.
Theorem 22 (Strings with repetition)#
Let be an alphabet with symbols, and let be a nonnegative integer. The number of strings of length over is
Proof#
There are positions. Each position may contain any of the symbols, independently of the symbols chosen in the other positions. The product rule therefore gives When , the product has no factors and is equal to , corresponding to the one empty string.
Example 23 (Three-digit strings with repetition)#
Let be the alphabet of decimal digits. The number of strings of length over is These are strings rather than three-digit positive integers, so a string such as 042 is included.
Suppose now that no symbol may occur more than once.
Theorem 24 (Strings without repetition)#
Let be an alphabet with symbols, and let be a nonnegative integer. The number of strings of length over with no repeated symbol is This formula makes sense when , the product in the first line has factors.
When we have . When then .
Proof#
Assuming that . There are choices for the first position. Once a symbol has been used, it cannot be used again, so there are choices for the second position, choices for the third position, and, finally, choices for the th position. The product rule gives The specific digits available at each step depend on the earlier choices, but the number of available digits does not. This is exactly what the product rule requires.
If , a string without repetition would require more than distinct symbols from an alphabet containing only symbols. No such string exists, so .
Example 25 (Three-digit strings without repetition)#
Let be the alphabet of decimal digits. The number of strings of length with no repeating digits over is These are strings rather than three-digit positive integers, so a string such as 042 is included.