Transcript combinatorics-04-23

CS 140 Discrete Mathematics
Combinatorics
And Review Notes
1
Combinatorics
 Permutations and r -permutations
 Properties of “n choose r”
 Pascal’s theorem
 The binomial theorem
 Review
 Inclusion/exclusion principle
2
Permutations
Permutation of a set of objects: an ordering of the objects in a row.
Example: How many permutations are there of the letters in the word
“now”?
Positions:
____
1
____
2
____
3
Step 1: Choose a letter to put in position 1.
Step 2: Choose a letter to put in position 2.
Step 3: Choose a letter to put in position 3.
n, o, w
 3 ways
 2 ways
 1 way
So the total number of ways to construct a permutation (which equals
the total number of permutations) is 3∙2∙1 = 6.
Theorem: The number of permutations of a set of n elements is n!.
3
r-Permutations
Definition: An r -permutation of a set of n elements is an “ordered
selection” of r elements taken from the set of n elements.
Example: How many 3-permutations are there of the letters in the
word “DEPAUL”?
Solution:
____
1
D, E, P, A, U, L
____
2
____
3
Step 1: Choose a letter to put in position 1.
Step 2: Choose a letter to put in position 2.
Step 3: Choose a letter to put in position 3.
 6 ways
 5 ways
 4 ways
So the total number of 3-permutations that can be formed from the 6
letters is 6∙5∙4 = 120.
4
r -Permutations
Example: How many r-permutations are there of the symbols
x1,x2,x3, . . . ,xn?
Solution:
___ ___
1
2
___
3
___ ___
r–1 r
Step 1: Choose a letter to put in position 1.
Step 2: Choose a letter to put in position 2.


x1, x2, x3, . . . , xn
 n ways
 n - 1 ways
NOTE: n – (r – 1) = n – r + 1

Step r: Choose a letter to put in position r.
 n – (r - 1) ways
So the total number of r-permutations that can be formed from
x1,x2,x3, . . . ,xn is n∙(n – 1)∙ ∙ ∙ (n – r + 1).
5
P (n,r)
Notation: P(n,r) = the number of r -permutations of a set of n
elements
Theorem: If n and r are integers and n ≥ r ≥ 0, then
P (n ,r ) = n (n – 1)(n – 2) ∙ ∙ ∙ (n – r + 1)
or, equivalently,
P (n , r ) 
n!
.
(n  r )!
6
More Review
What is  n  ?
r 
 
Definition:
 n  , “n choose r,” is the number of subsets of size
r 
 from a set with n elements.
r that can be formed
Theorem:
n 
n!

 r  r !(n  r )!
 
7
a. How many distinguishable ways can the
letters of the word MISSISSIPPI be arranged?
M, I, I, I, I, S, S, S, S, P, P
__ __ __ __ __ __ __ __ __ __ __
1 2 3 4 5 6 7 8 9 10 11
Step 1: Choose 1 position for the M
(Ex: {9})
Step 2: Choose 4 positions for the I’s
Step 3: Choose 4
Step 4: Choose 2
(Ex: {3, 4, 7, 11})
11 
  1  ways
 
 10 
  4  ways
 
6
positions for the S’s   4  ways
(Ex: {1, 2, 6, 10})
2
positions for the P’s   2  ways
(Ex: {5, 8})
So the answer is
11  10   6   2 
11!
10!
6!
2!
11!


 1   4   4   2  (1!)(10!) (4!)(6!) (4!)(2!) (2!)(0!) (1!)(4!)(4!)(2!) .
    
8
b. How many distinguishable ways can the letters of the
word MISSISSIPPI be arranged if PPI stays together and
the string begins with M?
M, PPI, I, I, I, S, S, S, S
M __ __ __ __ __ __ __ __
1 2 3 4
5 6 7
8
Step 1: Choose 1 (“long”) position for PPI
(Ex: {3})
8
  1  ways
 
Step 2: Choose 3 positions for the I’s
7
  3  ways
 
