TOÁN RỜI RẠC
Bài 2: ta có bảng chân trị sau:
p
q
T
T
F
T
F
F
F
T
T
F
F
T
Từ bảng chân trị trên  ^( ^ q) = ^

F
T
F
T

^q
F
F
T
F

^
F

1
1
1
0

(p Λ q)→( p v q)
1
1
1
1

T
1
1
1
1

Câu 4
Ta có bảng giá trị
p

q

p→q

q→p

p↔q

(p → q) ˄ (q → p)


1

0

0

1

1

1

1

1

1

Theo bảng giá trị ta thấy mệnh đề (p ↔ q) và mệnh đề (p → q) ˄ (q → p) có cùng
các giá trị chân lý
Vậy (p ↔ q) = (p → q) ˄ (q → p)


Bài 6: Sử dụng bảng giá trị, chứng minh :
(p→ r)∨ (q→ r)=(p∧ q)→ r
Giải
p

q

1
0
1
0
1

1
1
1
1
0
1
0
1

1
1
0
1
1
1
0
1

0
0
0
0
0
0

j=5 k=8 => hoán vị tiếp theo 568431297

Bài 8:
A={1,2,3,4,5,6,7,8,9}.
n=9; a[]=(458796321).
Hoán vị 1: i=4; k=5 → a[]=(4587912367).


Hoán vị 2: i=8; k=9 → a[]=(458912376).
Hoán vị 3: i=7; k=9 → a[]=(458912637).
Hoán vị 4: i=8; k=9 → a[]=(458912673).
Vậy 4 hoán vị liền kề tiếp theo của hoán vị 45879321 là:
458912367
458912376
458912637
458912673
Bài 9: Cho tập A={1, 2, … , 9}. Sử dụng phương pháp sinh hội theo thứ tự từ điển,
tìm 4 hoán vị liền kề tiếp theo của 236897541.
Giải:
*Phương pháp:
Cho hoán vị ban đầu: a1a2...an.
+Bước 1: Tìm từ phải qua trái của hoán vị ban đầu phần tử ak đầu tiên thỏa mãn akak.
+Bước 3: Đổi chỗ ai và ak.
+Bước 4: Đảo ngược thứ tự các phần tử từ ak+1 đến an.
*Bài giải:
Hoán vị đầu tiên: 236897541.
+n=9.
+k=4: ak=a4=8 < ak+1=a5=9.

+Đổi chỗ a8 và a9. Sau đó đảo ngược thứ tự từ a9, ta được hoán vị kế tiếp:
139624587.
Sinh hoán vị kế tiếp:
+n=9
+k=7: a7=5
n=4,k=4 tổ hợp tiếp theo : 1,5,6,9
n=4,k=3 tổ hợp tiếp theo : 1,5,7,8
n=4,k=4 tổ hợp tiếp theo : 1,5,7,9
n=4,k=3 tổ hợp tiếp theo : 1,5,8,9

Câu 15

TH1
2 thành phần đầu là các chữ cái in hoa
3 thành phấn sau là các chữ số từ 0 → 9
Ta có

262

cách chọn 2 chữ cái để đưa vào 2 thành phần đầu


Có

103

cách chọn 3 chữ số để đưa vào 3 thành phần sau

Theo quy tắc nhân ta có

262 103

.

biển số thỏa mãn


263

cách chọn 3 chữ cái để đưa vào 3 thành phần đầu

cách chọn 3 chữ số để đưa vào 3 thành phần sau

Theo quy tắc nhân ta có

263 103

.

biển số thỏa mãn

TH4
3 thành phần đầu là các chữ cái in hoa
4 thành phấn sau là các chữ số từ 0 → 9
Ta có

263

cách chọn 2 chữ cái để đưa vào 2 thành phần đầu


Có

104

cách chọn 4 chữ số để đưa vào 4 thành phần sau

.

= 200 772 000

Bài 16:
Số cách chọn chữ:
1.
2.

Số cách chọn 3 chữ cái in hoa đầu biển số : 263
Số cách chọn 4 chữ cái in hoa đầu biển số : 264

Số cách chọn số:
1.
2.

Số cách chọn 2 chữ số kết thúc biển số : 102
Số cách chọn 3 chữ số kết thúc biển số : 103

⇒ Số cách tạo biển số xe thỏa mãn là: (102+103)(263+264)= 522007200.
Câu 17: Có bn so nguyên từ 1000 đến 5000 chia hết cho
6 hoặc 9:

+[0;1000]6 : 166 số.
+[0;5000]6 : 833 số.
=>[1000;5000] 6 :833-166=677 số.
+[0;1000]9 : 111 số.
+[0;5000]9 : 555 số.
=>[1000;5000] 9 :555-111=444 số.


