Transcript Chapter 6 - The University of Texas at Dallas

Discrete Math For Computing II
Discrete Math For Computing II
 Main Text:
 Topics in enumeration; principle of inclusion
and exclusion, Partial orders and lattices.
Algorithmic complexity; recurrence relations,
Graph theory.
 Prerequisite: CS 2305
 "Discrete Mathematics and its Applications"
Kenneth Rosen, 5th Edition, McGraw Hill.
Contact Information
B. Prabhakaran
Department of Computer Science
University of Texas at Dallas
Mail Station EC 31, PO Box 830688
Richardson, TX 75083
Email: [email protected]
Phone: 972 883 4680; Fax: 972 883 2349
URL: http://www.utdallas.edu/~praba/cs3305.html
Office: ES 3.706
Office Hours: 1-2pm Tuesdays, Thursdays
Other times by appointments through email
Announcements: Made in class and on course web page.
TA: TBA.
Course Outline
 Selected topics in chapters 6 through 9.
 Chapter 6: Advanced Counting Techniques:
recurrence relations, principle of inclusion and
exclusion
 Chapter 7: Relations: properties of binary relations,
representing relations, equivalence relations, partial
orders
 Chapter 8: Graphs: graph representation,
isomorphism, Euler paths, shortest path algorithms,
planar graphs, graph coloring
 Chapter 9: Trees: tree applications, tree traversal,
trees and sorting, spanning trees
Course ABET Objectives









Ability to construct and solve recurrence relations
Ability to use the principle of inclusion and exclusion to
solve problems
Ability to understand binary relations and their
applications
Ability to recognize and use equivalence relations and
partial orderings
Ability to use and construct graphs and graph terminology
Ability to apply the graph theory concepts of Euler and
Hamilton circuits
Ability to identify and use planar graphs and shortest path
problems
Ability to use and construct trees and tree terminology
Ability to use and construct binary search trees
Evaluation
 1 Mid-terms: in class. 75 minutes. Mix of MCQs
(Multiple Choice Questions) & Short Questions.
 1 Final Exam: 75 minutes or 2 hours (depending on
class room availability). Mix of MCQs and Short
Questions.
 2 - 3 Quizzes: 5-6 MCQs or very short questions.
15-20 minutes each.
 Homeworks/assignments: 3 or 4 spread over the
semester.
Homeworks
 Each homework will be for 10 marks.
 Homeworks Submission:
 Submit on paper to TA/Instructor.
Grading




Home works: 5%
Quizzes: 15%
Mid-term : 40%
Final: 40%
Likely Letter Grades







Mostly Relative grading
A-, A, A+: 1.2 – 1.4 times class average
B-, B, B+: 1 – 1.2 class average
C-, C, C+: 0.8 – 1.0 class average
D-, D, D+: 0.7 – 0.8 class average
F: Below 0.6 times class average
Absolute scores will also influence above the ranges.
Schedule
 Quizzes: Dates announced in class & web, a week
ahead. Mostly before midterm and final.
 Mid-term: February 23, 2006
 Final Exam: Last day of class (April 20th) OR 11am,
May 1, 2006 (As per UTD schedule)
 Subject to minor changes
 Quiz and homework schedules will be announced in
class and course web page, giving sufficient time for
preparation.
Cheating
 Academic dishonesty will be taken
seriously.
 Cheating students will be handed over to
Head/Dean for further action.
 Remember: home works (and exams too!)
are to be done individually.
 Any kind of cheating in home
works/exams will be dealt with as per UTD
guidelines.
Chapter 6
Advanced Counting Techniques
§ 6.1: Recurrence Relations
Definition: A recurrence relation for the
sequence {an} is an equation expressing
an in terms of one or more of the previous
terms of the sequence:
a1,a2,a3,…,an-1, with n>=n0, (n0 being a
nonnegative integer).
A sequence is called a solution of a
recurrence relation if its terms satisfy the
recurrence relation.
Recurrence Example
 Consider the recurrence relation
