Discrete Mathematics

Basic counting

Vietnamese German University

Instructor: Tran Thi Thu Huong, VGU
Email: [Link]@[Link]
Office: A109
Basic counting

References:

1. Rosen’s textbook: Chapter 6 (Counting)

2. Stanley’s book: Enumerative combinatorics, Vol. 1
Basic counting rule I

Topics covered:

1. The sum/product/division/bijection principle

2. Two ways for counting and combinatorial identities: Binomial
coefficient, Pascal’s triangle.
3. Partitions of a set: Stirling number of the second kind, Bell
number
4. Permutations: one-line/two-line/cycle notation, circular
permutations, Stirling number of the first kind
5. Combinations and permutation with repetition
6. Finite functions and twelve ways for counting
7. The pigeonhole principle and Ramsey theory
Basic counting rule II

Notations

1. From now on, we denote [n] the set of n elements

{1, 2, . . . , n}.
2. Let n be a natural integer. Denote n! = n · (n − 1) · . . . 2 · 1
the factorial of n. By convention 0! = 1.
3. An n-tuple is a list of n ordered elements (x1 , x2 , . . . , xn ).
Introduction to the counting problem I
Counting problem:

I Given a set of objects X . How many elements are there in X ?

I Given X (n) the set of objects of size n. How many elements
are there in Xn ?
I Given X (n, k) the set of objects of sizes n and k. How many
elements are there in Xn ?
I ...

1. Binary strings of length n: Let Bn (capital B) denote the set

of all binary strings of length n and bn = |Bn | (small b) be the
number of binary strings of length n.
I n = 0: B0 = {} and b0 = 1;
I n = 1: B1 = {0, 1} and b1 = 2;
I n = 3: B2 = {00, 01, 10, 11} and b2 = 4;
I n = 4: B3 = {000, 001, 010, 100, 011, 101, 110, 111} and
b3 = 8
I For general n: bn = 2n .
Introduction to the counting problem II

2. Subsets of two elements (in general, k elements) of a set of n

elements. Let An be the collection of 2-element subsets of [n]
and let an = |An | be the number of 2-element subsets of [n].
In particular,
I n = 0: A0 = ∅ and a0 = 0;
I n = 1: A1 = ∅ and a1 = 1;
I n = 2: A2 = {1, 2} and a2 = 1;
I n = 3: A3 = {{1, 2}, {1, 3}, {2, 3}} and a3 = 3;
I n = 4: A3 = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}} and
a4 = 6;
I For general n: An is the collection of 2-combinations of n and
an = n(n−1)
2 .
Introduction to the counting problem III

3. Arrangements of n people in a line. Let Pn be the set of all

arrangements of n people in a line and let pn = |Pn |. Then
I n = 0: P0 = ∅ and pn = 0;
I n = 1: P1 = {1} and pn = 1;
I n = 2: P2 = {12, 21} and pn = 2;
I n = 3: P3 = {123, 132, 213, 231, 312, 321} and pn = 6;
I For general n: Pn is the set of permutations on [n] and
pn = n!.
Introduction to the counting problem IV

4. Possible passwords for an account of 8 charts with at least

one capital letter
5. Possible passwords for an account of 8 charts with at least
one capital letter and at least one number.
The sum rule

Definition. Two sets A and B are called disjoint if A ∩ B = ∅. The

collection of sets {S1 , S2 , . . . , Sm } is called a family of mutually
disjoint sets if any two of which are disjoint. The union of mutually
disjoint sets {S1 , S2 , . . . , Sm } is denoted by S1 t S2 t · · · t Sm .

The sum rule

1. If a task can be done either in one of n1 ways or in one n2

ways, where none of the set of n1 ways is the same as any of
the set of n2 ways, then there are n1 + n2 ways to do the task.
2. The size of a union of a family of mutually disjoint finite sets
is the sum of the sizes of the sets:

|S1 t S2 t · · · Sm | = |S1 | + |S2 | + · · · + |Sm |.

Examples.

1. (Tournament problem.) Five schools are going to send their