Step 3: Choose 4 positions for the S’s
4
  4  ways
 
(Ex: {1, 5, 7})
(Ex: {2, 4, 6, 8})
So the answer is
87 4 
8!
7!
4!

 1   3   4  (1!)(7!) (3!)(4!) (4!)(0!)
   

8!
8  7  6  5  4!

 280.
(1!)(3!)(4!) (3  2  1)(4!)
9
n 
Properties of  r 
 
Examples: Use the definition of n choose r to find
a.  n  = the number of subsets of size 1 that can be formed
1 
from a set with n elements
 
= n
b.  n  = the number of subsets of size n that can be formed
n 
from a set with n elements
 
= 1
c.
 n  = the number of subsets of size 0 that can be formed
0
from a set with n elements
 
= 1
10
n 
Properties of  r 
 
Example: What is
 n 
n  r 


Solution:
 n
n  r


n!
n!


 (n  r )!(n  (n  r ))! (n  r )! (n  n  r )!

n 
n!
n!



(n  r )! r ! r ! (n  r )!  r 
11
n 
Theorem about  r 
 
Theorem: Let n and r be nonnegative integers and suppose r ≤ n.
Then
n 
n!

 r  r !(n  r )!
 
Idea of Proof: Consider a set with 4 elements: {a,b,c,d}.
The 2-permutations of the set are
ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc
and there are P (4,2) of them, where P (4,2) =
4!
.
( 4  2)!
12
Proof Idea, cont.: Know P (4,2) =
4!
(4 - 2)!
But:
We can also calculate the number of 2-permutations
of the set of 4 elements as follows:
Step 1: Choose a subset of 2 elements from the set
Step 2: Order the two elements.
4
  2  ways
 
 2! ways
Thus we also have
4
P (4,2) =    2!
2
Equating the two values of P (4,2) gives
4
4!
    2!
(4  2)!  2 
4
4!

and dividing both sides by 2! gives  
.
2!(4

2)!
2
 
13
Pascal’s Formula
Let n and r be positive integers and suppose r ≤ n. Then
 n  1  n   n 
 r    r  1   r .

 
  
Proof: Next class
Example: Pascal’s Triangle
row 0  1
1 1
1 2 1
row 3  1 3
3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
etc.
n 
The entry in row n column r is   .
r 
For example,  3   1 and  3  = 3,
 
 
0
1 
 4   3  3
and so          1  3  4.
 1   0  1 
14
The Binomial Theorem
Given any real numbers a and b and any nonnegative integer n,
(a  b )n 
n n 
n k b k
a
 
k 0  k 
n 
n 
(a  b )n    a n 0b 0    a n 1b 1 
0
1
, i.e.,
n 
   a n n b n
n 
15
 n  n 0 0  n  n 1 1
n
(a  b )    a
b   a
b 
0
1
 n  n n n
  a
b
n 
Example: Prove that for all integers n ≥ 0,
n  n  n 
2n          
0 1 2
n 
 .
n 
Proof: Let n be any integer  0, and apply the binomial theorem
with a = 1 and b = 1.
n
Then
 n  n k k
1 .
(1 + 1)n =     1
k 0  k

But 1 + 1 = 2, and 1 to any power equals 1. So this equation
becomes
n
n  n  n  n 
2         
k 0  k   0   1   2 
n
n 
 
n 
16
 n  n 0 0  n  n 1 1
n
(a  b )    a
b   a
b 
0
1
Example: Find (u – 2v)4.
 n  n n n
  a
b
n 
Note: u – 2v = u + (– 2v)
Solution: Apply the binomial theorem with n = 4, a = u and b = –2v.
4
4
4
4
4
(a  b )4    a 4 0b 0    a 4 1b 1    a 4 2b 2    a 4 3b 3    a 4  4b 4
0
1 
2
3
4
 a 4  4a 3b  6a 2b 2  4ab 3  b 4 .
