6. Counting
Counting problems arise throughout mathematics and computer science. In CS, we need to measure the time complexity of given algorithms, and know the number of passwords of a computer system and so on.
6.1 The Basics of Counting
6.1.1 Basic Counting Principles
**The Product Rule**
Suppose that a procedure can be broken down into two tasks. If there are 
ways to do the first task and 
ways to do the second after the first task has been done, then there are 
ways to complete the procedure.
In terms of sets, if 
are finite sets, then the number of elements in the Cartesian product of these sets is the product of the number of elements of each set. The task of choosing an element in the Cartesian product 
is done by choosing an element in 
, an element in 
, … , and an element in 
. By the product rule, it follows that 
**The Sum Rule**
If a task can be done either in one of 
ways or in one of 
ways, where none of the set of 
ways is the same as any of the set of 
ways, then there are 
ways to do the tasks.
In terms of sets, 
where 
for all 
.**The Subtraction Rule**
If a task can be done in either 
ways or 
ways, then the number of ways to do the task in 
minus the number of ways to do the task that are common to the two different ways. The subtraction rule is also known as the principle of inclusion-exclusion.**The Division Rule**
There are 
ways to do a task if it can be done using a procedure that can be carried out in 
ways, and for every way 
, exactly 
of the 
ways correspond to way 
.
Restated in terms of sets: If the finite set 
is the union of 
pairwise disjoint subsets each with 
elements, then 
.
In terms of functions: If 
is a function from 
to 
, where both are finite sets, and for every value 
there are exactly 
values 
such that 
, then 
.
🌰 e.g.
How many ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left and right neighbor?
Solution:
Number the seats around the table from 1 to 4 proceeding clockwise. There are four ways to select the person for seat 1, three for seat 2, two for seat 3, and one way for seat 4. Thus there are 4! = 24 ways to order the four people. But since two seatings are the same when each person has the same left and right neighbor, for every choice for seat 1, we get the same seating. Therefore, by the division rule, there are 24/4 = 6 different seating arrangements.
6.1.2 Tree Diagrams
We can solve many counting problems through the use of tree diagrams, where a branch represents a possible choice and the leaves represent possible outcomes.
6.2 The Pigeonhole Principle
📋The Pigeonhole Principle (Also called Dirichlet Drawer Principle)
If 
is a positive integer and 
or more objects are placed into 
boxes, then there is at least one box containing two or more of the objects.
Proof:
We use a proof by contraposition. Suppose none of the 
boxes has more than one object. Then the total number of objects would be at most 
. This contradicts the statement that we have 
objects.
🌰e.g.
In a party of 2 or more people, there are 2 people with the same number of friends in the party, assuming you can’t be your own friend and that friendship is mutual.
Pigeons : the 
people (with 
).
Pigeonholes: the possible number of friends, i.e. the set 
🌰e.g.
Show that for every integer 
there is a multiple of 
that has only 0s and 1s in its decimal expansion.
Solution:
Let 
be a positive integer. Consider the 
integers 1, 11, 111, … , 11…1 (where the last has 
1s). There are 
possible remainders when an integer is divided by 
.
By the pigeonhole principle, when each of the 
integers is divided by 
, at least two must have the same remainder. Subtract the smaller from the larger and the result is a multiple of 
that has only 0s and 1s in its decimal expansion.
📋The Generalized Pigeonhole Principle
If 
objects are placed into 
boxes, then there is at least one box containing at least 
objects.
Proof:
Suppose that none of the boxes contains more than 
objects. Then, the total number of objects is at most 
.
🌰e.g.
Show that among any 
positive integers not exceeding 
there must be an integer that divides one of the other integers.
Solution:
🌰e.g.
During 11 weeks football games will be held at least 1 game a day, but at most 12 games be arranged each week. Show that there must be a period of some number of consecutive days during which exactly 21 games must be played.
Solution:
Let xi be the number of football games helded on the i-th day.
Let 
be 
, where
Let 
be
, so 
,
Since
, there exist integers
that 
So 
🌰e.g.
Every sequence of 
distinct integers contains a subsequence of length 
that is either strictly increasing or strictly decreasing.
Proof:
🌰e.g.
6.3 Permutations and Combinations
6.3.1 Basic Concepts
**Permutation** An ordered arrangement of the elements of a set.**r-Permutation** An ordered arrangement of 
elements of a set
📋The number of r-permutations of a set with 
distinct elements is
Specially, 
, 
.**r-Combination** An unordered selection of 
elements of a set. An r-combination is simply a subset of a set with 
elements.
📋The number of r-combination of a set with 
elements, where 
is a positive integer and 
is an integer with 
, denoted by 
, equals to 
📋Combination Corollary
Let 
and 
be nonnegative integers with 
. Then 
6.3.2 Combinatorial Proof
A **combinatorial proof** of an identity:
**Double Counting Proofs**Uses counting arguments to prove that both sides of the identity count the same objects but in different ways.**Bijective Proofs**Show that there is a bijection between the sets of objects counted by the two sides of the identity.6.4 Binomial Coefficients
💡二项式定理也是高中就学了的。
A**binomial expression**is the sum of two terms, such as
. (More generally, these
terms can be products of constants and variables.)
📋The Binomial Theorem
Let
and 
be varaibles, and let 
be a nonnegative integer. Then 
.
Proof:
We can use counting principles to find the coefficients in the expansion of
. To form the term 
, it is necessary to choose 
s and 
s from the 
sums.
📋Corrolaries for the Binomial Theorem
, 
, 
📋Pascal’s Identity
Let
and 
be positive integers with 
. Then 
.
Proof:
We construct a subset of size
form a set 
with 
elements. The total will include:
All of the subsets from the set of size
which do not contain the element 
, 
, plus the subsets of size 
with the element 
added 
.
📋Pascal’s Triangle
The nth row in the triangle consists of the binomial coefficients
. By Pascal’s identity, adding two adjacent bionomial coefficients results is the binomial coefficient in the next row between these two coefficients.
📋Vandermonde’s Identity
Let
, 
and 
be nonnegative integer with 
not exceeding either 
or 
. Then 
.
📋If
is a nonnegative integer. Then 
.
Proof:
We use Vandermonde’s Identity with
to obtain 
.
📋Let
and 
be nonnegative integer with 
, then
.
Proof:
The left-hand side counts the bit strings of length
containing 
1s. We show that the right-hand side counts the same objects by considering the cases corresponding to the possible locations of the final 1 in a string with 
ones.
6.5 Generalized Permutations and Combinations
6.5.1 Permutations and Combinations with Repetition
📋The number of r-permutations of a set of
objects with repetition allowed is 
.
📋There are
r-combination from a set with 
elements when repetition of elements is allowed.
Proof:
- The
bars are used to mark off 
different cells, with the ith cell contains a star for each time the ith element of the set occurs in the combination. For example, | | | | * means the first element occurs twice, the second element occurs once, the fourth element occurs once, and the fifth element occurs three times. - Each r-combination of a set with n elements when repetition is allowed can be represented by a list of
bars and 
stars. - The number of such lists is
.
🌰e.g.
How many solutions are there to the equation 
where 
is nonnegative integer?
Solution:
Since a solution of this equation corresponds to a way of selecting 16 items from a set with four element, such that 
items of type one, 
items of type two, 
items of type three, 
items of type four are chosen.
Hence the number of solutions is 
.
How about the number of solutions to 
?
Solution:
We can introduce an auxiliary variable 
so that 
.
.
6.5.2 Permutations with Indistinguishable Objects
📋The number of different permutations of 
objects, 
, where there are 
indistinguishable objects of type 1, … ,and 
indistinguishable objects of type k, is 
.
Proof:
🌰e.g.
How many different strings can be made form the letters in MISSISSIPPI, using all the letters?
Solution:
, so there are 
different strings.
6.5.3 Distributing Objects into Boxes
Many counting problems can be solved by counting the ways objects can be placed in boxes. The objects may be either different from each other (distinguishable) or identical (indistinguishable). The boxes may be labeled (distinguishable) or unlabeled (indistinguishable).
📋The number of ways to distribute 
distinguishable objects into 
distinguishable boxes so that 
objects are place into box i, i=1,2,…,k, equals 
.
It can be proved by setting up a one-to-one correspondence between the permutations in the last theorem and the ways to distribute objects counted here.
🌰e.g.
How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?
Solution:
It is typical problem that involves distributing distinguishable objects into distinguishable boxes.
The distinguishable objects are the 52 cards.
The five distinguishable boxes are the hands of the four players and the rest of the deck.
So there are 
kinds of distribution.
📋There are 
ways to place 
indistinguishable objects into 
distinguishable boxes.
Proof based on one-to-one correspondence between k-combinations from a set with n-elements when repetition is allowed and the ways to place 
indistinguishable objects into 
distinguishable boxes.
📋Stirling Numbers（斯特林数） of the Second Kind
, the number of ways to distribute 
distinguishable objects into 
indistinguishable boxes so that no boxes is empty.
is the number of ways to partition the set with nelements into 
nonempty and disjoint subsets.
is the number of ways to distribute 
distinguishable objects into 
distinguishable boxes so that no boxes is empty.
is the number of ways to place 
distinguishable objects into 
indistinguishable boxes.
6.6 Generating Permutations and Combinations
**Lexicographic Ordering for Permutations**The permutation
precedes the permutation of 
, if for some 
, with 
, 
, and 
.
📋Generating All the Permutations
- List the elements in lexicographic order.
- Find the least permutation.
- Find the next least permutation until the largest permutation is found.
🌰e.g.
Algorithm of producing the 
permutations of the integers 
.
- Begin with the smallest permutation in lexicographic order, namely
. - Produce the next largest permutation.
- Continue until all
permutations have been found.
📋Generating All the Combinations
- A combination is just a subset, so we need to list all subsets of the finite set.
- Use bit strings of length
to represent a subset of a set with 
elements. If the subset contains the ith element, then the ith bit of the string is 1; otherwise the ith bit is 0. - The
bit strings can be listed in order of their increasing size as integers in their binary expansions.
8. Advanced Counting Techniques
8.1 Applications of Recurrence Relations
A**recurrence relation**for the sequence
is an equation that express 
in terms of one or more of the previous terms of the sequence, namely, 
, for all integers 
with 
, where 
is a nonnegative integers. 
A**solution**of a recurrence relation is a sequence if its terms satisfy the recurrence relation. Normally, there are many sequences which satisfy a recurrence relation. We should distinguish them by initial conditions.
The**degree**of a recurrence relation is the number of initial conditions it needs to determine a specific sequence. For example,
is a recurrence relation of degree 8.
💡Many relationships are most easily described using recurrence relations.
🌰e.g.
Find a recurrence relation for the number of bit strings of length
that don’t have two consecutive 0s.
Solution:
Let
denote the number of bit strings of length 
that don’t have two consecutive 0s.
Recurrence relation:
.
Initial conditions:
.
Note that
satisfies the same recurrence relation as the Fibonacci sequence. Since 
and 
, we conclude that 
.
⚙️ Recurrence relations play an important role in many aspects of the study of algorithms and their complexity.
- Dynamic programming algorithm
- An algorithm follows the dynamic programming paradigm when it recursively breaks down a problem into simpler overlapping subproblems, and computes the solution using the solutions of the subproblems.
- Recurrence relations are used to find the overall solution from the solutions of the subproblems.
- Divide-and-conquer algorithm
where 
are real numbers, and 
.**Linear**: The right-hand side is a sum of the previous terms of the sequence each multiplied by a
function of 
.**Constant Coefficients**: The coefficients in the sum of the 
s are constants, independent of 
.**Degree**: 
is expressed in terms of the previous 
terms of the sequence. By strong induction, a sequence satisfying such a recurrence relation is uniquely determined by the recurrence relation and the 
initial conditions 
.**Homogeneous**: Because no terms occur that are not multiples of the 
s. Otherwise **inhomogeneous** or **nonhomogeneous**.
📋 Solving Linear Homogeneous Recurrence Relation with Constant Coefficients
Two key ideas to find all their solutions:
- These recurrence relations have solutions of the form
, where 
is a constant.
The last equation is called the **Characteristic Equation**, and the roots of the equation is called the **Characteristic Roots**. The sequence 
with 
where 
is a solution if and only if 
is a characteristic root.
- A linear combination of two solutions of a linear homogeneous recurrence relation is also a solution.
Suppose that 
and 
are both solutions of this recurrence relation.
Then we have
and
Now suppose that 
and 
are real numbers. Then
This means that 
is also a solution of the same linear homogeneous recurrence relation.
📋 The Degree 2 Case
Let 
be real numbers. Suppose that 
has two distinct roots 
. Then the sequence 
is a solution of the recurrence relation 
if and only if 
for 
, where 
are constants.
Proof:
Show that if 
is a solution, then 
for some constant 
.
The initial conditions 
hold. It will be shown that there are constants 
such that the sequence 
with 
satisfies these same initial conditions. This requires that:
Hence, with these values for 
, the sequence 
with 
satisfies the two initial conditions. We know that 
and 
are both solutions of the recurrence relation and both satisfy the initial conditions when 
and 
.
Because there is a unique solution of a linear homogeneous recurrence relation of degree two with two initial conditions, it follows that the two solutions are the same.
📋 The Solution of the Degree 2 Case when there is a Repeated Root
Let 
be real numbers with 
. Suppose that 
has only one root 
. A sequence 
is a solution of the recurrence relation 
if and only if 
, where 
are constants.
📋 The General Case
Let 
be real numbers. Suppose that the characteristic equation has 
distinct roots 
. Then a sequence 
is a solution of the recurrence relation 
if and only if 
for 
where 
are constants.
The coefficients 
are found by enforcing the initial conditions.
📋 The General Case with Repeated Roots Allowed
Let 
be real numbers. Suppose that the characteristic equation 
has 
distinct roots with multiplicities 
, respectively, so that 
for 
and 
. Then a sequence 
is a solution of the recurrence relation 
if and only if 
for 
where 
are constants.
8.2.2 Linear Nonhomogeneous Recurrence Relation With Constant Coefficients
, where 
are real number, 
is a function not identically zero depending only on 
. 
is called the **associated homogeneous recurrence relation**. Solution to nonhomogeneous case is sum of solution to associated homogeneous recurrence system and a **particular solution** to the nonhomogeneous case.
📋 Solving Linear Nonhomogeneous Recurrence Relations with Constant Coefficients
Let 
be a particular solution of the nonhomogeneous linear recurrence relation with constant coefficients 
. Then every solution is of the form 
, where 
is a solution of the associated homogeneous recurrence relation 
.
📋 Assume a linear nonhomogeneous recurrence equation with constant coefficients with the nonlinear part 
of the form 
. If 
is not a root of the characteristic equation of the associated homogeneous recurrence equation, there is a particular solution of the form 
. If 
is a root of multiplicity 
, a particular solutions is of the form 
.
8.4 Generating Function
如果觉得不好理解可以看这篇文章：
The **generating function**（生成函数） for a finite sequence 
of real numbers is the series 
.
The generating function for a infinite sequence 
of real numbers is the infinite series 
.
📋 Let 
, 
, then 
.
Proof:
🌰 e.g.
Suppose that the generating function of the sequence 
is 
. What is the generating function for the sequence 
?
Solution:
So 
. The generating function of 
is 
.
So 
.
📋 The Extended Binomial Coefficient
Let 
be a real number and 
a nonnegative integer. Then the extended binomial coefficient is defined by 
.
📋 Let 
be a real number with 
and let 
be a real number. Then 
📋 Counting Problems Using Generating Functions
This method is shown in the following examples.
🌰 e.g.
Find the number of solutions of 
, where 
, 
, and 
are nonnegative integers with 
, 
, and 
.
Solution:
The number of solutions with the indicated constraints is the coefficient of 
in the expansion of 
. This follows because we obtain a term equal to 
in the product by picking a term in the first sum 
, a term in the second sum 
, and a term in the third sum 
, where 
. It is not hard to see that the coefficient of 
in this product is 3. Hence, there are three solutions.
🌰 e.g.
Use generating functions to find the number of r-combinations from a set with 
elements when repetition of elements is allowed.
Solution:
Since there are 
elements in the set, each can be selected zero times, one times and so on. It follows that 
.
the number of r-combinations from a set with 
elements when repetition of elements is allowed, is the coefficient ar of 
in the expansion of 
. Since 
. Then the coefficient 
equals 
.
🌰 e.g.
Suppose that there are 
red balls, 
blue balls, and 
white balls. How many ways to select 
balls from these balls?
Solution:
The coefficient 
of 
in the expansion of 
is the solution of this problem.
So 
, so 
.
🌰 e.g.
Determine the number of ways to insert tokens worth $1,$2 and $5 into a vending machine to pay for an item that costs r dollars in both the case when the order in which the tokens are inserted does not matter and when the order does matter.
Solution:
(1) When the order in which the tokens are inserted does not matter:
The coefficient of 
in the expansion of 
is the solution of this problem.
(2) When the order in which the tokens are inserted does matter:
The number of ways to insert exactly 
tokens to produce a total of $r is the coefficient of 
in 
. Since any number of tokens may be inserted, the number of ways to produce $r using $1,$2 and $5 tokens, is the coefficient of 
in 
.
📋 Use Generating Function to Solve Recurrence Relations
This method is shown in the following examples.
🌰 e.g.
Use generating functions to solve the recurrence relation 
with initial conditions 
.
Solution:
Multiply by 
on both sides of 
.
8.5 Inclusion-Exclusion and Its Application
📋 The Formula for the Number of Elements in the Union of n Finite Sets
There are 
terms in this formula.
Proof:
An element in the union is counted exactly once by the right-hand side of the equation.
Suppose that 
is an element of exactly 
of the sets 
where 
. This element is counted 
times by 
, 
times by 
, …
Thus it is counted exactly 
.
📋 An Alternative Form of Inclusion-Exclusion
To solve problems that ask for the number of elements in a set that have none of 
properties 
. Let 
be the the subset containing the elements that have property 
. Let 
be the number of elements with all properties 
. It follows that 
. Let 
be the number of elements with none of the properties 
. From the inclusion-exclusion principle, we see that: 
📋 The Sieve of Eratoshenes
A method to find the number of primes not exceeding a specified positive integer.
🌰 e.g.
Take 100 for example.
Solution:
A composite integer is divisible by a prime not exceeding its square root, so composite integer not exceeding 100 must have a prime factor not exceeding 10. Since the only primes less than 10 are 2,3,5,7, the primes not exceeding 100 are these four primes and the positive integers greater than 1 and not exceeding 100 that are divisible by none of 2,3,5,7.
Firstly, we pick out the composites divisible by 2 and change their color into grey. Then pick out the composites divisible by 3 from the rest numbers and so on. Then the black integers are the primes we want.
🌰 e.g.
Let 
and 
be positive integers with 
. Then, there are 
onto functions from a set with 
elements to a set with 
elements.
Proof:
Let 
be the property that 
is not in the range of the function, respectively. A function is onto if and only if it has none of these properties.**Derangement**: A derangement is a permutation of objects that leaves no object in the original position.
🌰 e.g.
21453 is a derangement of 12345 because no number is left in its original position.
📋 The number of derangements of a set with 
elements can be calculated using inclusion-exclusion, and is 
.
Proof:
Let a permutation have property 
if it fixes element 
. The number of derangements is the number of permutation having none of the properties 
for 
, namely.
若有收获，就点个赞吧
0 人点赞