an = 2an−1 − an−2 (n≥2).
 Which of the following are solutions?
an = 3n Yes -> 2 [3(n-1)] – 3(n-2)
an = 2n
an = 5
= 3n => an
No -> a0 = 1, a1 = 2, a2 = 4;
a2 = 2a1 – a0 = 2.2 – 1 = 3 ≠ a2
Yes -> an = 2.5 – 5 = 5 = an
Initial conditions
The initial conditions (base
conditions):
Specify the terms that precede the
first term where the recurrence
relation takes effect.
i.e., specify a0
Example Applications
 Growth of bank account
Initial Amount P0=$10,000
After n Years= Pn
Compound Interest I = 11%
Soln: Pn =Pn-1+(I/100)Pn-1=(1.11)Pn-1
Using Iteration we get, Pn =(1.11)n P0
i.e P30 =(1.11)3010,000=$228,922.97
Example Application
 Rabbits and Fibonacci Numbers
Growth of rabbit population in which
each rabbit yields 1 new one every
period starting 2 periods after its
birth.
Pn = Pn−1 + Pn−2 (Fibonacci relation)
Classic Tower of Hanoi Example
 Problem: Get all disks from peg 1 to
peg 2.
 Only move 1 disk at a time.
 Never set a larger disk on a smaller one.
Hanoi Recurrence Relation
 Let Hn = # moves for a stack of n disks.
 Optimal strategy:
 Move top n−1 disks to spare peg. (Hn−1
moves)
 Move bottom disk. (1 move)
 Move top n−1 to bottom disk. (Hn−1 moves)
 Note:
Hn = 2Hn−1 + 1
Why is Hn = 2Hn-1 + 1
 Only move 1 disk at a time.
 Never set a larger disk on a smaller one.
Solving Tower of Hanoi RR
Hn = 2 Hn−1 + 1
= 2 (2 Hn−2 + 1) + 1 = 22 Hn−2 + 2 + 1
= 22(2 Hn−3 + 1) + 2 + 1 = 23 Hn−3 +
22 + 2 + 1
…
= 2n−1 H1 + 2n−2 + … + 2 + 1
= 2n−1 + 2n−2 + … + 2 + 1 (since H1=1)
= 2n − 1
§6.2: Solving Recurrences
 Definition: A linear homogeneous
recurrence relation of degree k with
constant coefficient is a recurrence
relation of the form
an = c1an−1 + … + ckan−k,
where the ci are all real, and ck ≠ 0.
 The solution is uniquely determined if
k initial conditions a0…ak−1 are
provided
§6.2: Solving Recurrences..
 Linear?: Right hand side is sum of
multiples of previous terms.
 Homogenous?: No terms that are NOT
multiples of the ajs.
 Degree?: k-degree since previous k
terms are used.
Solving with const. Coefficients
 Basic idea: Look for solutions of the
form an = rn, where r is a constant.
 This requires the characteristic
equation:
rn = c1rn−1 + … + ckrn−k, i.e.,
rk − c1rk−1 − … − ck = 0 (Dividing both sides
by rn-k and subtracting right hand side from left).
 The solutions (characteristic roots)
can yield an explicit formula for the
sequence.
Solving ……
 Theorem1: Let c1 and c2 be real
numbers.
Suppose that r2 − c1r − c2 = 0 has
two distinct roots r1and r2. Then the
sequence {an} is a solution of the
recurrence relation an = c1an−1 +
c2an−2 if and only if an = α1r1n + α2r2n
for n≥0, where α1, α2 are constants.
Theorem 1: Proof
 2 things to prove
 Case 1: Roots are r1 & r2, i.e., {an = α1r1n +
α2r2n}  an is a solution.
 r1 & r2 are roots of r2 − c1r − c2 = 0  r12 =
c1r1 + c2; r22 = c1r2 + c2.
  c1an−1 + c2an−2 = c1(α1r1n-1 + α2r2n-1) +