*Dạng 1:
Chọn 8 số X: Có 108 cách
Chọn 3 số N: Có 53 cách
Lập được 108 x 53 số dạng 1
*Dạng 2:
Chọn 8 số X: Có 109 cách
Chọn 3 số N: Có 53 cách
Lập được 109 x 53 số dạng 2
*Dạng 3:
Chọn 8 số X: Có 1010 cách
Chọn 3 số N: Có 53 cách
Lập được 1010 x 53 số dạng 3
Lập được 53 x (108 + 109 + 1010) số điện thoại thỏa mãn.

Bài 21: Lớp học có 55 bạn nam và 35 bạn nữ. Hãy cho biết có bao nhiêu cách
chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội
văn nghệ cần ít nhất 6 thành viên và nhiều nhất 10 thành viên.
Giải
Ta có đội văn nghệ cần ít nhất là 6 nhiều nhất là 10 người và số nam phải bằng số
nữ nên ta chỉ có thể chọn 3 nam-3 nữ hoặc 4 nam-4 nữ hoặc 5 nam-5 nữ
Chọn ngẫu nhiên 3 bạn nam trong số 55 bạn: số cách chọn là 1 tổ hợp chập 3 của
55: C(55,3)
Chọn ngẫu nhiên 3 bạn nữ trong số 35 bạn: số cách chọn là 1 tổ hợp chập 3 của 35:
C(35,3)
Chọn ngẫu nhiên 4 bạn nam trong số 55 bạn: số cách chọn là 1 tổ hợp chập 4 của
55: C(55,4)


Chọn ngẫu nhiên 4 bạn nữ trong số 35 bạn: số cách chọn là 1 tổ hợp chập 4 của 35:
C(35,4)

(cách)
TH 2. Đội văn nghệ có 9 người :
Số cách chọn 6 bạn nam từ 50 nam và 3 bạn nữ từ 20 nữ tại thành đội văn
nghệ 9 người là :
(cách)
TH 3. Đội văn nghệ có 12 người :
Số cách chọn 9 bạn nam từ 50 nam và 4 bạn nữ từ 20 nữ tại thành đội văn
nghệ 12 người là :
(cách)
Vậy có cách lập thành một đội văn nghệ là :

Bài 24. Số người trong đội văn nghệ thóa măn yêu cầu bài toán là: 3,6,9 theo 3
trường hợp.
TH 1: Đội văn nghệ có 3 người:
Số cách chọn 2 bạn nam từ 60 nam và 1 bạn nữ từ 25 bạn nữ tạo thành đội văn
nghệ 3 người là:
(cách)
TH 2: Đội văn nghệ có 6 người:
Số cách chọn 4 bạn nam từ 60 nam và 2 bạn nữ từ 25 bạn nữ tạo thành đội văn
nghệ 6 người là: (cách)
TH 3: Đội văn nghệ có 9 người:
Số cách chọn 6 bạn nam từ 60 nam và 3 bạn nữ từ 25 bạn nữ tạo thành đội văn
nghệ 9 người là: (cách)
Vậy có cách lập thành một đội văn nghệ là:

+

+

(cách),

=

b)


Gọi N là số nghiệm của HPT :


Gọi N1 là số nghiệm của HPT :





Đặt
N1 cùng là nghiệm của HPT :




N1 = =
Gọi N2 là số nghiệm của HPT :
Đặt :



N2 cùng là số nghiệm của hệ




a0=2, a1=6, an=3an-1-2an-2 với n≥2
b, Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n chứa 3 số 0 liên tiếp.
c, Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n=7.
Giải:

a, Xét phương trình đặc trưng: k2-3k+2=0 (1)
Phương trình (1) có hai nghiệm phân biệt r1=1; r2=2
Do đó {an} có công thức tổng quát: an=α1.r1n+α2.r2n= α1+ α2.2n
a0=2, a1=6 nên ta có hệ :
Vậy an=
b,
Gọi an là số các xâu nhị phân có độ dài n và chưa ba số 0 liên tiếp.
Ta có:
a0=0
a1=0
a2=0
a3=1
Với n≥4 ta xét xâu nhị phân Xn có độ dài n và chứa 3 số 0 liên tiếp.


+, Nếu X[n]=1 có an-1 xâu thỏa mãn
+, Nếu X[n]=0 xét X[n-1] :
•

•

Nếu X[n-1]=0 ta xét X[n-2] :
o Nếu X[n-2]=0 có 2n-3 xâu thỏa mãn
o Nếu X[n-2]=1 có an-3 xâu thỏa mãn
Nếu X[n-1]=1 có an-2 xâu thỏa mãn

α1 α 2

,

là hằng số.


