2. More counting techniques#
We will now add two operations to our counting toolkit.
The difference rule counts allowed objects by removing forbidden ones.
The division principle corrects a construction that overcounts the same outcome multiple times.
We then use these rules to derive formulas for permutations and combinations - important counting problems that differ by whether order is considered important or not.
Finally, we discuss how strings and sets can be used to model a variety of different combinatorial problems using bijections.
2.1 The difference rule#
We used Theorem 10 to count the elements in a set by subdividing them into separate cases. When solving problems that impose restrictions on the allowed outcomes, it is convenient to first count the total number of possible outcomes and subtract those that are not allowed.
Theorem 1 (Difference rule)#
Let be a finite set. If then Equivalently, if is the universe of all possible objects and is the set of forbidden objects, then the number of allowed objects is .
Proof#
Because , the sets and are disjoint and their union is . The sum rule therefore gives Subtracting from both sides proves the formula.
Example 2 (Recounting strings by subtraction)#
In Example 20, we counted the length- strings over a-z in which no letter appears three times by separating them into cases. Let us now count the same set using subtraction.
Solution: An outcome is an ordered string of three letters. Let be the set of all such strings. Repetition is allowed, so the product rule gives Let be the set of forbidden strings in which one letter appears three times. Such a string is determined by its repeated letter, so . The difference rule gives This is a useful way of counting because forbidden strings are easier to describe than the allowed strings.
This agrees with the earlier case-based count, but subtraction produces the shorter model.
Warning 3 (Subtract only objects inside the universe)#
Suppose and . A careless application of the difference rule gives whereas, actually, The reason for the mistake is that we didn’t check that because . The elements of that can actually be removed are those in . Therefore the correct computation is Before subtracting, always check that the forbidden set is a subset of the universe! If it is not, replace it by its intersection with the universe.
Example 4 (Distinct-digit PINs)#
A four-digit PIN is a string of four digits from 0-9; leading zeroes are allowed. How many four-digit PINs have no repeated digit and contain at least one odd digit?
Incorrect solution: Let be the set of four-digit PINs with no repeated digit. Because a PIN is an ordered string of length 4 chosen from of an alphabet of 10 letters, we get
We want to remove the PINs containing no odd digit. The number of strings containing no odd digits is the strings of 4 digits chosen from the alphabet of the 5 odd digits : Therefore we get that This solution is wrong!
The issue is that cannot be subtracted from because it is not true that . The way we counted is we included pins containing no odd digits but possibly containing repetitions, like the pin 2248. This pin was not accounted for in so we should not be subtracting it.
Correct solution: Instead, let be the set of PINs in whose digits are all even. Then , and its four positions must contain distinct digits chosen from the 5 even digits. Hence The difference rule now gives
The modeling lesson is that the universe and the forbidden set must enforce the same background restrictions. Here, “no repeated digit” is part of the definition of both and .
2.1.1 Counting the same set in two ways#
In Example 20 and Example 2, we counted the same quantity in two different ways. Our approaches clearly work for any alphabet with letters (it doesn’t have to be the standard 26 letter alphabet)
The first approach applied to an alphabet of letters, where gives the formula On the other hand, using the difference rule gives the formula Because both expressions count the same set of strings, we must surely have
By itself, this identity is not very exciting. One can show it by standard algebraic simplification. However, it is interesting because it shows how using different combinatorial approaches can provide a “combinatorial” explanation to important formulas from algebra. This idea is often referred to as double counting, and we will see more examples in the future.
2.1.2 More examples of subtraction#
Example 5 (Decimal strings containing a zero)#
How many length- strings of decimal digits contain at least one 0?
Solution: The objects are strings, so order matters, leading zeroes are allowed, and digits may repeat. Let be the set of all length- decimal strings. Then .
We could try to count strings according to the position of a zero. However the cases would overlap because there are string that have several zeroes.
Instead we exclude the strings with no zero. Each of the six positions has choices, so there are of them. Hence the requested count is
The complement replaces overlapping cases with one product-rule count.
Example 6 (A string with prohibition)#
How many length- strings over the alphabet do not begin with ab?
Solution: Let contain all length- strings over the alphabet. Repetition is allowed, so .
Let contain the strings beginning with ab. Their first two positions are fixed, and each of the remaining six positions has choices. Thus , and the difference rule gives The restriction fixes two particular positions; it does not forbid a or b in the other positions.
Example 7 (Strings containing at least two different symbols)#
How many length- strings over an alphabet of letters with , contain at least two different letters?
Solution: There are strings in total. If a string does NOT have two different letters then it is just one letter repeated 5 times like aaaaa. So there are forbidden strings. Therefore the quantity we are looking for is Note: for the boundary case (that is an alphabet of one letter), this gives , as it should! There is no way to have at least two different letters if all you have is one letter.
2.2 The division principle and permutations#
Theorem 17 requires every outcome to be constructed uniquely by the specified sequence of choices. The division principle handles a controlled failure of that uniqueness.
Sometimes a convenient construction is not unique. If every outcome is represented the same number of times, we can correct the overcount.
Theorem 8 (Division rule for constant overcounting)#
Suppose a construction produces representations, and every unique outcome has exactly representations, where . Then the total number of outcomes is .
Proof#
Let us count all the possible representations . We do it in two steps. First we choose the outcome to which it corresponds. Then, having chosen the outcome, we choose the specific representation that gives that outcome.
There are outcomes (choices at step 1)
There is representations to choose from once the “outcome” has been established ( choices at step 2).
The number of choices at each step does not depend on the choices of the other steps so we apply the product rule to obtain: , and therefore , as desired.
Warning 9 (The overcounting factor must be constant)#
Division is justified only when every outcome is represented exactly the same number of times. If some outcomes have more representations than others, there is no single overcounting factor by which to divide.
Next, we will apply this principle to count strings where the order of characters does not matter, but only the characters actually present do.
2.3 Unordered selections: combinations without repetition#
Lecture Note 1 introduced Section 1.3 as ordered objects and Section 1.1 as unordered collections. We now use the division rule to pass from ordered representations to unordered selections.
First, we introduce an important mathematical notation, the factorial.
Definition 10 (Factorial)#
For an integer , we define (pronounced “ factorial”) the quantity that is the product of the numbers from to .
We also define , matching the convention that an empty product equals .
The factorial is closely related to the concept of order. Indeed let us count the ways to order or arrange a total of distinct characters.
Example 11 (Anagrams: n distinct characters)#
What is the number of anagrams (permutations) of a string of distinct characters?
Solution: A permutation of a string of characters is another length- string over the alphabet consisting of those characters, with no repetition. Therefore the number of anagrams (permutations) of a string of distinct characters is
Theorem 12 (Factorial formula for -permutations)#
The product defining in Theorem 24 can be written as The division removes all the numbers from downwards from the product in the numerator: as desired.
We now have the notation needed to count unordered selections. A -element subset of a set is a subset with .
Definition 13 (Binomial coefficient)#
For integers and , the binomial coefficient is the number of -element subsets of an -element set.
In other words, it is the number of ways to choose different elements from possible options, disregarding the order in which we choose it.
Theorem 14 (Formula for combinations without repetition)#
For ,
Proof#
Let as associate to each set the list of its elements: if with we write Effectively, we associated to a string of characters chosen from the alphabet . We do not allow repetitions since the same element may not be listed multiple times.
The number of strings of length from an alphabet of characters is exactly . However, is it true that every string corresponds to a different set? No! if we take a string or any of its premutations, we will describe the same set. Since the number of permutations of a string of distinct characters is we will be overcounting every outcome (set) times. According to the division rule, the number we are looking for is therefore
Example 15 (Choosing a committee)#
Return to part 1 of Problem 9: a company has employees and must form a four-person committee.
Solution: An outcome is a four-element subset of the set of employees. The employees are distinct, nobody can be selected twice, and positions on the committee are not distinguished. Therefore the number of committees is
If we had selected the four employees in sequence, we would have counted every committee times—once for each ordering of its members. Dividing by turns ordered selections into unordered subsets.
Warning 16 (Do not divide merely because the problem says “choose”)#
Do not divide by merely because a problem uses the word “choose.” First decide what an outcome is and decide whether the order matters
We are now ready to solve the second part of the earlier challenge problem.
Example 17 (Choosing a committee with a chair)#
Return to part 2 of Problem 9: a company with employees must select a committee with one chair and three other members.
Solution 1: Let us split the selection into two steps. First we select the chair. Then, among the remaining 19 employees, we select a subset of 3 to serve as line members of the commitee.
Step 1 gives us 20 choices.
In step 2 we select a subset of 3 out of the remaining 19 employees. This can be done in ways.
Each of these choices yields a valid committee and each possible commitee is the result of a unique choice in our described procedure. Therefore, by the product rule, the total number we are looking for is
Solution 2: Let us select the 4 employees to serve on the commitee in order. This can be done in ways. The first person selected is the chair while the remaining 3 are the line members. Each of these orderred selections yields a valid committee, however different selections can lead to the same outcome. For example abcd and acbd both correspond to a commitee with as chair and as commitee line memebers.
By how much do we overcount? Any permutation of the last 3 characters gives the same outcome so every outcome is counted times. By the division principle our answer is then
2.4 Counting problems#
Many combinatorial problems can be solved by modeling them using settings we have become familiar with: ordered strings or unordered subcollections.
In particular, if we manage to esablish a “bijection” (a 1-to-1 and onto relationship) between a problem and another one we know how to solve, then the number of outcomes in both has to be the same.
Next we provide a list of examples linking common mathematical counting problems to the ones we already studied.
2.4.1 Number of subsets of a set#
Example 18 (Counting all subsets)#
Let be a finite set with elements. How many subsets does have? In other words: how large is the collection of all sets that are subsets of ?
Solution: First, let us number the elements of from to .
To a subset , associate the binary string of length as follows: Every subset produces exactly one binary string. Conversely, every binary string specifies exactly one subset by selecting exactly when . Therefore we have established a bijection between the objects we are counting (subsets) and things we know how to count (strings).
There are choices for each of the positions, so there are subsets of .
For , the formula gives one subset: the empty set itself.
2.4.2 Functions from one set to another#
For sets and , a function assigns exactly one element to each element .
Example 19 (Functions from one set to another)#
Suppose and , where . How many functions are there?
Solution: List the elements of as . A function is determined uniquely by the string For each input , there are possible outputs, with repetition allowed. The product rule therefore gives functions. When , there is one function from the empty set to , corresponding to the empty string, so the value is .
Example 20 (Injective functions from one set to another)#
Suppose and , where . How many injective functions are there?
Solution: We require that different inputs must receive different outputs. As before, list the elements of as . The function is determined uniquely by the string and the function is injective if and only if the string does not have repeating characters.
Therefore we have estabished a bijection between injective functions and strings of length of an alphabet of letters.
There are such functions.
Careful, it is easy to mess up the role of and in the formulas above! One way to help remeber is to try the case when , that is functions from 1 possible input to possible outputs..