c2(α1r1n-2 + α2r2n-2)
  α1r1n-2 (c1r1 + c2) + α2r2n-2 (c1r2 + c2)
  α1r1n-2 r12 + α2r2n-2 r22
  an
Theorem 1: Proof …
 2 things to prove
 Case 2: an is a solution  an = α1r1n + α2r2n for some
α1 & α2.







an is a solution  a0 = C0 = α1 + α2.
 C1 = α1r1 + α2r2
 α1 = (C1 – C0r2)/(r1- r2)
 α2 = C0 – α1 = (C0r1 - C1)/(r1- r2)
 Works only if r1≠ r2
an = α1r1n + α2r2n works for 2 initial conditions
 Since the initial conditions uniquely
determine the sequence, an = α1r1n + α2r2n
Example
 Solve the recurrence an = an−1 + 2an−2 given
the initial conditions a0 = 2, a1 = 7.
 An = rn  rn = rn-1 + 2rn-2  r2 = r +2
 Solution: Use theorem 1
 c1 = 1, c2 = 2
 Characteristic equation:
r2 − r − 2 = 0
 Solutions: r = [−(−1)±((−1)2 − 4·1·(−2))1/2]
/ 2·1
= (1±91/2)/2 = (1±3)/2, so r = 2 or r =
−1.
 So an = α1 2n + α2 (−1)n.
Example Continued…
 To find α1 and α2, solve the equations for the
initial conditions a0 and a1:
a0 = 2 = α120 + α2 (−1)0
a1 = 7 = α121 + α2 (−1)1
Simplifying, we have the pair of equations:
2 = α1 + α2
7 = 2α1 − α2
which we can solve easily by substitution:
α2 = 2−α1; 7 = 2α1 − (2−α1) = 3α1 − 2;
9 = 3α1; α1 = 3; α2 = -1.
 Final answer: an = 3·2n − (−1)n
The Case of Degenerate Roots
 Theorem2: Let c1 and c2 be real
numbers with c2 ≠ 0. Suppose that
r2 − c1r − c2 = 0 has only one root r0.
A sequence {an} is a solution of the
recurrence relation an=c1an-1 + c2an-2 if
and only if an = α1r0n + α2nr0n, for all
n≥0, for some constants α1, α2.
k-Linear Homogeneous Recurrence
Relations with Constant Coefficients
Theorem3: Let c1,c2,….ck be real numbers.
k
Suppose the C.E. r k 
c r k i  0

i 1
i
If this has k distinct roots ri, then the solutions
to the recurrence are of the form:
k
an    i ri n
i 1
k
if and only if
an   ci an i
i 1
for all n≥0, where the αi are constants.
Theorem 3: Example
Let an = 6an-1 – 11an-2 +6an-3;
a0=2,a1=5, & a2=15.
C.E.: r3 – 6r2 + 11r – 6; Roots = 1,2, & 3.
Solution: an = α1.1n + α2.2n + α3.3n
a0 = 2 = α1 + α2 + α3
a1 = 5 = α1 + α2.2 + α3.3
a2 = 15 = α1 + α2.4 + α3.9
α1 = 1; α2 = 1; α3 = 2.
an = 1 – 2n + 2.3n
Degenerate t-roots
 Theorem 4: Suppose there are t roots
r1,…,rt with multiplicities m1,…,mt. mi >= 1
for i = 1…t. Then:
 mi 1
 n
j
an     i , j n ri
i 1  j 0

t
for all n≥0, where all the α are constants.
Theorem 4: Example
 E.g., Roots of C.E. are 2, 2, 2, 5, 5, & 9.
 Solution:
(α1,0 + α1,1n + α1,2n2).2n + (α2,0 + α2,1n).5n +
α3,09n
Linear NonHomogeneous Recurrence
Relations with Constant Coefficients
 Linear NonHomogeneous RRs with
