Permutations and Cobinations_Concepts.ppt

Permutation and its concepts

1. Permutations and Combinations
Rosen 4.3

2. Permutations
•A permutation of a set of distinct objects is
an ordered arrangement these objects.
•An ordered arrangement of r elements of a
set is called an r-permutation.
•The number of r-permutations of a set with
n elements is denoted by P(n,r).
A = {1,2,3,4} 2-permutations of A include
1,2; 2,1; 1,3; 2,3; etc…

3. Counting Permutations
•Using the product rule we can find P(n,r)
= n*(n-1)*(n-2)* …*(n-r+1)
= n!/(n-r)!
How many 2-permutations are there for the
set {1,2,3,4}? P(4,2)
12
!2
!4
1*2
1*2*3*4
3*4 ===

4. Combinations
•An r-combination of elements of a set is an
unordered selection of r element from the set.
(i.e., an r-combination is simply a subset of the set
with r elements).
Let A={1,2,3,4} 3-combinations of A are
{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}(same as {3,2,4})
•The number of r-combinations of a set with n
distinct elements is denoted by C(n,r).

5. Example
Let A = {1,2,3}
2-permutations of A are: 1,2 2,1 1,3 3,1 2,3 3,2
6 total.Order is important

2-combinations of A are: {1,2}, {1,3}, {2,3}
3 total. Order is not important
If we counted the number of permutations of each 2-
combination we could figure out P(3,2)!

