Discrete Mathematics
Chapter 7 � Advanced Counting Techniques
大葉大學 資訊工程系 黃鈴玲(Lingling Huang)
Outline
Ch9-2
7.1 Recurrence Relations(遞迴關係)
Here a0=3 and a1=5 are the initial conditions.
By the recurrence relation,
a2 = a1−a0 = 2
a3 = a2−a1 = −3
a4 = a3−a2 = −5
:
Q1: Applications ?
Q2: Are there better ways for computing the terms of� {an}?
Ch7-3
※Modeling with Recurrence Relations
We can use recurrence relations to model (describe) a
wide variety of problems.
Ch7-4
Example 3. Compound Interest (複利)
Suppose that a person deposits(存款) $10000 in�a saving account at a bank yielding 11% per year with interest compounded annually.
How much will be in the account after 30 years ?
Sol : Let Pn denote the amount in the account � after n years.
Pn=Pn−1 + 0.11×Pn−1=1.11 × Pn−1,
∴ P30=1.11 × P29=(1.11)2 × P28=…=(1.11)30 × P0� =228922.97
P0=10000
Example 5. (The Tower of Hanoi)
The rules of the puzzle allow disks to be moved one at a time from one peg to another as long as a disk is never placed on top of a smaller disk. Let Hn denote the number of moves needed to solve the Tower of Hanoi problem with n disks. �Set up a recurrence relation for the sequence {Hn}.
�Sol : Hn=2Hn-1+1, � ( n−1個 disk 先從peg 1→peg 3, 第 n 個 disk 從 peg 1→peg 2, � n−1個 disk 再從 peg 3→peg 2)
Ch7-5
peg 1
peg 2
peg 3
H4 moves
目標 : n 個disk都從 peg 1 移到 peg 2
H1=1
上例中 Hn=2Hn−1+1, H1=1
∴Hn=2Hn−1+1
=2(2Hn−2+1)+1
=22Hn−2+2+1
=22(2Hn−3+1)+2+1
=23Hn−3+(22+2+1)
:
=2n−1H1+(2n−2+2n−3+…+1)
=2n−1+2n−2+…+1
= =2n−1
Ch7-6
Example 6. Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. �How many such bit strings are there of length 5 ?
Sol :
Ch7-7
∴ an = an−1+an−2, n ≥ 3
a1=2 (string : 0,1)
a2=3 (string : 01,10,11)
∴ a3=a2+a1=5, a4=8, a5=13
1
an-1 種
an-2 種
1
0
n-2
n-1
n
1
2
n-3
…
Let an be the number of bit strings of length n that do not have two consecutive 0s.
Example 7. (Codeword enumeration)
A computer system considers a string of decimal digits a valid codeword if it contains an even number of 0 digits. Let an be the number of valid n-digit codewords. �Find a recurrence relation for an.
Sol :
Ch7-8
1~9
an−1 種
10n−1 − an−1 種
0
∴ an = 9an−1 + (10n−1−an−1)
= 8an−1 + 10n−1 , n≥2
a1 = 9
n-1
n
1
2
3
…
求an通解 :
Ch7-9
Exercise : 3,23,25,27,29,41
(41推廣成n)
7.2 Solving Recurrence Relations
Def 1. A linear homogeneous recurrence relation of
degree k (i.e., k terms) with constant coefficients
is a recurrence relation of the form
where ci∈R and ck≠0
Ch7-10
Example 1 and 2.
fn = fn−1 + fn−2
an = an−5
an = an−1 + an−22
an = nan−1
Hn = 2Hn−1 + 1
an = c1an−1+c2an−2+…+ckan−k
(True, deg=2)
(True, deg=5)
(False, not linear)
(False , not linear)
(False, not homogeneous)
Theorem 1.
Let an = c1an−1+ c2an−2 be a recurrence relation
with c1,c2∈R.
If r2 − c1r − c2= 0 (稱為characteristic equation) �has two distinct roots r1 and r2.
Then the solution of an is an = α1r1n + α2r2n ,
for n=0,1,2,…, where α1 , α2 are constants.
(α1 , α2可利用 a0, a1算出)
Ch7-11
Solving Linear Homogeneous Recurrence�Relations with Constant Coefficients
Example 3.
What’s the solution of the recurrence relation
an = an−1 + 2an−2
with a0=2 and a1=7 ?
Sol :
The characteristic equation is r2 – r − 2=0.
Its two roots are r1= 2 and r2 = −1.
Hence an=α1×2n +α2 ×(−1)n .
∵a0 = α1+α2 = 2, a1=2α1−α2=7
∴α1 = 3, α2 = −1
⇒ an = 3×2n − (−1)n.
Ch7-12
驗算：a2 = a1 + 2a0 =11� a2= 3×22 − 1 =11
r1與r2順序可交換，�結果會一樣
Example 4. Find an explicit formula for the � Fibonacci numbers.
Sol :
fn = fn−1 + fn−2 , n ≥ 2, f0=0 , f1=1.
The characteristic equation is r2 − r − 1=0.
�Its two roots are , .
So we have
Ch7-13
Thm 2.
Let an = c1an−1+c2an−2 be a recurrence relation
with c1,c2∈R.
If r2 − c1r − c2= 0 has only one root r0 .
Then the solution of an is
an = α1 ⋅ r0n + α2 ⋅ n ⋅ r0n
for n=0,1,2,…, where α1 and α2 are constants.
Ch7-14
Example 5.
What’s the solution of an= 6an−1 − 9an−2 �with a0=1 and a1=6 ?
Sol :
The root of r2 − 6r + 9 = 0 is r0 = 3.
Hence an = α1．3n +α2．n．3n .
∵a0 = α1 = 1
a1 = 3α1 + 3α2 = 6
∴ α1 = 1 and α2 = 1
⇒ an = 3n + n．3n
Ch7-15
驗算：a2 = 6a1 − 9a0 =27� a2= 32 +2 × 32 =27
Thm 3.
Let an = c1an−1 + c2an−2 + … + ckan−k be a recurrence relation with c1, c2, …, ck ∈ R.
If rk − c1rk-1 − c2rk-2 −…− ck = 0 has k distinct roots r1, r2,…, rk.
Then the solution of an is
an = α1r1n +α2r2n + …+αkrkn, for n = 0, 1, 2, …
where α1, α2,…αk are constants.
Ch7-16
Example 6 (k = 3)
Find the solution of an = 6an−1 − 11an−2 + 6an−3
with initial conditions a0=2, a1=5 and a2=15 .
Sol :
The roots of r3 − 6r2 + 11r – 6 = 0 are
r1 = 1, r2 = 2, and r3 = 3
∴an = α1 ⋅ 1n + α2 ⋅2n + α3 ⋅3n
∵a0 = α1 + α2 + α3 = 2
a1 = α1 + 2α2 + 3α3 = 5
a2 = α1 + 4α2 + 9α3 = 15
∴an = 1 − 2n + 2 ⋅ 3n
Ch7-17
α1 = 1,
α2 = −1,
α3 = 2
驗算：a3 = 6a2 − 11a1+ 6a0 =47� a3= 1 − 23 + 2 ⋅ 33 =47
Thm 4.
Let an = c1an−1 + c2an−2 + … + ckan−k be a recurrence � relation with c1, c2, …, ck ∈R.
If rk − c1rk−1 − c2rk−2 − … − ck = 0 has� t distinct roots r1, r2, …, rt � with multiplicities m1, m2, …, mt respectively, � where mi ≥ 1,∀i, and m1+ m2 +…+ mt = k,
then
Ch7-18
where αi,j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ mi−1.
Ch7-19
補充說明：
若特徵方程式的root為：1 (2重根),
−2 (3重根),� 3 (無重根)
則上述定理給出的通解為：
an= (α1,1+ α1,2 ⋅n) ⋅ 1n+ (α2,1+ α2,2 ⋅n + α2,3 ⋅n2) ⋅ (−2)n � +α3,1 ⋅ 3n
(其實變數α的下標可從1開始排起，只要不重複就好)
an= (α1+ α2 ⋅n) ⋅ 1n+ (α3+ α4 ⋅n + α5 ⋅n2) ⋅ (−2)n +α6 ⋅ 3n
Example 8. Find the solution to the recurrence relation an = −3an−1 − 3an−2 − an−3 with initial conditions�a0 = 1, a1 = −2 and a2 = −1.
Sol :
r3 + 3r2 + 3r + 1 = 0 has a single root r0 = −1 of � multiplicity three.
∴ an = (α1+α2n+α3n2) r0n = (α1+α2n+α3n2)(−1)n
∵ a0 = α1 = 1
a1 = (α1+α2+α3) ⋅ (−1) = −2
a2 = α1+2α2+4α3 = −1
∴α1 = 1, α2 = 3, α3 = −2
⇒ an = (1+3n−2n2) ⋅ (−1)n
Ch7-20
Exercise : 3,13,15,19
驗算：a3 = − 3a2 − 3a1− a0 =8� a3= (1+3⋅3−2⋅32)⋅(−1)3 =8
Ch7-21
Linear Nonhomogeneous Recurrence�Relations with Constant Coefficients
Example: an = 3an−1 + 2n
A recurrence relation of the form� an = c1an−1 + c2an−2 + … + ckan−k + F(n),
where c1, c2, …, ck are real numbers�and F(n) is a function not identically zero depending�only on n.
The recurrence relation� an = c1an−1 + c2an−2 + … + ckan−k
is called the associated homogeneous recurrence �relation.
Ch7-22
Example 9: � an = an−1 + 2n, associated h.r.r ⇒ an = an−1 � an = an−1 + an−2 + n2+1, associated h.r.r ⇒ an = an−1 + an−2
an = 3an−1 + n3n, associated h.r.r ⇒ an = 3an−1 � an = an−1 + an−3 + n!, associated h.r.r ⇒ an = an−1 + an−3
Theorem 5. If {an (p)} is a particular solution (特解) of an = c1an−1 + c2an−2 + … + ckan−k + F(n),
then every solution is of the form {an (p) + an (h)}, where {an (h)} is a solution of
an = c1an−1 + c2an−2 + … + ckan−k
Ch7-23
Proof. If {an (p)} and {bn} are both solutions of
an = c1an−1 + c2an−2 + … + ckan−k + F(n),
then an(p) = c1an−1(p) + c2an−2 (p)+ … + ckan−k(p) + F(n), �and bn = c1bn−1 + c2bn−2 + … + ckbn−k + F(n).
⇒ an(p) − bn = c1(an−1 − bn−1) + c2(an−2 − bn−2) + … � + ck(an−k − bn−k)
⇒ {an(p) − bn} is a solution of an = c1an−1 + c2an−2 + … + ckan−k
⇒ bn = an(p) + an (h)
Example 10. Find all solutions of the recurrence relation an = 3an−1 + 2n. What is the solution with a1=3?
Sol :
{associated的部分 an = 3an−1 先解}
Characteristic equation: r – 3 = 0 ⇒ r = 3 ⇒ an(h) = α ×3n.
{particular solution}
∵ F(n) = 2n ∴ Let an(p) =cn+d, where c, d ∈R.
If an(p) = cn+d is a solution to an = 3an−1 + 2n,
then cn+d = 3(c(n−1)+d)+2n =3cn − 3c + 3d +2n
⇒ 2cn−3c + 2d +2n = (2c+2)n + (2d−3c) = 0 (任何n代入都需為0)
∴2c+2 = 0, and 2d−3c = 0 ⇒ c = −1, d = −3/2
⇒ an(p) = −n − 3/2 ⇒ an = an(h) +an(p) = α ×3n−n − 3/2
If a1= α ×3−1 − 3/2 = 3 ⇒ α = 11/6
⇒ an = (11/6) ×3n− n − 3/2
Ch7-24
Example 11. Find all solutions of the recurrence relation an = 5an−1 −6an−2 + 7n.
Sol :
{associated的部分 an = 5an−1 −6an−2 先解}
Characteristic equation: r2 – 5r + 6 = 0
⇒ r1 = 3, r2 = 2
⇒ an(h) = α1 × 3n + α2 × 2n.
{particular solution}
∵ F(n) = 7n ∴ Let an(p) = c⋅7n, where c ∈R.
If an(p) = c⋅7n is a solution to an = 5an−1 −6an−2 + 7n,
then c⋅7n = 5c⋅7n−1 − 6c⋅7n−2 + 7n
⇒ 49c = 35c − 6c + 49
⇒ c = 49/20 ⇒ an(p) = (49/20) ⋅7n
⇒ an = an(h) +an(p) = α1 × 3n + α2 × 2n + (49/20) ⋅7n
Ch7-25
Exercise : 23
Ch7-26
Theorem 6.
an = c1an−1 + c2an−2 + … + ckan−k + F(n),
where F(n) = (btnt + bt−1nt−1 +…+ b1n + b0)sn.
When s is not a root of the characteristic equation�of the associated linear homogeneous recurrence relation, there is a particular solution of the form
(ptnt + pt−1nt−1 +…+ p1n + p0)sn.
When s is a root of the characteristic equation and its multiplicity is m, there is a particular solution of the form
nm(ptnt + pt−1nt−1 +…+ p1n + p0)sn.
Ch7-27
Example 12. What form does a particular solution of the linear nonhomogeneous recurrence relation� an = 6an−1 − 9an−2 + F(n) have when F(n) =3n, F(n) =n3n, F(n) =n22n , and F(n) = (n2+1)3n.
Sol :
The associated linear homogeneous recurrence relation is an = 6an−1 − 9an−2.
characteristic equation: r2 − 6r + 9 = 0 ⇒ r = 3 (2重根)
F(n) =3n, and 3 is a root ⇒ an(p) = p0n23n
F(n) =n3n, and 3 is a root ⇒ an(p) = n2(p1n+p0) 3n
F(n) =n22n , and 2 is not a root ⇒ an(p) = (p2n2+p1n+p0)2n
F(n) = (n2+1)3n , and 3 is a root � ⇒ an(p) = n2 (p2n2+p1n+p0) 3n
Exercise : 27
Example 13. Find the solutions of the recurrence relation an = an−1 + n with a1=1.
Sol :
Ch7-28
The associated linear homogeneous recurrence relation is an = an−1 .
F(n) = n = n(1)n, and 1 is a root
⇒ an(p) = n(p1n+p0)1n = p1n2+p0n
將an(p)代入an = an−1 + n � ⇒ p1n2+p0n = p1(n−1)2+p0(n−1)+n
⇒ (2p1−1)n+p0−p1=0 ⇒ p1= ½, p0 = p1= ½
⇒ an(p) = (n2+n)/2
⇒ an = an(p) + an(h) = (n2+n)/2+c
characteristic eq.: r − 1 = 0 ⇒ r = 1 ⇒ an(h) = c(1)n=c
a1=1 ⇒ c=0 ⇒ an = an(p) + an(h) = (n2+n)/2
Exercise : 29
Ch7-29
ex 40: Solve the simultaneous recurrence relations
an = 3an−1 + 2bn−1
bn = an−1 + 2bn−1 �with a0 = 1 and b0 = 2.
Sol :
an −bn= 2an−1
⇒ bn = an−2an−1
⇒ an = 3an−1 + 2bn−1 = 3an−1 + 2an−1− 4an−2
⇒ an = 5an−1 − 4an−2
⇒ r2 − 5r + 4 = 0
⇒ r = 1, 4
⇒ an = α1+α24n
a0 = α1+α2 = 1
a1 = α1+4α2 = 3a0 + 2b0 = 7
⇒ α1 = −1, α2 = 2
⇒ an= 2⋅4n−1
⇒ bn = an−2an−1= 2⋅4n−1−4n+2 = 4n+1
7.4 Generating Functions.
Def 1. The generating function for the sequence �a0, a1, a2,… of real numbers is the infinite series
G(x) = a0 + a1x +… + anxn +…
=
(若數列{an} 是finite，可視為是infinite，但後面的項都等於0)
Ch7-30
Example 1. Find the generating functions for the sequences {ak} with
(1) ak= 3
(2) ak = k+1
(3) ak = 2k
Ch7-31
(1) G(x) =
Sol :
(3) G(x) =
(2) G(x) =
Example 2. What is the generating function for the sequence 1,1,1,1,1,1 ?
Sol :
Ch7-32
(expansion，展開式)
(closed form)
a0
a1
a2
a3
a4
a5
a6及之後都=0
G(x) = = a0 + a1x + a2x2 + a3x3 +…
Exercise : 2
Example 3.
Let m∈Z+ and ,for k = 0, 1, …, m.
What is the generating function for the sequence a0, a1,…, am ?
Sol :
G(x) = a0 + a1x + a2x2 + … + amxm
= (1+x)m (by下面的二項式定理)
Ch7-33
Example 4.
The function f (x) = is the generating
function of the sequence 1, 1, 1, …, because �
= 1 + x + x2 + …= when |x| < 1.
Ch7-34
Useful Facts About Power Series
Example 5.
The function f (x) = is the generating
function of the sequence 1, a, a2, …, because �
= 1 + ax + a2x2 + …= when |ax| < 1 for a≠0.
Exercise : 5(a)(b), 11(a)
Theorem 1.
Let f(x) = and g(x) = .
Then f(x) + g(x) = .
f(x) g(x) = (a0+a1x+a2x2 +…)(b0+b1x +b2x2+…)� = (a0b0)+(a0b1+a1b0) x+(a0b2+a1b1+a2b0) x2+…� � =
Ch7-35
Example 6.
Let f (x) = . Use Example 4 to find the ��coefficients a0, a1, a2, … in the expansion f (x)= .
Ch7-36
Sol :
= 1 + x + x2 + …
=
=
∴ ak = k+1
Def 2.
Let u∈R and k∈N. Then the extended
binomial coefficient is defined by
Example 7. Find and
Sol :
Ch7-37
Example 8
When the top parameter is a negative integer, the extended binomial coefficient can be expressed in terms of an ordinary binomial coefficient.
Ch7-38
Thm 2. (The Extended Binomial Theorem)
Let x∈R with |x|<1 and let u∈R, then
Ch7-39
Example 9.
Find the generating functions for (1+x)−n and (1−x)−n where n∈Z+
Sol : By the Extended Binomial Theorem,
Ch7-40
By replacing x by –x we have
(跳過)
Exercise : 11(b)(d)
Example 10.
Find the number of solutions of e1 + e2 + e3 = 17, where e1, e2, e3 are integers with 2≤ e1 ≤ 5, 3≤ e2 ≤ 6, and 4≤ e3 ≤ 7. �
Ch7-41
Counting Problems and Generating Functions
Generating functions can be used to count the number�of combinations of various types.
Sol : The number of solutions with the indicated �constraints is the coefficient of x17 in the expansion�of
(x2 + x3 + x4 + x5)(x3 + x4 + x5 + x6)(x4 + x5 + x6 + x7)
(即相當於找 e1, e2, e3 使 xe1 xe2 xe3 = x17)
∴(e1, e2, e3)=(4, 6, 7), (5, 5, 7), (5, 6, 6) 共3種
Ch7-42
Example 11.
In how many different ways can eight identical cookies be distributed among three distinct children if each child receives at least two cookies and no more than four cookies?
Sol : The number of solutions is the coefficient of x8 in �the expansion of
(x2 + x3 + x4)3
∴(c1, c2, c3) = (2, 2, 4), (2, 3, 3), (2, 4, 2),
(3, 2, 3), (3, 3, 2), (4, 2, 2)
共6種
Exercise: 23
※Using Generating Functions to solve � Recurrence Relations.
Example 16.
Solving the recurrence relation ak = 3ak−1 for k=1,2,3,… and initial condition a0 = 2.
Sol :
另法： (by 7.2節Thm 1公式)
r – 3 = 0 ⇒ r = 3 ⇒ an = α ⋅ 3n
∵ a0 = 2 = α
∴ an = 2 ⋅ 3n
Ch7-43
Let be the
generating function for {ak}.
First note that ak = 3ak−1
⇒
⇒ G(x) − a0 = 3x ⋅ G(x)
∵a0 = 2 ⇒ G(x) − 3x ⋅ G(x) = G(x)(1−3x) = 2
Ch7-44
∴ ak = 2 ⋅ 3k
從k = 1開始，以避免ak−1變成a−1
Exercise : 5,7,11,33
Ch7-45
Example 17
Solving ak = 8ak−1 +10k−1 for k =1,2,3,… and initial condition a1 = 9. (Sec. 7.1 Example 7)
Let
be the generating function for {ak}.
Sol : Let a0 = 1 (為計算方便而假設).
Ch7-46
∴ ak = (10k + 8k)/2
Exercise: 33
7.5 Inclusion-Exclusion 排容原理
A,B,C,D : sets
Ch7-47
1
1
1
2
2
2
3
A
B
C
|A|+|B|+|C| 時
各部分被計算的次數
1
1
1
1
2
0
+|A∩B∩C|後
-|A∩B|-|A∩C|-|B∩C|後
Theorem 1.
A1, A2, …, An : sets
Ch7-48
Exercise : 17
7.6 Applications of Inclusion and Exclusion
Example 1. How many solutions does x1 + x2 + x3 = 11�have, where x1, x2, x3 are nonnegative integers with�x1 ≤ 3, x2 ≤ 4, and x3 ≤ 6?
Sol :
Ch7-49
Let a solution have property P1 if x1 ≥ 4, property P2 if �x2 ≥ 5, and property P3 if x3 ≥ 7.
N(P1’P2’P3’) = N − N(P1) − N(P2) − N(P3) + N(P1P2)� + N(P2P3) + N(P1P3) − N(P1P2P3)
Example 2. How many onto functions are there� form set A={1, 2, 3, 4, 5, 6} to set B={a, b, c} ?
Sol : f : A → B
Ch7-50
f (1)= {a, b, c}
f (2)=
︰ ︰
f (6)=
不同的填法造出不同的函數
如何使a,b,c都出現 ?
The number of onto functions
= (所有函數個數) − (a,b,c中有一個沒被對應) � + (a,b,c中二個沒被對應) − (a,b,c都沒被對應)
=
The Number of Onto Functions
Thm 1. |A| = m , |B| = n
There are
onto functions f : A → B.
Ch7-51
pf :
A = {a1, a2, …, am}. B = {b1, b2, …, bn}
f (a1)=
f (a2)=
︰ ︰
f (am)=
b1, b2, …, bn
Exercise : 8
Example 3. How many ways are there to assign five �different jobs to four different employees if every employee is assigned at least one job?
Sol :
Ch7-52
Consider the assignment of jobs as a function from the set of five jobs to the set of four employees.
The number of onto functions
Exercise : 9
Derangements (亂序)
Def. A derangement is a permutation of objects that leaves no object in its original position.
Ch7-53
Example 5. � The permutation 21453 is a derangement of 12345.
But 21543 is not a derangement of 12345.
Ch7-54
D4 = (所有4個元素的permutation數)
− (4個元素有一個在原位置的permutation數)
+ (4元素中有二個在原位置的permutation個數)
− (4個元素中有三個在原位置的permutation個數)
+ (4元素都在原位置的permutation個數)
� =
Def. � Let Dn be the number of derangements of n objects.
D3 = 2 because the derangements of 123 are 231 and 312.
D2 = 1 because the derangements of 12 are 21.
Theorem 2. (亂序公式)
Ch7-55
Exercise : 13
Proof.
Ch7-56
Exercise 17. � How many ways can the digits 0, 1, 2, 3, 4, 5, 6, 7, �8, 9 be arranged so that even digit is in its original position?
Sol :