constant coefficients may (unlike
LiHoReCoCos) contain some terms
F(n) that depend only on n (and not
on any ai’s). General form:
an = c1an−1 + … + ckan−k + F(n)
The associated homogeneous recurrence relation
(associated LiHoReCoCo).
Solutions of LiNoReCoCos
If an(p) is a particular
solution to the LiNoReCoCo, then
 k

an    ci an i   F (n)
 i 1

 Theorem 5:
Then all its solutions are of the form:
an = an(p) + an(h) ,
where an(h) is a solution to the associated
k
homogeneous RR a   c a 
n


i 1
i n i

Theorem 5: Proof
 {an(p)} is a particular solution:
 an(p) = c1an-1(p) + c2an-2(p) +..+ckan-k(p) + F(n)  (1)
 Let bn be a 2nd solution:
 bn = c1bn-1 + c2bn-2 +..+ckbn-k + F(n)  (2)
 (2) – (1):
 bn – an(p) = c1(bn-1 - an-1(p)) + c2(bn-2 - an-2(p)) +… +
ck(bn-k - an-k(p))
 Hence, {bn – an(p) } is a solution of the
associated homogeneous RR, say {an(h) }.  bn
= an(p) + an(h) .
Example
 Find all solutions to an = 3an−1+2n.
Which solution has a1 = 3?
 To solve this LiNoReCoCo, solve its
associated LiHoReCoCo equation: an = 3an−1,
and its solutions are an(h) = α3n, where α is a
constant.
 By Theorem 5, the solutions to the original
problem are all of the form an = an(p) + α3n.
So, all we need to do is find one an(p) that
works.
Trial Solutions

Since F(n)=2n, i.e it is linear so a reasonable
trial solution is a linear function in n, say pn =
cn + d.
Then the equation an = 3an−1+2n becomes,
cn+d = 3(c(n−1)+d) + 2n,
(for all n)
Simplifying, we get
(−2c+2)n + (3c−2d) = 0 (collect terms)
So c = −1 and d = −3/2.
So a(p)n = −n − 3/2 is a solution.
Finding a Desired Solution
 From Theorem 5, we know that all general
solutions to our example are of the form:
an = −n − 3/2 + α3n.
Solve this for α for the given case, a1 = 3:
3 = −1 − 3/2 + α31
α = 11/6
 The answer is an = −n − 3/2 + (11/6)3n
Theorem 6
 k

 Suppose {an} satisfies LiNoRR: an    ci ani   F (n)
 i 1

 t
t i  n
And F(n)=   bt i n  s ; bt and s are real nos.
 i 0

 When s is not a root of C.E. of the associated
LiHoRR, there is a particular solution of the
form
 t
t i  n
  pt i n  s
 i 0

Theorem 6 continue…..
 When s is a root of this C.E. and its
multiplicity is m, there is a particular
solution of the form
 t
t i  n
n   pt i n  s
 i 0

m
 This factor nm ensures that the proposed
particular solution will not already be a
solution of the associated LiHoRR.
Theorem 6: Example

a = 6a
– 9a
+ F(n); F(n) = 3n
n
n-1
n-2
C.E.: r2 – 6r + 9 => (r-3)2
= 0; r = 3.
Solution: By Theorem 6, s = 3,
multiplicity m = 2. Solution is of the
form p0n23n, where p0 is polynomial
constant.
§6.3: Divide & Conquer R.R.s
 Many types of problems are solvable by
reducing a problem of size n into some
number a of independent subproblems, each
of size n/b, where a1 and b>1.
 The time complexity to solve such problems is
given by a recurrence relation:
 f(n) = a·f(n/b) + g(n)
where g(n) is the extra operations required.
This is called a divide-and-conquer recurrence relation
Divide+Conquer Examples
 Binary search: Break list into 1 subproblem (smaller list) (so a=1) of size
n/2 (so b=2).
 So f(n) = 1.f(n/2)+2 (g(n)=2 constant)
 Merge sort: Break list of length n into 2