football teams to a tournament, in which each team must
play each other team exactly once. How many matches are
required?
Answer: Let A, B, C , D, E be names of schools:
I There are 4 matches between A and other teams;
I There are 3 matches between B and other teams except for A;
I There are 2 matches between C and other team except for A
and B;
I There are 1 match between D and other teams except for
A, B, and C ;
I There is no between E and other teams except for A, B, C ,
and D.
Since matches are counted disjointly, by the sum rule there are

4 + 3 + 2 + 1 + 0 = 10

matches in total.
2. How many subsets of a set with n elements have exactly two
elements (2-element subsets)?
3. How many subsets of a set with 100 elements have at most
two elements?
4. How many subsets of a set with 100 elements have more than
two elements?
5. How many subsets of a set with n elements are there?
6. How many strings of five ASCII characters contain the
character @ at least once (note that there are 128 different
ASCII characters)?
7. How many bit strings of length 5 contain
I exactly two occurrences of 0s;
I at most two occurrences of 0s;
I at least two occurrences of 0s.
8. Prove that Euler’s phi function φ(p k ) = p k − p k−1 where p is
prime and k is a positive integer.
The product rule
The product rule

1. Assume that a procedure can be broken down into a sequence

of two tasks. If there are m ways to do the first task and for
each of these ways of doing the first task, there are n ways to
do the second task, then there are m · n ways to do the
procedure.
2. If a set S of lists/strings/words of length m has the properties
that
I There are i1 different first elements of lists in S, and
I For each j > 1 and each choice of the first j − 1 elements of a
list in S there are ij choices of elements in position j of those
lists,
then there are i1 · i2 · · · · · im lists in S.
3. Generally, let A1 , A2 , . . . , Ak be sets. Then,

|A1 × A2 × · · · × Ak | = |A1 | · |A2 | · · · · · |Ak |.

Examples and exercises:

1. The number of bit strings of length n is 2n since there are

I 2 ways (either 0 or 1) to choose the first element;
I 2 ways for the second element;
I ···
I 2 ways for the nth element.
By the product rule, there are 2| · 2 ·{z· · · · 2} = 2n bit strings of
n times
length n.
2. How many words of five uppercase letters in the English
alphabet are there such that all letters are different and the
first letter does not start with vowels.
Answer: There are 5 vowels in English alphabet a, e, i, o, u.
Hence,
I There are 26 − 5 ways for choosing the first letter;
I There are 26 − 1 ways for choosing the second letter;
I There are 26 − 1 − 1 ways for choosing the third letter;
I There are 26 − 1 − 1 − 1 ways for choosing the fourth letter;
I There are 26 − 1 − 1 − 1 − 1 ways for choosing the last letter.
By the product rule, there are 21 · 25 · 24 · 23 · 22 different
words.
3. The chairs of an auditorium are to be labeled with an
uppercase English letter followed by a positive integer not
exceeding 100. What is the largest number of chairs that can
be labeled differently?
4. How many different license plates can be made if each plate
contains a sequence of three uppercase English letters
followed by three digits (and no sequence of letters are
prohibited even if they are obscene).
5. A password for a certain computer system is supposed to be
between 4 and 8 characters long and composed of lower
and/or upper case letters. How many passwords are possible?
6. In how many ways may a ten person club select a president
and a two-person executive advisory board from among its
members (assume that the president is not on the advisory
board)?
 7. How many bijections from [n] to [n] are there?
Answer: Let f be a bijection from [n] to [n]. Then f is
determined if we know the n-tuple (f (1), f (2), . . . , f (n)).
Furthermore, f is bijective if all their images are different.
Hence, there are
I n ways to choose f (1);
I n − 1 ways to choose f (2) (since f (2) must be different from
f (1));
I ···
I n − (i − 1) ways to choose f (i), where f (i) does not coincide
to any values of f (1), f (2), . . . , f (i − 1);
I 1 way to choose f (n).
By the product rule, there are n · (n − 1) · · · · · 2 · 1 = n!
bijections from [n] to [n].
Definition
A bijection from [n] to [n] is called a permutation of [n].
 8. List all functions from [3] to [2].
Recall:
Definition
Let X and Y be sets.
I A function f from a set X to Y is an assignment of each
element of X to an element of Y .
I A function f is called one-to-one or injective if each element of
X is assigned to one and only one element of Y , i.e., if there
exists x, x 0 ∈ X such that f (x) = f (x 0 ) then x = x 0 .
I A function f is onto or surjective if for any element y ∈ Y ,
there exists an element x ∈ X such that f (x) = y .
Equivalently, f (X ) = Y .
I A function is bijective if f is injective and surjective.