6. How to compute C(n,r)
•To find P(n,r), we could first find C(n,r),
then order each subset of r elements to
count the number of different orderings.
P(n,r) = C(n,r)P(r,r).
•So C(n,r) = P(n,r) / P(r,r)
)!(!
!
!)!(
)!(!
)!(
!
)!(
!
rnr
n
rrn
rrn
rr
r
rn
n
−
=
−
−
=
−
−
=

7. A club has 25 members.
•How many ways are there to choose four members
of the club to serve on an executive committee?
–Order not important
–C(25,4) = 25!/21!4! = 25*24*23*22/4*3*2*1
=25*23*22 = 12,650
•How many ways are there to choose a president,
vice president, secretary, and treasurer of the club?
–Order is important
–P(25,4) = 25!/21! = 303,600

8. The English alphabet contains 21 consonants and
5 vowels. How many strings of six lower case
letters of the English alphabet contain:
•exactly one vowel?
•exactly 2 vowels
•at least 1 vowel
•at least 2 vowels

9. The English alphabet contains 21 consonants and
5 vowels. How many strings of six lower case
letters of the English alphabet contain:
•exactly one vowel?
Note that strings can have repeated letters!
We need to choose the position for the vowel
C(6,1) = 6!/1!5! This can be done 6 ways.
Choose which vowel to use.
This can be done in 5 ways.
Each of the other 5 positions can contain any of the 21
consonants (not distinct).
There are 21
5
ways to fill the rest of the string.
6*5*21
5

10. The English alphabet contains 21 consonants and
5 vowels. How many strings of six lower case
letters of the English alphabet contain:
•exactly 2 vowels?
Choose position for the vowels.
C(6,2) = 6!/2!4! = 15
Choose the two vowels.
5 choices for each of 2 positions = 5
2
Each of the other 4 positions can contain any of 21
consonants.
21
4
15*5
2
*21
4

11. The English alphabet contains 21 consonants and
5 vowels. How many strings of six lower case
letters of the English alphabet contain:
•at least 1 vowel
Count the number of strings with no vowels
and subtract this from the total number of
strings.
26
6
- 21
6

12. The English alphabet contains 21 consonants and
5 vowels. How many strings of six lower case
letters of the English alphabet contain:
•at least 2 vowels
Compute total number of strings and subtract
number of strings with no vowels and the
number of strings with exactly 1 vowel.
26
6
- 21
6
- 6*5*21
5

13. Corollary 1: Let n and r be nonnegative
integers with r  n. Then C(n,r) = C(n,n-r)
Proof:
C(n,r) = n!/r!(n-r)!
C(n,n-r) = n!/(n-r)!(n-(n-r))! = n!/r!(n-r)!

14. Binomial Coefficient
Another notation for C(n,r) is . This
number is also called a binomial coefficient.
These numbers occur as coefficients in the
expansions of powers of binomial
expressions such as (a+b)
n
.

n
r
⎛
⎝
⎜
⎞
⎠

15. Pascal’s Identity
Let n and k be positive integers with n  k.
Then C(n+1,k) = C(n, k-1) + C(n,k).
Proof:
),1(
)!1(!
)!1(
)!1(!
)1(!
)!1(!
)1(!
)!)(1(!
!)1(
)!)(1()!1(
!
)!(!
!
)!1()!1(
!
),()1,(
knC
knk
n
knk
nn
knk
knkn
knknk
nkn
knknkk
kn
knk
n
knk
n
knCknC
+=
−+
+
=
−+
+
=
−+
+−+
=
−+−
+−
+
−+−−
=
−
+
+−−
=
+−

16. Let n be a positive integer. Then
Proof: We know from set theory that the
number of subsets in a set of size n is 2
n
.
We also know that C(n,k) is the number of
subsets of a set of size n that are of size k.
counts the number of subsets
of every size from 0
(empty set) to n. Therefore the sum must
add up to 2
n
.

C(n,k)=2
n
k=0
n
∑

C(n,k)
k=0
n
∑

17. Vandermonde’s Identity

C(m+n,r)=C(m,r−k)
k=0
r
∑ C(n,k).
Proof: Suppose there are n items in one set and m items in
a second set. Then the total number of ways to pick r
elements from the union of these sets is C(m+n,r).
Another way to pick r elements from the union is to pick k
elements from the first set and then r-k elements from the
second set, where 0  k  r. There are C(n,k) ways to
pick the k elements from the first set and C(m,r-k) ways to
pick the rest of the elements from the second set.

18. Proof: Suppose there are n items in one set and m items in a
second set. Then the total number of ways to pick r
elements from the union of these sets is C(m+n,r).
Another way to pick r elements from the union is to pick k
elements from the first set and then r-k elements from the
second set, where 0  k  r. For any k,there are C(n,k)
ways to pick the k elements from the first set and C(m,r-k)
ways to pick the rest of the elements from the second set.
By the product rule there are C(m,r-k)C(n,k) ways to pick r
elements for a particular k. For all possible values of k

C(m+n,r)=C(m,r−k)
k=0
r
∑ C(n,k).

C(m,r−k)
k=0
r
∑ C(n,k).

19. Pascal’s Triangle
0
0
⎛
⎝
⎜ ⎞
⎠
1
0
⎛
⎝
⎜
⎞
⎠
1
1
⎛
⎝
⎜
⎞
⎠
2
0
⎛
⎝
⎜
⎞
⎠
2
1
⎛
⎝
⎜
⎞
⎠
2
2
⎛
⎝
⎜
⎞
⎠
3
0
⎛
⎝
⎜ ⎞
⎠
3
1
⎛
⎝
⎜
⎞
⎠
3
2
⎛
⎝
⎜
⎞
⎠
3
3
⎛
⎝
⎜
⎞
⎠
1
1
1
1
1 2
3 3
1
1
1 4 64 1
n’th row, C
nk
=k = 0, 1, …, n

n
r
⎛
⎝
⎜
⎞
⎠

20. Binomial Theorem
Let x and y be variables and let n be a positive
integer. Then

(x+y)
n
=C(n,j)x
n−j
j=0
n
∑ y
j
=
n
0

⎛

⎝

⎜

⎞

⎠
x
n
+
n
1

⎛

⎝

⎜

⎞

⎠
x
n−1
y+
n
2

⎛

⎝

⎜

⎞

⎠
x
n−2
y
2
+...+
n
n−1

⎛

⎝

⎜

⎞

⎠
xy
n−1
+
n
n

⎛

⎝

⎜

⎞

⎠
y
n