sublists (a=2), each of size  n/2 (so b=2),
then merge them, in g(n) = n operations
 So M(n) = 2M(n/2) + n
Fast Multiplication Example
 This algorithm splits each of two 2n-bit
integers into two n bits blocks. Thus,
from multiplications of two 2n-bit
integers, it is reduced to only three
multiplications of n bit integers, plus
shifts and additions
 To find the product ab of two 2n-digitbase 2 numbers, a=(a2n-1a2n-2…a0)2 and
b=(b2n-1b2n-2…b0)2,
first, we break them in half:
a=2nA1+A0,
b=2nB1+B0,
Derivation of Fast Multiplication
ab  (2 n A1  A0 )( 2 n B1  B0 )
(Multiply out
 2 A1 B1  2 ( A1 B0  A0 B1 )  A0 B0 polynomials)
Zero
 22n A B  A B 
2n
n
1 1
0
0
2 n ( A1 B0  A0 B1  ( A1 B1  A1 B1 )  ( A0 B0  A0 B0 ))
 (2 2 n  2 n ) A1 B1  (2 n  1) A0 B0 
2 n ( A1 B0  A1 B1  A0 B0  A0 B1 )
 (2 2 n  2 n ) A1 B1  (2 n  1) A0 B0 
2 n ( A1  A0 )( B0  B1 )
(Factor last polynomial)
Three multiplications, each with n-digit numbers
Recurrence Rel. for Fast Mult.
Notice that the time complexity f(n) of
the fast multiplication algorithm
obeys the recurrence:
Time to do the needed adds &
 f(2n)=3f(n)+C(n) subtracts of n-digit and 2n-digit
i.e.,
numbers
 f(n)=3f(n/2)+C(n)
So a=3, b=2.
Theorem1
 Let f(n) = af(n/b) + c whenever n is divisible
by b, where a1, b is an integer greater than 1,
and c is a positive real number. Then
f (n)
is

O ( n lo gb a )
O (log n )
if a > 1
if a = 1
Furthermore, when n =bk, where k is a positive
integer,
lo g a
f(n) = C1 n b + C2.
where C1 = f(1) + c/(a-1) and C2 = -c/(a-1)
Theorem1: Proof
k 1
k 1
 n = bk; f(n) = akf(1) +  a c  a f (1)  c a
j 0
j 0
k
 a = 1: f(n) = f(1) + ck; Since n = b , k = logbn  f(n) =
f(1) + clogbn.
 n is a power of b or not: f(n) is O(logn), when a = 1.
 a > 1: (from Theorem 1, Section 3.2)
 f(n) = akf(1) + c(ak – 1)/(a – 1)
= ak[f(1) + c/(a – 1)] – c/(a – 1)
= C1nlogba + C2, since ak = alogbn = nlogba
  f(n) is O(nlogba)
j
k
j
MASTER Theorem
 Let f(n) = af(n/b) + cnd whenever
n=bk,
where a1, b>1, and c and d are real number,
with c positive and d nonnegative. Then
f(n) is

 o ( nlogb a )

O ( nd )
O ( nd log n )
if a<bd
if a=bd
if a>bd
Example
 We know that number of comparisons
used by the merge sort to sort a list
of n elements is less then M(n),
where M(n)=2M(n/2) + n
 From Master Theorem we find that
M(n) is O(nlogn)
§6.4 Generating Functions
 Generating functions: Used to represent
sequences efficiently by coding the terms of
a sequence as coefficients of powers of a
variable x in a formal power series
 Definition: Let S = {a0, a1, a2, a3, ...} be
an (infinite) sequence of real numbers.
Then the generating function G(x), of S is
the series

G(x)=a0+a1x+…+akxk+…=
ak xk

k 0
Example of GF
 Let S = {1, 1, 1, 1, ... }. Then
G(x) =1+ x + x2 +...+ xk +... =

k
x