Examples: On the whiteboard!

 9. List all one-to-one functions from [2] to [3].
10. List all bijections from [3] to [3].
11. How many functions from [m] to [n] are there?
12. List all one-to-one functions from the [2] to the set [4].
13. How many one-to-one functions from [3] to [5] are there.
14. How many one-to-one functions from [m] to [n] are there?
15. In how many ways can you draw a first card, second, and third
card from a deck of 52 cards?
16. In how many ways can you draw a two cards from a deck of
52 cards (the order of drawing is not important)?
17. Given n different objects put in a secret box. Take k objects
out of the box.
I How many ways to do that if the order of the taking matters
(k-permutations of n).
I How many ways to do that if the order of the taking does not
matter (k-combination of n).
The division rule
The division rule: If we can partition a set of size n into m blocks
and each block has size r , then m = nr .

Examples: (Circular permutations) How many different ways are

there to seat n people around a circular table, where two seatings
are considered the same when each person has the same left and
right neighbors?

Answer:

I There are n! ways to seat n people on a line (please verify

this).
I Each group of n ways to seat people on a line (s1 , s2 , . . . , sn ),
(s2 , s3 , . . . , s1 ), . . . , (sn , s1 , . . . , sn−1 ) gives the same way to
seat people on the circular table.

n!
By the division rule we have n = (n − 1)! way to seat n people on
a circular table.
k-permutations and k-combinations of [n]

1. (k-combinations of n) How many ways to pick k unordered

objects from a set of n objects?
Answer:
I From the product rule, we have n · (n − 1) · · · · · (n − k + 1)
ways to pick ordered objects from a set of n objects (please
clarify this!).
I Each set of k unordered objects gives exactly k! (please verify
this!) k-tuples of k ordered objects.
By the division rule, there are n·(n−1)·····(n−k+1)
k!
n!
= k!(n−k)!
ways to pick k unordered objects from a set of n objects.
2. How many bit strings of length n have exactly k occurrences
of 0s?
k-permutations and k-combinations of [n]

1. An ordered arrangement of k objects from a set of n objects is

called a k-permutation of n.
Examples: All 2-permutations of [3] are
{(1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)}.
2. An unordered selection of k elements from a set of n elements
is called a k-combination of n.
Example: All 2-combinations of [3] are {{1, 2}, {1, 3}, {2, 3}}.
k-permutations and k-combinations of [n]

Theorem
Let n, k be positive integers. Then

i) The number of k-permutations of a set with n distinct objects

is denoted by P(n, k) and
(
n!
if k ≤ n
P(n, k) = (n−k)! .
0 otherwise

ii) The number of k-combinations of a set with n distinct