α 0 = α1 + α 2 = 2

α1 = 2α1 + α 2 (−1) = 7
α = 3
⇔ 1
α 2 = −1

Vậy nghiệm của biểu thức truy hồi là:
α n = 3.2n + 2(−1) n

. Với

n≥2

b.tìm hệ thức truy hồi để tính xác xuất xâu nhị phân có độ dài n chứa 3 số 1 liên
tiếp.

Giải
Đặt Sn là số chuỗi nhị phân độ dài n, có 3 bit 1 liên tiếp:
Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
A1 ( A là chuỗi có độ dài n -1, A chứa 3 bit 1 liên tục) , gọi số cách là S(n-1)
B10 (B là chuỗi có độ dài n - 2, B chứa 3 bít 1 liên tục), gọi số cách là S(n-2)
C100 (C là chuỗi có độ dài n - 3, C chứa 3 bít 1 liên tục, gọi số cách là S(n-3)

hoặc x[n-1]=0
Vậy ta có hệ thức truy hồi:
Với: , n ≥4.
c,
=
= 2.( +
= 2.(5+2+4)+5+8+16
= 51
Bài 36:
a,
Phương trình đặc trưng:

Phương trình tổng quát:

Theo đề bài ta có:
Vậy
b, Gọi là số xâu nhị phân kết thúc bằng số 1 và có 2 số 1 liên tiếp.

Với n≥3 ta có:
+, Nếu a[1]=0 →


+, Nếu a[1]=1
•
•

a[2]=1
a[2]=0

Vậy (n≥3)

=>X[n-1] = 1 =>2n-3.
Vậy : an = an-1 + an-2 + 2n-3 .
c)
+) Với n = 7 ta có :
a7 = a6 + a5 + 24
Mặt khác a5 = a4 + a3 + 22 = 3 + 1 + 4 = 8.
a6 = a5 + a4 + 23 = 8 + 3 + 8 = 19.
Nên a7 = a6 + a5 + 24 = 19 + 8 + 16 = 43.
Vậy n=7 ta có 43 xâu thỏa mãn yêu cầu đề bài.
Bài 38 :

a, Giải hệ thức truy hồi sau:
a0=8, a1=3, an= -an-1+2an-2 với n≥2
b, Tìm hệ thức truy hồi để tính số các xâu nhị phân độ dài n, kết thúc bằng số 0 và
có chứa 2 số 1 liên tiếp.


c, Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n=6.
Giải:
a, Xét phương trình đặc trưng: k2+k-2=0 (1)
Phương trình (1) có hai nghiệm phân biệt là r1=1; r2= -2
Do đó {an} có công thức tổng quát:
an= α1.r1n+α2.r2n= α1+ α2.(-2)n
a0=8, a1=3 nên ta có hệ :
Vậy an =
b, Gọi an là số các xâu nhị phân có độ dài n kết thúc bằng số 0 và có chứa hai số 1
liên tiếp.
Ta có:
a0=0
a1=0


Tìm hệ thức truy hồi để tính số xâu nhị phân có độ dài n,bắt đầu bằng 1 và
có 2 số 0 liên tiếp.
Tính số xâu nhị phân thỏa mãn điều kiện ở câu b với n=7.
Bài giải
Phương trình đặc trưng của hệ thức truy hồi có dạng:
có 2 nghiệm phân biệt
.

Khi đó dãy là nghiệm của hệ thức truy hồi khi và chỉ khi:

Từ giả thiết:

Vậy nghiệm của hệ thức truy hồi là
b)

•
•

Vậy

Gọi là số xâu nhị phân có độ dài n,bắt đầu bằng 1 và có 2 số 0 liên tiếp.
Ta có:
Với n , xét xâu nhị phân có độ dài n, bắt đầu bằng 1 và có 2 số 0 liên tiếp.
Nếu X[n] = 1 thì có xâu thỏa mãn.
Nếu X[n] = 0:
 Xét X[n-1] =0 thì có xâu thỏa mãn.
 Xét X[n-1] =1 thì có xâu thỏa mãn.



Xâu thỏa mãn bài toán có thể có các trường hợp:
• A1(A là xâu có độ dài n-1,A chứa 2 số 0 liên tiếp) thì số cách là .
• B11(B là xâu có độ dài n-2,B chứa 2 số 0 liên tiếp)=>số cách là
• C101(C là xâu có độ dài n-3,C có 2 số 0 liên tiếp)=> số cách là .
• D001(D là xâu có độ dài n-3 thỏa mãn bt)=> có số cách là: .
Vậy hệ thức truy hồi để tính số xâu nhị phân có độ dài n,kết thúc bằng 1 và
có 2 số 0 liên tiếp là:
với

c)