k 0
if S=1,1,1,1,1,1
By Theorem 1 of Section 3.2,
(x6-1)/(x-1) = 1+ x + x2 +...+ x5
G(x) =(x6-1)/(x-1) is the generating
function of sequence 1,1,1,1,1,1
Theorems of GF
 Theorem 1:


Let f(x) =
a
k 0
x and g(x)=  bk x . Then,
k
k
k

k 0
k
(
a

b
)
x
f(x) + g(x)=  k
and
k
k 0

k

 k
f(x)g(x)=    a j bk  j  x


k 0  j 0

Example
 A expression for the generating function of the
sequence S= {1, 1, 1, 1, 1, 1, ...} is 1/(1- x)
 1/(1- x) = 1 + x + x2 + x3 +
…

k
a
x
2

 Let f(x) = 1/(1-x) ; f(x) = k 0
 What are the coefficients of ak?
 From theorem 1,
we have
(1 + x + x2 + ..) x (1 +


x + x2 + ..)   x k x  x k
k 0
k 0

  k

 k
(k  1) x k
 1/(1- x)2 =   1 x =
k
k 0
 j 0 

k 0
Permutations & Combinations
 Permutation: An ordered arrangement of objects
from a set of distinct objects.
 P(n,r): n – distinct objects; r – number of objects in
the permutation
 P(n,r) = n(n-1)(n-2)…(n-r+1)
  P(n,r) = n!/(n-r)!
 Example: Selecting first 3 prize winners from 100
different people  100 x 99 x 98 = 970,200.
 Combination: Unordered selection of r elements
from a set.
 C(n,r) = n!/[r!(n-r)!]; n is non-negative, 0 ≤ r ≤ n
 Proof: r-permutation is ordered r-combinations.
Permutations & Combinations …
 Proof: r-permutation is ordered r-combinations.:




 P(n,r) = C(n,r) x P(r,r)
 C(n,r) = P(n,r) / P(r,r)
 C(n,r) = [n!/(n-r)!]/[r!/(r-r)!]
= n!/[r!(n-r)!]
 Corollary 1: C(n,r) = C(n,n-r) if n & r are non-negative
and r ≤ n.
 Proof: C(n,n-r) = n!/[(n-r)!(n- (n-r))!]

= n!/[(n-r)!r!]
 Note: C(n,n) = C(n,0) = 1.
 Example: Choosing 5 players from 10 member team.

 C(10,5) = 10!/(5!5!) = 252.
Binomial Coefficients & Theorem
 C(n,r): denoted by n

r
 C(n,r): Binomial coefficient  these numbers occur
as co-efficients in the expansion of powers of
binomial expressions such as (a+b)n
 Binomial Theorem: x, y are variables; n – nonnegative integer.
 (x + y)n = ∑j=0 n C(n,j).xn-j.yj

= C(n,0)xn + C(n,1)xn-1y + C(n,2)xn-2y2
+….C(n,n-1)xyn-1 + C(n,n)yn
 Example: (x + y)2 = (x+y)(x+y) = xx + xy + xy +
yy = x2 + 2xy + y2
Binomial Coefficients & Theorem
 Proof: Count the number of terms of form xn-j.yj
  Choose xs from the n sums (so that the other
terms are ys)
  Coefficient of xn-jyj is C(n,n-j) = C(n,j)
 Example 1: Expansion of (x + y)4
 = ∑j=0 4 C(4,j)x4-jyj
 = C(4,0)x4 + C(4,1)x3y + C(4,2)x2y2 + C(4,3)xy3 +
C(4,4)y4
 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
 Example 2: Coeffiecient of x12y13 in (x+y)25
 = C(25,13) = 25!/(13! 12!) = 5,200,300
Binomial Theorem: Corollary 1
Corollary 1: n is non-negative  ∑k=0 n C(n,k) = 2n
Proof: 2n = (1 + 1)n = ∑k=0 n C(n,k)1k1n-k
= ∑k=0 n C(n,k)
 Basically, ∑k=0 n C(n,k) is the total number of