elements is called binomial coefficients, denoted by kn or Cnk ,
and (
n!
if k ≤ n
C (n, k) = k!(n−k)! .
0 otherwise
k-combinations/permutations with repetition

1. How many different strings can be made from the letters in

CALIFORNIA, using all letters?
2. How many ways to take k objects with replacement from n
objects?
The bijection rule
Theorem (The bijection rule)

Two set have the same cardinality if and only if there is an

one-to-one correspondence from one set to the other.

Examples.

1. The set of bit strings of length n has the same size to the set
of subsets of [n].
2. How many number of 3 digits whose digits are pairwise
different and decrease from left to right.
3. Give a bijection that proves that
   
n n
= .
k n−k

Answer: On the white board!

Some ”familiar” identities

We explore how to apply the technique of counting in two ways to

obtain identities in mathematics

1. Cn0 + Cn1 + · · · + Cnn−1 + Cnn = 2n

2. Cn0 − Cn1 + · · · + (−1)i Cni + · · · + (−1)n Cnn = 0
2
3. nCn−1 = Cn2 (n − 2)
k−1
4. Cnk = Cn−1
k + Cn−1 (Pascal’s triangle)
5. Cnk Ckj = Cnj Cn−j
k−j

j
6. Cnk Cn−k = Cnj Cn−j
k

r = ri=0 Cmi Cnr −i Vandermonde’s identity

P
7. Cm+n
Pascal’s triangle I

Theorem (Pascal Theorem)

If n and k are integers with n > 0 and 0 < k < n, then

     
n n−1 n−1
= + .
k k −1 k
Pascal’s triangle II
Proof.
Using the sum rule as follows:

I Let S be all k-combinations of [n].

I Let S1 be all k-combinations of [n] which contains the
element {n}.
I Let S2 be all k-combinations of [n] which do not contain the
element {n}.

We have S = S1 t S2 . On the other hand (please verify),

   
n−1 n−1
|S1 | = , and |S2 | = .
k −1 k

These complete our proof.

Pascal’s triangle
...is used to generate the coefficients of monomials x k y n−k in the
expansion of (x + y )n basing on the previous coefficient row (row
of the coefficients of monomials in the expansion of (x + y )n−1 )
via Pascal’s formula.

n\k 0 1 2 3 4 5 6
0 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0
2 1 2 1 0 0 0 0
3 1 3 3 1 0 0 0
4 1 4 6 4 1 0 0
5 1 5 10 10 5 1 0
6 1 6 15 20 15 6 1

Table: Pascal’s triangle

Binomial coefficients

helps us to show the monomial coefficients in the expansion of the

nth power of two-element sum:

Theorem (Binomial Theorem)

For any integer n ≥ 0 and x, y ∈ R

n  
n
X n
(x + y ) = x i y n−i .
i
i=0

Proof.
On the white board.
Applications: Examples and exercises
1. List all 2-combinations and 2-permutations of [4].
2. The coefficient of
monomial x 12 y 13 in the expansion of
(2x − 3y )25 is 25 12
12 2 (−3)
13

3. (Trinomial coefficients) What is the coefficient of monomial

x p y q z r in the expansion of (x + y + z)n where n = p + q + r ?
4. You do not need to compute all
rows 7, 8, and 9 of Pascal’s
triangle to use it to compute 96 . Figure out which entries of
Pascal’s triangle not given in Pascal’s triangle

in the slide you
9
actually need, and compute them to get 6 .
5. Apply calculus and the binomial theorem to (1 + x)n to show
that
       
n n n n
+2 +3 ··· + n = n2n−1 .
1 2 3 n

Could you find a combinatorial explanation for that identity?

Multisets
Definition

1. A multiset is a collection of unordered elements where an

element may appear several times there.
2. The number of times an element belongs to the multiset is
called its multiplicity
3. The size of a multiset is the sum of multiplicities of all its
elements.
4. Notation: We use the double braces to distinguish a multiset
from a set.

Examples. {{A, C , C , E , S, S}} is a multiset of size 6. The

multiplicity of

I A is 1 I E is 1
I C is 2 I S is 2.
Permutations with repetition I
Definition (Permutations with repetition)

An ordered arrangement of objects on a multiset (i.e. objects may

be identical) is called a permutation with repetition.

Theorem
The number of different permutations of a multiset of size n of k
types, where the multiplicity of type 1 is n1 , of type 2 is n2 , and of
type k is nk , is
n!
.
n1 ! · n2 ! · · · · · nk !

Proof.
Using the division rule. Details are on the white board.
Permutations with repetition II
Corollary

The multinomial coefficient of x1n1 x2n2 · · · xknk in the expansion of

(x1 + x2 + · · · + xk )n is

n!
,
n1 !n2 ! · · · nk !
where n1 + n2 + · · · + nk = n.

Example. How many different strings can be made by re-ordering

letters of the word ACCESS?

Answer: The number of different strings is equal to the number of

permutations with repetition on the multiset {A, C , C , E , S, S}.
6!
This number is 1!2!1!2! .
Applications: Exercises

1. How many different strings can be made from the letters in

MISSISSIPPI, using all letters.
2. How many different strings can be made from the letters in
CASABLANCA, using all letters.
3. How many different strings can be made from the letters in
SUCCESS, using all letters.
4. Find the coefficient of the monomial x 3 y 2 z 5 in the expansion
of (2x − 3y − 2z)10
5. How many ways are there three identical red apples and two
identical golden apples may be lined up in a line?
6. How many ways are there three identical red apples, two
identical golden apples, four identical green apples may be
lined up in a line?
Combinations with repetition I

A k-combination with repetition of n-element set A is a multiset of

size k whose elements are in A. We would like to know the number
of k-combinations with repetition of an n-element set. There are
some problems equivalent with this problem as follows (please
verify):

1. How many ways are there to distribute k indistinguishable

apples to n children?
2. How many ways are there to place k indistinguishable books
onto the n shelves of a bookcase?
3. How many non-negative solutions of the equation
x1 + x2 + · · · + xn = k are there?
Combinations with repetition II
Theorem
The number of k-combinations with repetition that can be chosen
from an n-element set is
 
n+k −1 (n + k − 1)!
= .
k k!(n − 1)!

Proof.
On the white board.

Examples and exercises

1. How many solutions to the equation x1 + x2 + · · · + xn = k

are there with each xi > 0 and xi ∈ Z.
Combinations with repetition III
2. In how many ways may we pass out k indistinguishable apples
to n children if each child must get at least one apple?
3. In how many ways may n red checkers and n + 1 black
checkers be arranged in a circle?
4. How many solutions are there to the equation

x1 + x2 + x3 + x4 + x5 = 21,

where xi , i = 1, . . . , 5 are non-negative integers such that

I xi ≥ 1, for i = 1, 2, . . . , 5
I xi ≥ 2, for i = 1, 2, . . . , 5
I 0 ≤ x1 ≤ 10.
5. How many solutions are there to the inequality

x1 + x2 + x3 ≤ 11,

where x1 , x2 , x3 are non-negative integers.

Partitions of a set I

Definition

1. A partition of a set A into k blocks or parts is a collection of

k non-empty mutually disjoint sets A1 , A2 , . . . , Ak such that

A = A1 t A2 · · · t Ak .

2. The number of partitions of a set of n elements into k parts is

called the Stirling number of the second kind, denoted by
S(n, k).
3. The total number of partitions of an n-element set is called
the nth Bell number, denoted by Bn .
Partitions of a set II

Example 1. Which of the following subsets form a partition of the

set of all real numbers?

(a) The subset of positive integers, the subset of negative integers

(b) The subset of non-positive integers, the subset of
non-negative integers
Partitions of a set III

(c) The subset of rational numbers, the subset of irrational

numbers
(d) The closed intervals [n, n + 1] where n is an integer
(e) The intervals (n, n + 1] where n is an integer.

Example 2. Which of these collections of subsets are partitions of

{1, 2, 3, 4, 5, 6}:

a) {1, 2}, {2, 3, 4}, {4, 5, 6}