Substitute u for a and (–2v) for b (use parentheses!):
(u  (2v ))4  u 4  4u 3 (2v )  6u 2 (2v )2  4u (2v )3  (2v ) 4
 u 4  8u 3v  6u 2 (2)2 (v 2 )  4u (2)3 (v 3 )  (2) 4 (v 4 )
 u 4  8u 3v  6u 2 (4)(v 2 )  4u (8)(v 3 )  (16)(v 4 )
 u 4  8u 3v  24u 2v 2  32uv 3  16v 4 .
17
Cartesian Product of Sets
Definition: Given any sets A and B, we define the Cartesian
product of A and B, denoted A  B, to be the set of all ordered
pairs (a,b) where a is in A and b is in B.
In symbols:
A  B = { (a,b) | a  A and b  B }
Example: Let A = {1, 3, 5} and let B = {u, v}.
Find A  B.
Solution:
A  B = {(1,u) , (1,v),(3,u),(3,v) ,(5,u) , (5,v)}
18
Binary Relations
Def: Given any sets What do we mean by a “relation” between two
sets?
Ex: Let W be the set of all women and P be the set of all people.
For any w in W and p in P, we could say “w is related to p” if, and
only if, w is the mother of p.
Note: An element of W  P is an ordered pair (w,p) where w is a
woman and p is a person. The elements of some ordered pairs are
related; others are not.
Def: We define the relation M (for “is the mother of”) as follows: M
is the set of all (w,p) in W  P such that w is the mother of p. (So
M is a subset of W  P.)
19
Definition of Binary Relation
Definition: A binary relation R from a set A to a set B is a subset
of A  B. Given an ordered pair (a, b) in A  B, we say that a is
related to b, written a R b, if, and only if, (a, b) R. In symbols:
a R b  (a, b) R
Ex: Let A = {1, 3, 5, 7} and B = {2, 4, 6, 8}. Define a binary
relation R from A to B as follows:
a R b  a > b.
a. Is 3 R 4? No
Is 5 R 4? Yes
Is (7, 2)  R ? Yes
b. Write R as a set of ordered pairs.
R = {(3, 2), (5, 2), (5, 4), (7, 2), (7, 4), (7, 6)}
20
Example of a Binary Relation, cont.
c. Draw an “arrow diagram” to represent R, where
R = {(3, 2), (5, 2), (5, 4), (7, 2), (7, 4), (7, 6)}.
A
B
1
3
5
7
2
4
6
8
Note: An arrow diagram can be used to define a relation.
21
Definition of Function
Definition: A function f from a set A to a set B is a
binary relation from A to B that satisfies the following two
properties:
1. Every element of A is related by f to some
element of B.
2. No element of A is related by f to more than one
element of B.
22
Definition of Function
Example: Which of the relations defined by the following arrow
diagrams are functions?
u
v
w
1
2
3
no
yes
u
v
w
1
2
3
yes
u
v
w
1
2
3
u
v
w
1
2
3
no
23
The Inclusion/Exclusion Rule
Recall: The union of sets S and T, S T, is the set consisting of
all the elements of S together with all the elements of T:
S  T = {x | x  S or x  T }.
The intersection of sets S and T, S  T, is the set consisting of
all the elements that are common to both S and T:
S  T = {x | x  S and x  T }.
Example: Let A be the set of numbers from 1 to 15 that are
divisible by 2 and B be the set of numbers from 1 to 15 that are
divisible by 3. What are
N (A)? 7
N (B)? 5
N (A  B)? 2
N (A  B)? 10
How are these related?
10 = 7+ 5 – 2
24
Inclusion/Exclusion Rule
Theorem: If A, B, and C are any finite sets, then
N (A  B) = N (A) + N (B) – N (A  B)
and
N (A  B  C) = N (A) + N (B) + N (C)
– N (A  B) – N (A  C) – N (B  C) + N (A  B  C)
ABC
AB
A
B
A
B
AB
ABC
AC
AB
BC
C
25