subsets of a set with n elements
  2n




Binomial Theorem: Corollary 2




Corollary 2: n is positive  ∑k=0 n (-1)kC(n,k) = 0
Proof: 0 = 0n = ((-1) + 1)n = ∑k=0 n C(n,k)(-1)k1n-k
= ∑k=0 n C(n,k)(-1)k
 C(n,0) + C(n,2) + C(n,4) + .. = C(n,1) + C(n,3)
+ C(n,5) + …
Binomial Theorem: Corollary 3
 Corollary 3: n is positive  ∑k=0 n 2kC(n,k) = 3n
 Proof: 3n = (1+2)n = ∑k=0 n C(n,k)(2)k1n-k
 = ∑k=0 n C(n,k)2k
Permutations With Repetitions
 Chapter 4.5
 Theorem 1: Number of r-permutations of a set of
n objects with repetitions allowed is nr.
 Theorem 2: There are C(n+r-1, r) r-combinations
from a set with n elements when repetition of
elements is allowed.
Extended Binomial Coefficients
 Definition: Let u be a real number and k a
non-negative integer. Then the extended
binomial coefficient (EBC) is:
  
u
k
u ( u 1)....( u  k 1) / k !
1
if k>0,
if k=0.
 e.g:EBC(-2,3) = (-2)(-3)(-4) / 3! = -4.
EBC(0.5,3)=(0.5)(-0.5)(-1.5) / 3! = 1/16
Example
When the top parameter (u) is negative
integer, the EBC can be expressed in terms
of ordinary binomial coefficients. Using
earlier definition:
EBC
= (-n)(-n-1)….(-n-r+1)/r!
= (-1)rn(n+1)…(n+r-1)/r!
= (-1)r(n+r-1)!/(r!*(n-1)!). Therefore,
 n 
r  n  r  1
r
    1 
   1 C (n  r  1, r )
 r 
 r 
n, r  Z 
The Extended Binomial Theorem
 Let x be a real number with |x| < 1
and let u be a real number. Then
(1+x)u =
 x

k 0
u
k
k
Example
 Find GF for (1+x)-n and (1-x)-n
By EB Theorem,
it follows that

n
k
(1+x)-n =   k x
k 0
We know that r n  (1) r C (n  r  1, r )
 

(1+x)-n
k
k
(

1
)
C
(
n

k

1
,
k
)
x
= 
k 0
Replacing x with –x we get
(1-x)-n =  C ( n  k  1, k ) x k
k 0
Counting Problems and Generating
Functions
 Generating Functions can be used to
solve a wide variety of counting
problems. In particular they can be
used to count the number of
combinations of various types.
Example
 Use GF to find the number of ways to select r
objects of n different kinds {ar} if we must
select at least one object of each kind?
 Chapter 4, theorem.
 Each of the n kinds of objects contributes the
factor (x+x2+x3…+) to the GF G(x), Hence
 G(x)= (x+x2+x3…+)n=xn(1+ x+x2+x3…+) =xn/(1-x)n
 Using EB Theorem,
we have

G(x) = xn.(1-x)-n = xn
  ( x)
r 0

G(x)=
 C (n  r  1, r ) x
r 0
nr
n
r
r

= xn  C (n  r  1, r ) x
r 0
r
Continue…
 Substituting
t = n+r, we get

t
G(x)=  C (t  1, t  n) x
t n
 Replacing t by r as the index of summation,
we get

G(x)=  C (r  1, r  n) x r
r n
Hence, there are C(r-1,r-n) ways to select
r objects of n different kinds if we must
select at least one object of each kind.
Using GF to Solve Recurrence Relations
 We can find the solution to a
recurrence relation and its initial
conditions by finding an explicit
formula for the associated generating
function.
Example
 Solve the R.R., ak=3ak-1 for k=1,2,3… and
initial condition a0=2.
ak  3ak 1
a0  2.