b) {1}, {2, 3, 6}, {4}
c) {2, 4, 6}, {1, 3, 5}
d) {1, 4, 5}, {2, 6}
Exercises:

1. All partitions of [3] into 1 parts are {{1, 2, 3}} and S(3, 1) = 1
2. All partitions of [3] into 2 parts are {{1, 2}, {3}};
{{1, 3}, {2}}; {{1}, {2, 3}}; Hence, S(3, 2) = 3.
3. All partitions of [3] into 3 parts are {{1}, {2}, {3}}. Hence,
S(3, 3) = 1.
4. The Bell number of [3] is B3 = S(3, 1) + S(3, 2) + S(3, 3) = 5.
5. List all partitions of [4] into k = 1, k = 2, k = 3, k = 4 parts.
What is the value of S(4, k)? What is the value of the nth
Bell number?
6. What are S(n, 1), S(n, n − 1), S(n, n) in general case n?
7. Construct a recursive formula for S(n, k) in general case n?
What is the value of S(n, 2)
8. Construct a bijection from the set of all partition of [n] into 2
parts to the family of non-empty subsets of [n − 1].
Partitions of a set

Theorem
Let n, k be non-negative integers. Then

1. S(n, 2) = 2n−1 − 1
2. S(n, k) = S(n − 1, k − 1) + kS(n − 1, k)

Proof.
On the white-board!

Remark: There is no closed formula for S(n, k) known for general

n and k. However, there is a formula involving a summation will
be presented in the part of the advanced counting rules.
Number of surjective functions

1. List all onto functions from [3] to [2] are ...

2. How many surjective functions from [3] to [2]?
3. How many surjective functions from [4] to [2]?
4. How many surjective functions from [m] to [n]?

Theorem
The number of surjective functions from [m] to [n] is n!S(m, n).

Proof.
On the white board!
Twelvefold ways for counting I

Problem: Place all k objects into n boxes, where there are

1. 2 possibilities for choosing kind of objects: distinguishable

(labeled) or indistinguishable (unlabeled);
2. 2 possibilities for choosing kind of boxes: distinguishable
(labeled) or indistinguishable (unlabeled);
3. 3 possibilities to place objects into boxes: arbitrary,
one-to-one (each box gets at most 1 objects), onto or
surjective (each box gets at least 1 objects).
Twelvefold ways for counting II

Denote by ≤ 1 the one-to-one placing; and by ≥ 1 the surjective

placing. We have the table of twelvefold way as follows:

Objects Boxes unrestricted ≤1 ≥1

labeled labeled nk P(n, k) n!S(k, n)
n+k−1 n k−1




unlabeled labeled
Pn k k k−n
labeled unlabeled m=1 S(k, m) Ik≤n S(k, n)
unlabeled unlabeled ? Ik≤n ?

Table: Twelvefold way

Remark: Detailed explanations for the above table will be

presented on the whiteboard!
Examples and exercises I

1. There are ? ways to place 4 distinct gifts to 3 identical boxes

2. There are ? ways to place 4 distinct gifts to 3 identical boxes
such that each box must contains at least one gift.
3. There are ? ways to place 4 identical gifts to 3 identical boxes
4. There are ? ways to place 4 identical gifts to 3 identical boxes
such that each box must contains at least 1 gift.
Examples and exercises II

5. There are ? ways to place 15 distinct gifts to 10 distinct boxes

6. There are ? ways to place 15 distinct gifts to 10 distinct boxes
such that each box contains at least 1 gift.
7. There are ? ways to place 15 distinct gifts to 10 distinct boxes
such that each box contains at most 1 gift.
8. There are ? ways to place 10 distinct gifts to 15 distinct boxes
such that each box contains at most 1 gift.
9. There are ? ways to place 100 identical gifts to 3 distinct
boxes
10. There are ? ways to place 100 identical gifts to 10 distinct
boxes such that each box contains at least 5 gifts.
Permutations I
Let S be a set of n objects.

Definition

1. A permutation of S is an ordered arrangement of all elements

of S. In the other words, a permutation of S is a bijection σ
from S to itself.
2. An element s ∈ S is called a fixed point of permutation σ if
σ(s) = s.

Example: Let S = {3}. Then f (1) = 2, f (2) = 3, f (3) = 1 is a

permutation on [3].

Exercises: Write down all possible permutations of [4] that maps 1

to 3.
Permutations II
Notations: Let S = [n] and σ be a permutation on S.

1. One-line notation: σ(1) σ(2) · · · σ(n): We write all images

of elements from 1, 2, . . . , n of σ on a line
2. Two-line notation:
 
1 2 ··· n
,
σ(1) σ(2) · · · σ(n)

where the first line represents all elements of S, the second

line represents their corresponding images.
3. Cycle notation: We will decompose [n] into disjoint cycles to
represent permutations. Each cycle is of the form
(i1 , i2 , . . . , ik ) such that i2 = σ(i1 ), i3 = σ(i2 ), ... ,
ik = σ(ik−1 ) and i1 = σ(ik ). Precisely,
Permutations III
I Starting from some element i of S, we write the sequence
(i, σ(i), σ(σ(i)), ...) of successive images under σ, until the
image returns to i, at which point one closes the parenthesis
rather than repeat i.
I We then continue by choosing a new element j ∈ S outside the
previous cycles and writing down the cycle starting at j; and so
on until all elements of S are written in cycles.

Examples. Permutation σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3,

σ(5) = 1 is represented as

I 25431 by one-line notation;

 
1 2 3 4 5
I by two-line notation;
2 5 4 3 1
I (1, 2, 5)(3, 4) by cycle notation since
σ σ σ
I 1−
→2−
→5− → 1 we get the cycle (1, 2, 5);
σ σ
I 3−
→4−
→ 3 we get the cycle (3, 4).
Permutations IV
Remark: In the cycle notation:

I The order of cycles are not important