k 1
k 1
j 0
G( x)  a0   ak x k  a0   3ak 1 x k  a0  3x a j x j  a0  3xG ( x) 


a0
G ( x) 
 a0  3k x k   (2  3k ) x k
1  3x
k 0
k 0

k k
a
x

 Uses identity1/(1-ax) =
k 0
k
 Consequently, ak=2 . 3
§6.5 The principle of Inclusion-Exclusion
If A, B and C are finite sets then
|A  B| = |A| + |B| – |A  B|
Continue…
 If A, B and C are finite sets then
|A  B  C| = |A| + |B| + |C| - |A
- |B  C| - |A  C| - |A  B  C |
|A  B|
|A|
|B|
|A  C|
|B  C|
|C|

B|
General Inclusion-Exclusion
 Theorem 1: Let A1,…,An be finite sets.
Then | A1  A2 …… An | =
 | Ai | 
1i  n
 | Ai  Aj | 
1i  j  n
n 1
|
A

A

A
|

...

(

1
)
| A1  A2  ...  An |
 i j k
1i  j  k  n
General Theorem: Proof
 | A1  A2 …… An |: Show an element in the union is
counted only once in the right hand side.
 Let a be a member of exactly r sets (A1, …).
 a is counted C(r,1) times by 1st summation, C(r,2) by
2nd summation of the intersections, and C(r,m) times by
mth summation involving m sets Ai.
 a is counted exactly C(r,1) – C(r,2) + C(r,3) - … + (1)r+1C(r,r).
 By Corollary 2 of Section 4.4, C(r,0) - C(r,1) + C(r,2) C(r,3) - … + (-1)rC(r,r) = 0.
  C(r,0) = C(r,1) – C(r,2) + C(r,3) - … + (-1)r+1C(r,r).
  a is counted only once.
§6.6 Applications of Inclusion-Exclusion
 Alternative Form: Let Ai be the subset
containing the elements that have Property Pi.
Writing these quantities in terms of sets, we
have | Ai1  Ai 2  ...  Aik | N ( Pi1Pi 2. ..Pik )
 If the number of elements with none of the
properties P1,…,Pn is denoted by N(P1’ P2’…Pn’)
then, N(P1’ P2’…Pn’)=N- | A1  A2  ...  An |
Continue
 From the inclusionexclusion principle,
we see that
N(P1’ P2’…Pn’)=N   N | Pi | 
1i  n
 N ( P P )   N ( P P P )  ...
1i  j  n
 (1) n N ( P1 P2 ...Pn )
i
j
1i  j  k  n
i
j k
The Number of Onto Functions
 Let m and n be positive integers with (m  n).
How many ways to assign m different jobs to
n different employees if every employee is
assigned at least one job?
 Assume m = 5, n = 4, following Theorem 1
(next slide):
 45 – C(4,1).35 + C(4,2).25 – C(4,3)15 = 240
The Number of Onto Functions
 Theorem: Let m and n be positive integers with
(m  n). Then, there are
nm - C (n,1)·(n -1)m + C (n,2)·(n -2)m+…
+(-1)iC (n,i )·(n-i )m +…+ (-1)n-1C (n,n-1)·1m
onto functions from a set with m elements to a
set with n elements
Derangements
 A derangement is a permutation of objects
that leaves no object in its original
position.
 Theorem: The number of derangements of
a set with n elements is
 1 1 1 1
n 1 
Dn  n!1         1 
n! 
 1! 2! 3! 4!
Theorem Proof
 Property Pi: A permutation that fixes element i.
 Number of derangements: number of permutations
having none of the properties Pi for i = 1,2,…,n.
 Dn = N(P1’,P2’,…,Pn’) (from inclusion-exclusion)
= N -  N ( Pi )  N ( Pi Pj ) - ...
i
i j
 N: number of permutations of n elements. So, N = P(n).
 Similarly: N(Pi) = P(n-1); N(Pi,Pj) = P(n-2).
 Inserting these values in the expression for Dn, we get
the formula.