I The order of elements in each cycle are important and it is the
order on circular
I The number of permutations of [n] with k cycles is denoted
by c(n, k). The numbers s(n, k) = (−1)n−k c(n, k) are called
the Stirling numbers of the first kind.

Question:

1. Count c(n, k)? 3. Count c(n, n − 1)?

2. Count c(n, 1)? 4. Count c(n, 2)?

5. Count the number of permutations without fixed point

(derangement number)?
Permutations V

Theorem
The number of permutations of [n] with k cycles c(n, k) satisfies
the following recurrence equation

c(n, k) = c(n − 1, k − 1) + (n − 1)c(n − 1, k).

Proof.
On the white board!
Permutations VI
Remark: Since a permutation on [n] is in fact a bijection from [n]
to [n], we can define the inverse permutation σ −1 of σ as the
inverse function of σ, and σ k = σ ◦ σ ◦ · · · ◦ σ as the composite
function of k times of σ.

Example
   
1 2 3 4 5 −1 1 2 3 4 5
1. Let σ = . Then, σ = ,
2 5 4 3 1 5 1 4 3 2
 
1 2 3 4 5
and σ 2 =
5 1 3 4 2
2. Let σ = (1, 2, 5)(3, 4) be a permutation in cycle notation.
Then σ −1 = (1, 5, 2)(3, 4) and σ 2 = (1, 5, 2)(3)(4).

Remark: In cycle notation, each cycle of σ −1 is the reflection of

each cycle of σ.
Examples and exercises
1. Write down the following permutations in the form of cycle
notation and two-line notation; find their fixed points; the
number of cycles that those permutations contain; Calculate
σ −1 (inverse function), σ 2 in each case.

I σ = 36215847 I σ = 361452
I σ = 42765813 I σ = 32156487

2. Write down in the two-line notation for each of following

permutations. Compute σ −1 and σ 2 :

I σ = (1, 3, 5)(2, 4, 6) I σ = (7, 5, 3, 1)(2, 4, 6)

I σ = (2, 3)(1, 7)(5)(6, 2) I σ = (2, 7)(6, 5, 1)(4, 3)

3. List all permutations without fixed points of [4].

4. List all permutations with 2 cycles of [4].
5. List all derangement of [3] and [4]. Prove that
Dn = (n − 1)(Dn−1 + Dn−2 ).
Pigeonhole principle

If N objects are placed into k boxes, then there is at least one box
that contains at leasts dN/ke objects.

Example.

(1) Among 100 people there are at least d100/12e = 9 people

born in the same month.
(2) How many people must be selected to guarantee that there
are at least 10 people born in the same month?
(3) How many cards must be selected from a standard deck of 52
cards to guarantee that there are at least 3 cards of the same
suit? at least 3 hearts?
Exercises I

1. In a bureau drawer there are 60 sock, all identical except for

their color: 10 pairs are red, 10 pairs are blue, 10 pair are
green. The socks are all mixed up in the drawer, and the
room is in totally dark. What is the smallest number of socks
you must remove to be sure that you have at least one
matching pair?
2. Prove that if 5 points are placed anywhere on or in a square
of side√ length 1, at least two points will be no farther apart
than 22 .
3. Prove that if 5 points are placed anywhere on or in an
equilateral triangle of side length 1, at least two points will be
no farther apart than 12 .
4. Show that among any n + 1 positive integers not exceeding 2n
there must be an integer that divides one of the other integers.
Exercises II

5. Show that if seven integers are selected from the first 10

positive integers, there must be at least two pairs of these
integers with the sum 11. Is the conclusion true if six integers
are selected rather than seven?
6. Prove that every sequence of n2 + 1 distinct real numbers
contains a subsequence of length n + 1 that is either strictly
increasing or strictly decreasing.
The Ramsey number R(m, n)
A graph of 2 colors (blue, red) is a graph so that between two
distinct vertices there is one edge, and this edge is either blue or
red.
Let m, n be positive integers greater than or equal to 2.

The Ramsey number R(m, n) is the least number of vertices of a

graph of 2 colors such that we can always find a subgraph of m
vertices whose edges are all blue, or a subgraph of n vertices whose
edges are all red.

Problem. Find R(2, 3), R(2, n), R(3, 3).