PHẦN 1: KỸ THUẬT ĐẾM
CHƯƠNG 1
TỔ HỢP
1. Giới thiệu môn học toán rời rạc
- Toán rời rạc là một lĩnh vực của toán học, nghiên cứu các đối tuợng rời rạc. Ví dụ tập các số
nguyên, tập hợp các sinh viên trong một lớp là tập hợp các đối tượng rời rạc, tập hợp các số thực
không phải là tập hợp các đối tượng rời rạc mà là tập các đối tượng liên tục.
- Toán rời rạc là môn học quan trọng trong ngành tin học vì máy tính chỉ lưu trữ và xử lý các đối
tương rời rạc nên việc tìm hiểu, nghiên cứu các tính chất của các đối tương rời rạc là rất cần thiết.
- Toán rời rạc được chia thành hai phần: phần 1 trình bày các bài toán cơ bản của lý thuyết tổ hợp
như là bài toán đếm, bài toán tồn tại, bài toán liệt kê, bài toán tối ưu; phần 2 trình bày lý thuyết đồ
thị, đồ thị là một cấu trúc rời rạc được ứng dụng để giải nhiều bài toán trong tin học.
2. Tập hợp
2.1Các bài toán về tập hợp
Một cấu hình tập hợp là một cách phân bố các phần tử của một tập hợp theo những điều kiện xác
định. Ví dụ: một chỉnh hợp lặp hoặc không lặp, một hoán vị, một tổ hợp chặp k … gọi là một cấu
hình tập hợp. Có 4 bài toán cơ bản về tập hợp:
- Bài toán đếm: Đếm số cấu hình thoả mãn các điều kiện cho trước
- Bài toán liệt kê: Liệt kê tất cả các cấu hình thoả mãn các điều kiện cho trước
- Bài toán tối ưu: Tìm cấu hình tốt nhất theo một nghĩa nào đó.
- Bài toán tồn tại: Có hay không các cấu hình thoả mãn các điều kiện cho trước
Ví dụ:
+ Bài toán đếm: Đếm số chỉnh hợp lặp chặp k của tập hợp có n phần tử: Đáp số = n
k
+ Bài toán liệt kê: Liệt kê các hoán vị của tập hợp X={1,2,3}: (1,2,3); (1,3,2); (2,1,3); (2,3,1);
(3,1,2); (3,2,1)
+ Bài toán tối ưu: Tìm tổ hợp chặp k của tập hợp X={1,2,3,…,n} sao cho tổng các phần tử của tổ
hợp này là lớn nhất: (n-k+1,..,n)
2.2Các phép toán trên tập hợp
- Phần bù của A trong X (X gọi là tập vũ trụ chứa A): là tập các phần tử thuộc X nhưng
không thuộc A , kí hiệu
Tập hợp cùng với các phép toán trên tập hợp gọi là đại số tập hợp. Các phép toán trên tập
hợp có thể chuyển sang các phép toán trên mệnh đề. Mệnh đề và các phép toán trên mệnh đề
gọi là đại số mệnh đề.
- Phủ định A: kí hiệu NOT A
⇔
A
- Tuyển của A và B: kí hiệu A OR B (A V B)
⇔
A
∪
B
- Hội của A và B: kí hiệu A AND B (A
∧
B)
⇔
A
∩
B
2.3Các tính chất của các phép toán
- Tính kết hợp
( ) ( )
( ) ( )
A B C A B C
A B C A B C
∪ ∪ = ∪ ∪
∩ ∩ = ∩ ∩
//Dạng mệnh đề
(A||B)||C=A||(B||C)
(A&&B)&&C=A&&(B&&C)
- Tính giao hoán
B. Kí hiệu
AxB={(a,b)| a
∈
A, b
∈
B}
Mở rộng:
Tích Đề Các của nhiều tập hợp
A
1
x A
2
x … x A
k
= { (a
1
, a
2
, …, a
k
) |a
i
∈
A
i
, i = 1,2,…,k }
A
k
= A x A x … x A (k lần)
a, b, c
∈
X: (a,b), (b,c)
∈
R
⇒
(a,c)
∈
R
Ghi chú: nếu (a,b)
∈
R ta nói a có quan hệ R với b và kí hiệu a R b
(a,b)
∈
R
⇔
a R b
Ví dụ:
Cho X={1,2,3,4}. Xét quan hệ “chia hết” R trên tập X; R={(a,b)| a chia hết cho b ; a,b
∈
X}.
R có là quan hệ tương đương trên X?
HD: Xét ba điều kiện
- Tính phản xạ:
∀
a
∈
X, hiển nhiên a chia hết cho a
⇒
a có quan hệ R với a
b, b=k
2
c
⇒
a = (k
1
k
2
)c = kc
⇒
a chia hết cho c
⇒
(a,c)
∈
R
⇒
R có tính bắc cầu
Do không có tính đối xứng nên R không phải là quan hệ tương đương trên X.
* Nhận xét: số quan hệ có thể xây dựng trên tập có n phần tử là
2
2
n
3.2Lớp tương đương và phân hoạch
Một quan hệ tương đương trên tập X sẽ chia X thành các tập con gọi là các lớp tương đương sao
cho hai phần tử ở cùng một lớp thì có quan hệ với nhau và hai phần tử khác lớp thì không có
quan hệ với nhau. Gọi X
1
,…,X
n
là các lớp tương đương, ta có:
∃
X
i
: a,b
∈
X
i
Ví dụ:
Nếu a và b có cùng số dư khi chia cho k, kí hiệu là a
≡
b (mod k).
Cho X={1,2,…,m}, và k<m. Xét quan hệ “đồng dư” R; R={(a,b)| a
≡
b (mod k) ; a,b
∈
X}
a) R có là quan hệ tương đương trên X?
b) Nếu R là quan hệ tương đương trên X, tìm phân hoạch S tương ứng với R
DIENLOI.NET - 3 -
HD:
a) Xét ba tính chất
- Tính phản xạ:
∀
a
∈
X, hiển nhiên a
≡
a (mod k)
⇒
(a,a)
∈
R
⇒
a
≡
b (mod k), b
≡
c (mod k)
⇒
a
≡
c (mod k)
⇒
(a,c)
∈
R
⇒
R có tính bắc cầu
Do thoả cả ba điều kiện nên R là quan hệ tương đương trên X.
c) Một số chia cho k chỉ có thể có số dư là 0, hoặc 1, …, hoặc k-1 nên các phần tử x
∈
X chia
cho k dư là i (0,..,k-1) sẽ có quan hệ đồng dư R với nhau. Gọi tập X
i
gồm các phần tử chia cho
k dư là i.
X
i
={x
Gọi N(X) là số phần tử của tập X (bản số của X)
a) X
1
∩
X
2
=
∅
⇒
N(X
1
∪
X
2
)= N(X
1
)+N(X
2
)
b) {X
1
,X
2,
…,X
n
} là một phân hoạch của tập X
⇒
N(X)=N(X
1
Nam có 10 người
⇒
N(X
3
)+N(X
4
)=10 (1)
Số vđv bắn súng = 14
⇒
N(X
2
)+N(X
4
)=14 (2)
Nữ bơi=nam bắn súng
⇒
N(X
1
)=N(X
4
) (3)
Từ (3) thay N(X4) = N(X1) vào (1), rồi cộng (1) với (2) ta được:
N(X
3
)+N(X
1
)+N(X
2
)+N(X
4
) x …x N(X
n
)
Ví dụ:
DIENLOI.NET - 4 -
Từ Hà Nội đến Huế có 3 cách đi: máy bay, ô tô, tàu hoả. Từ Huế đến Sài Gòn có 4 cách đi: máy
bay, ô tô, tàu hoả, tàu thủy. Hỏi từ Hà Nội đến Sài Gòn (qua Huế) có bao nhiêu cách đi?
HD:
X
1
: tập hợp các cách đi từ Hà Nội đến Huế
X
2
: tập hợp các cách đi từ Huế đến Sài Gòn
X: tập hợp các cách đi từ Hà Nội đến Sài Gòn (qua Huế)
Ta có:
X=X
1
x X
2
⇒
N(X)= N(X
1
) x N(X
2
)= 3x4=12
Ví dụ:
Có bao nhiêu cách đặt tên biến độ dài 10, chỉ chứa chữ cái A, B và bắt đầu bằng AAA hoặc ABA?
HD:
) + N(X
2
)= 128+128 = 256 (công thức cộng)
5. Các cấu hình tập hợp
Một cấu hình tập hợp là một cách phân bố các phần tử của một tập hợp theo những điều kiện xác
định. Các cấu hình thông dụng là chỉnh hợp, hoán vị, tổ hợp.
5.1Chỉnh hợp
a) Chỉnh hợp lặp: Một chỉnh hợp lặp chặp k của tập hợp có n phần tử là một bộ có thứ tự gồm k
phần tử lấy từ n phần tử đã cho, các thành phần có thể lặp lại.
Tập hợp gồm tất cả các chỉnh hợp lặp chặp k của tập A có n phần tử chính là tập hợp
A
k
= AxAx…xA (k lần)
⇒
Ví dụ:
Liệt kê tất cả các chỉnh hợp lặp chặp 2 của tập X={1,2,3}.
HD:
Có 3
2
=9 chỉnh hợp lặp là: (1,1),(2,2),(3,3),(1,2)(2,1),(1,3),(3,1)(2,3)(3,2)
Ví dụ:
Tính số hàm có thể xây dựng được từ tập A có k phần tử vào tập B có n phần tử
f: A B
(a
1,
…,a
k
) (b
1
k
)= n
k
.
Một tập con A của tập X có thể biểu diễn bằng một dãy nhị phân n phần tử. Vị trí thứ i = 1 nghĩa là
A có phần tử x
i
, vt(i)= 0 là không có x
i
. ví dụ: A={x
3
, x
1
} biểu diễn là (1,0,1,0,…0). Do số dãy nhị
phân chiều dài n là 2
n
⇒
số tập con là 2
n
.
b) Chỉnh hợp không lặp:
Một chỉnh hợp không lặp chặp k của tập hợp có n phần tử là một bộ có thứ tự gồm k phần tử lấy
từ n phần tử đã cho, các phần tử không được lặp lại.
Để xây dựng một chỉnh hợp không lặp, ta xây dựng dần từ thành phần đầu tiên, thành phần này
có n khả năng chọn. Mỗi thành phần tiếp theo, số khả năng chọn giảm đi 1 so với thành phần
đứng trước. Theo công thức nhân:
Số chỉnh hợp không lặp chặp k của n pt = n(n-1)(n-2)…(n-k+1)=
!
( )!
các b
i
không thể trùng
⇒
số hàm đơn ánh = số chỉnh hợp không lặp chặp k của n phần tử =
!
( )!
n
n k
−
5.2Hoán vị
Một hoán vị của tập hợp có n phần tử là một cách xếp thứ tự các phần tử đó. Một hoán vị chính là
một chỉnh hợp không lặp chặp n của n phần tử. Do đó:
Ví dụ: Liệt kê tất cả các hoán vị của tập X={1,2,3}.
HD: Có 3!=6 hoán vị là: (1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)
Ví dụ: Có 3 người xếp thành hàng ngang để chụp ảnh. Hỏi có thể bố trí bao nhiêu kiểu?
HD: Mỗi kiểu là một hoán vị
⇒
số kiểu = 3!=6
5.3Tổ hợp
a) Tổ hợp không lặp
- Một tổ hợp không lặp chặp k của tập hợp có n phần tử là một bộ không có thứ tự gồm k
thành phần lấy từ n phần tử đã cho (k<=n), các thành phần không được lặp lại.
- Một tổ hợp chặp k của tập hợp X có n phần tử chính là một tập con k phần tử của X.
DIENLOI.NET - 6 -
Số hoán vị của n pt = n(n-1)(n-2)…1= n!
- Số tổ hợp chặp k của tập A có n phần tử, kí hiệu là
k
n
C
p
} là một phân hoạch của tập X
⇒
N(X
1
)+N(X
2
)+…+N(X
p
)=N(X)
Với N(X
1
)=…=N(X
n
)=k! và N(X)=
!
( )!
n
n k−
(số chỉnh hợp không lặp chặp k của n pt)
⇒
k! x
k
n
C
=
!
( )!
n
n k−
− −
Ví dụ: số giao điểm tối đa của các đường chéo của một đa giác lồi n đỉnh (n
≥
4).
HD:
Cứ 4 đỉnh lấy từ n đỉnh của đa giác lồi (không kể thứ tự) sẽ tạo ra hai đường chéo giao nhau tại
một điểm trong đa giác. Do đó số giao điểm chính là số tổ hợp chặp 4 của n và bằng
! ! ( 1)( 2)( 3)
!( )! 4!( 4)! 24
n n n n n n
k n k n
− − −
= =
− −
+ Một số công thức tổ hợp không lặp
a)
k
n
C
=
n k
n
C
−
b)
0
n
C
=
n
+
1
n
C
x
n-1
y + …+
1n
n
C
−
xy
n-1
+
n
n
C
y
n
=
0
n
k
=
∑
k
n
C
x
=
∑
k
n
C
x
n-k
f)
0
n
C
+
1
n
C
+…+
n
n
C
=2
n
⇒
số tập con của tập n phần tử là 2
n
(đã cm ct này bằng chỉnh hợp lặp)
DIENLOI.NET - 7 -
Số tổ hợp không lặp chặp k của n pt =
k
n
C
+…+
1n
n
C
−
= n 2
n-1
g) (n+1)
0
n
C
+n
1
n
C
+…+
n
n
C
= (n+1) 2
n+1
Chứng minh: xem như bài tập
Từ công thức b) và c) ta có thể tính được tất cả các hệ số
k
n
C
bằng tam giác Pascal như sau:
0
0
2
3
C
3
3
C
vv…
dòng n (n= 0,1,2,…,) là các hệ số của (x+y)
n
b) Tổ hợp lặp
Một tổ hợp lặp chặp k của tập hợp có n phần tử là một bộ không có thứ tự gồm k thành phần
lấy từ n phần tử đã cho (k có thể lớn hơn n), các thành phần có thể lặp lại.
Ví dụ:
Một học sinh đến cửa hàng mua 4 cây bút chọn trong ba màu khác nhau là xanh, đỏ, vàng. Có
bao nhiêu cách khác nhau để chọn mua hàng?
HD:
Có các trường hợp sau:
+ 4 bút cùng màu: 4 bút cùng xanh, hoặc cùng đỏ hoặc cùng vàng => số cách = 3
+ 3 bút cùng màu: 3 bút cùng xanh, hoặc cùng đỏ hoặc cùng vàng; bút còn lại chọn một trong
hai màu còn lại => số cách= 3*2=6
+ 2 bút cùng màu, 2 bút còn lại khác màu: 2 bút cùng xanh, hoặc cùng đỏ hoặc cùng vàng; hai
bút còn lại chọn một trong hai màu còn lại => số cách= 3
+ 2 cặp bút cùng màu: số cách=C(2,3)=3
tổng cộng có = 3+6+3+3=15 cách
Nhận xét:
- Gỉa sử chọn hai xanh, một đỏ, một vàng = {x,x,d,v} nên một cách chọn chính là một tổ hợp
1
k
n k
C
+ −
2/ Tìm số nghiệm nguyên không âm của phương trình sau: x
1
+x
2
+…+x
n
= k (k là số nguyên
không âm).
Gọi k là số vật, n là số hộp, x
i
là số vật cất vào hộp i . Bài toán trở thành bài toán chia k vật
đồng chất vào n hộp phân biệt và mỗi nghiệm là một cách chia => số nghiệm=số cách chia =
1
k
n k
C
+ −
DIENLOI.NET - 9 -
Số tổ hợp lặp chặp k của tập n phần tử =
1
1
n
n k
C
−
HD:.
A={ các cách xếp A không đứng cạnh B}
⇒
tính N(A)
+X={tất cả các cách xếp };
⇒
N(X)=số hoán vị của 5 phần tử=5!
+
A
={ các cách xếp A đứng cạnh B}
A đứng cạnh B nên có thể xem dãy còn 4 phần tử và A có thể đứng bên trái B (…AB…) hoặc bên
phải B (….BA…)
⇒
N(
A
)= 4! + 4! =2.4!
DIENLOI.NET - 10 -
Số chỉnh hợp lặp chặp k của n pt = N(A
k
)= n
k
.
Số chỉnh hợp không lặp chặp k của n pt = n(n-1)(n-2)…(n-k+1)=
!
( )!
n
n k
−
Số hoán vị của n pt = n(n-1)(n-2)…1= n!
Số tổ hợp chặp k của n pt =
2
)
b) {X
1
,X
2,
…,X
n
} là một phân hoạch của tập X
⇒
N(X)=N(X
1
)+N(X
2
)+…+N(X
n
)
* Công thức nhân
a) Nếu mỗi thành phần x
i
của bộ có thứ tự (x
1
,…,x
n
) có k
i
khả năng chọn thì số bộ khác
nhau được tạo ra là tích của các khả năng này k
1
k
m
= N(X
1
∩
…
∩
X
m
)
- Số tập giao của k tập lấy từ m tập là
k
m
C
Ví dụ m=3
N(X
1
∪
X
2
∪
X
3
)= N(X
1
)+N(X
2
) +N(X
3
)
2
) +N(X
3
)
N
2
=N(X
1
∩
X
2
) +N(X
2
∩
X
3
)+N(X
3
∩
X
1
)
N
3
= N(X
1
∩
X
2
k-1
k
k
C
= 1 – [
0
k
C
-
1
k
C
+
2
k
C
-
3
k
C
- …+(-1)
k
k
k
C
] = 1-0=1
⇒
x được đếm 1 lần (đpcm).
N
m
Công thức bù:
N
là số phần tử không thuộc bất cứ X
i
nào. N: số phần tử của X
Ví dụ:
Có bao nhiêu dãy nhị phân có chiều dài bằng 10 hoặc là bắt đầu bởi 00 hoặc kết thúc bởi 11.
HD:
X
1
={các dãy bắt đầu bởi 00}; X
2
={các dãy kết thúc bởi 11}
X={các dãy bắt đầu bởi 00 hoặc kết thúc bởi 11}
X=X
1
∪
X
2
⇒
N(X)= N(X
1
)+N(X
2
) – N(X
1
∩
∪
…X
m
)= N
1
– N
2
+…+(-1)
m-1
N
m
.
Trong đó N
k
là tổng các phần tử của tất cả các giao của k tập lấy từ m tập
N
= N - N
1
+ N
2
-…+(-1)
m
N
m
Ví dụ:
Cho X={1,2,…,10000}, có bao nhiêu số không chia hết cho bất cứ số nào trong 3 số 3,4,7
HD:
X
4
) +N(X
7
) =[10000/3]+[10000/4]+[10000/7]=7261
N
2
=N(X
3
∩
X
4
) +N(X
4
∩
X
7
)+N(X
7
∩
X
3
) =[10000/12]+[10000/28]+[10000/21]=1666
N
3
= N(X
3
∩
X
4
∪
X
2
∪
…X
m
)
⇒
N(Y)=N(X) - N
1
+ N
2
-…+(-1)
n
N
n
N
k
là tổng các phần tử của tất cả các “giao của k tập” lấy từ n tập X
1,…,
X
n
.
Ta có:
Giao của k tập X
i1,
…, X
ik
1!
+
1
2!
-…+
( 1)
!
n
n
−
)
⇒
n! cách bỏ thư có N(Y) cách bỏ sao cho không lá nào đúng địa chỉ
⇒
Xác xuất để không một lá thư nào bỏ đúng địa chỉ là :(1-
1
1!
+
1
2!
-…+
( 1)
!
n
n
−
)
3. Công thức truy hồi
DIENLOI.NET - 12 -
D
n
) của tập {1,2,…,n}, a
i
là thư. Một cách bỏ thư không thư nào đúng địa chỉ
là 1 hoán vị (a
1
,…,a
n
) sao cho a
i
≠
i,
∀
i;
G/s n=5 , hoán vị (a
1
, a
2
, a
3
, a
4
, a
5
) = (2,5,1,3,4) là một cách bỏ thư không thư nào đúng địa chỉ
Phong bì 1 2 3 4 5
Thư 2 5 1 3 4
Xét a
1
n-2
+ D
n-1
cách bỏ thư không thư nào đúng địa chỉ,mà k có n-1
giá trị nên tổng số cách bỏ thư không thư nào đúng địa chỉ là:
Công thức này gọi là công thức truy hồi, có thể suy ra công thức trực tiếp như sau:
D
n
= (n-1) (D
n-2
+ D
n-1
) =(n-1)D
n-2
+ nD
n-1
– D
n-1
⇒
D
n
– nD
n-1
= - (D
n-1
- (n-1)D
n-2
);
đặt V
n
!
n
n
D
-
1
( 1)!
n
n
D
−
−
=
( 1)
!
n
n
−
Cộng các đẳng thức sau và rút gọn
1
1!
D
-
0
0!
D
=
1
1!
−
⇒
D
n
= n!(1-
1
1!
+
1
2!
-…+
( 1)
!
n
n
−
)
DIENLOI.NET - 13 -
D
n
= (n-1) (D
n-2
+ D
n-1
),
∀
n
≥
2
Với D
0
X
2
= {các tổ hợp chặp k sao cho các tổ hợp này không chứa a}
⇒
N(X
2
)=
1
k
n
C
−
⇒
X = X
1
∪
X
2
và X
1
∩
X
2
=
∅
⇒
N(X)= N(X
C
−
−
=
2
4
C
=6
X
2
= { {1,3,4}; {1,3,5}; {1,4,5}; {3,4,5} }
⇒
N(X
2
)=
1
k
n
C
−
=
3
4
C
=4
⇒
N(X)= N(X
1
) + N(X
2
=1, a
1
= 2
là công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc 2
Ta tìm a
n
có dạng a
n
= r
n
. Thay a
n
vào (1) ta được:
r
n
= c
1
r
n-1
+ c
2
r
n-2
+…+ c
k
r
n-k
, cho n=k
⇒
Xét ctth tuyến tính thuần nhất hệ số hằng bậc k=2: a
+
1
k
n
C
−
( với
0
n
C
=
n
n
C
=1 )
* Công thức truy hồi tuyến tính thuần nhất hệ số hằng bậc k :
a
n
= c
1
a
n-1
+ c
2
a
n-2
+ …+ c
k
a
n-k
r
k-2
-…- c
k
= 0 (2)
(2) gọi là phương trình đặc trưng của (1)
Cm:
(
⇐
) ta cm c
1
a
n-1
+ c
2
a
n-2
= a
n
c
1
a
n-1
+ c
2
a
n-2
= c
1
(
n
r
−
) =
1
α
2
1
n
r
−
(c
1
r
1
+ c
2
) +
2
α
2
2
n
r
−
(c
1
r
2
+ c
2
,
2
2
r
= c
1
r
2
+ c
2
)
(
⇒
) ta cm a
n
=
1
α
1
n
r
+
2
α
2
n
r
bằng qui nạp:
G/s đẳng thức đúng với n-1, n-2 ta chứng minh đúng với n. Do a
−
) + c
2
(
1
α
2
1
n
r
−
+
2
α
2
2
n
r
−
) (do giả thiết qui nạp)
⇒
1
α
2
1
n
r
−
(c
r
(Do r
1
, r
2
là nghiệm của ptđt )
Tìm
1
α
,
2
α
:
C
0
=
1
α
+
2
α
; C
1
=
1
α
r
1
+
2
≥
2; F
0
=F
1
=1. Tìm dạng trực tiếp
HD:
B1: Tìm Ptđt: r
2
- r- 1 = 0
B2: Giải ptđt: ptđt có hai nghiệm r
1
=
1 5
2
+
, r
2
=
1 5
2
−
⇒
F
n
=
1
α
1
n
r
2
=1
⇒
1
α
= (1-r
2
)/(r
1
-r
2
) =
1 5
2 5
+
;
2
α
= (1-r
1
)/(r
2
-r
1
) =
5 1
2 5
−
, r
2
. Ta có:
Ctth (3): a
n
= c
1
a
n-1
+ c
2
a
n-2
⇔
a
n
=
1
α
1
n
r
+
2
α
2
n
r
(
2
);
G/s ptđt (4) : r
2
- c
1
r- c
2
= 0 có nghiệm kép r
0
. Ta có:
Ctth (3): a
n
= c
1
a
n-1
+ c
2
a
n-2
⇔
a
n
=
1
α
0
n
- 6r + 9 = 0
B2: Giải ptđt: ptđt có nghiệm kép r
0
=3
⇒
a
n
=
1
α
3
n
+
2
α
n.3
n
.
B3: Tính các hệ số của a
n
a
0
=1, a
1
=6
⇒
1
α
=1; 3
với a
0
=2, a
1
=5, a
2
=15. Tìm ct trực tiếp
HD:
B1: Tìm Ptđt: r
3
- 6r
2
+11r - 6 = 0
B2: Giải ptđt: ptđt có ba nghiệm phân biệt r
1
=1, r
2
=2, r
3
=3.
⇒
a
n
=
1
α
1
n
+
2
a
n
= 1 -2
n
+2.3
n
.
* Nhận xét: ptđt (2) không phải lúc nào cũng giải được, ta có một phương pháp khác để tìm công
thức trực tiếp đó là dùng hàm sinh.
4. Hàm sinh
4.1 Khái niệm
Xét dãy {h
n
} vô hạn (nếu hữu hạn ta chuyển thành dãy vô hạn bằng cách xem các phần tử còn lại
bằng 0).
Ví dụ:
(1+x)
n
=
k
n
0
C
n
k
k
x
=
∑
. Ta có:
Ctth (1): a
n
= c
1
a
n-1
+ c
2
a
n-2
+ …+ c
k
a
n-k
⇔
a
n
=
1
α
1
n
r
+…+
k
α
n
k
= 1+
1
x
x−
=1+ x +
2
1
x
x
−
=1+ x + x
2
+
3
1
x
x
−
+….= 1+x+x
2
+…+x
n
+…=
0
i
i
x
∞
=
∑
=
∑
, tìm h
n
= ?
Hệ số h
n
của x
n
là số nghiệm nguyên không âm của phương trình
t
1
+ t
2
+…+t
k
= n (
i
t
x
là số hạng của thừa số thứ i
)
và số nghiệm này bằng
1
k
n k
C
+ −
⇒
1
1
m
x
x
+
−
=
−
0
m
k
k
x
=
∑
c)
1
1 x−
=
0
n
n
x
∞
=
∑
d)
1
1
1
(1 )
k
rx
−
=
n
n+k-1
0
(C )
n n
n
r x
∞
=
∑
4.3 Dùng hàm sinh để đếm số cấu hình
* Phương pháp:
B1: Xây dựng hàm sinh: mỗi giả thiết là một hàm sinh, hàm sinh cần xây dựng là tích của các hàm
sinh mà suy ra từ giả thiết
B2: Rút gọn hàm sinh đưa về dạng
0
n
n
n
h x
∞
=
∑
B3: h
với h
n
là số nghiệm nguyên không âm của phương trình
n= a+b+c ( 0
≤
a
≤
3; 0
≤
b
≤
2; 0
≤
c
≤
4)
B3: h
n
là số cách chọn.
Việc nhân nhiều đa thức không phù hợp cho việc tính tay nhưng đối với máy tính là dễ dàng, chỉ
cần viết hàm nhân hai đa thức từ đó tính được các hệ số h
n
.
Ví dụ :
Tìm số cách chọn n qủa từ 4 loại quả: táo, chuối, cam, đào (mỗi loại có số lượng ít ra là n) mà
trong đó có một số chẵn quả táo, số lượng quả chuối chia hết cho 5, không quá 4 quả cam và
không quá 1 quả đào.
HD:
B1: Xây dựng hàm sinh:
g(x)=(1+x
−
x (1+x) =
2
1
(1 )x
−
=
n
n+1
0
C
n
n
x
∞
=
∑
=
0
( 1)
n
n
n x
∞
=
+
∑
B3: suy ra số cach chọn h
n
= n+1
n
n
h x
∞
=
∑
= h
0
+ h
1
x + h
2
x
2
+h
3
x
3
+…+h
n-2
x
n-2
+h
n-1
x
n-1
+h
n
x
n
=
1 1 1
4 1 2 1 2x x
−
− +
B2: Chuyển công thức giải tích về công thức lũy thừa
g(x)=
0 0
1
(2 ) ( 2 )
4
k k
k k
x x
∞ ∞
= =
− −
∑ ∑
=
0
1
[2 ( 2) ]
4
k k k
∞
=
∑
= x+
2
2
4
n
n
n
h x
∞
−
=
∑
= x+4
2
2
n
n
n
h x
∞
+
=
∑
=x+4x
2
g(x)
Ví dụ:
n n
n
f f x
∞
− −
=
+
∑
=1+x+
1
2
n
n
n
f x
∞
−
=
∑
+
2
2
n
n
n
f x
∞
−
=
∑
1
1 x x− −
B2: Chuyển công thức giải tích về công thức lũy thừa
α
= (1-
5
)/2;
β
= (1+
5
)/2; là nghiệm của 1-x-x
2
=0
⇒
F(x)=
1
1 1x x
α β
α β α β
−
− − −
=
0 0
1
( ) ( )
k k
k k
1 1n n
α β
α β
+ +
−
−
=
1 1
1 1 5 1 5
2 2
5
n n
+ +
+ −
−
÷ ÷
÷ ÷
DIENLOI.NET - 19 -
CHƯƠNG 3
BÀI TOÁN TỒN TẠI
5. Giới thiệu bài toán
+ Bài toán tồn tại: Xét xem có hay không có một cấu hình thoả điều kiện cho trước, nếu có thì chỉ
ra cách xây dựng một cấu hình. Nhiều khi việc xây dựng cấu hình cụ thể là khó hoặc không thể,
khi đó ta chỉ cần chứng minh là có hoặc không có cấu hình.
19
a
2
+ a
3
+ a
4
≤
19
a
10
+ a
11
+ a
12
≤
19
a
11
+ a
12
+ a
1
≤
19
a
12
+ số vật=k=3, số hộp=n=2 => số cách xếp=
1
k
n k
C
+ −
=
3
4
C
= 4; và các cách xếp là: 111, 222, 112,
122.
+ số vật=k=4, số hộp=n=2 => số cách xếp=
1
k
n k
C
+ −
=
4
5
C
= 5; và các cách xếp là: 1111,1112, 1122,
1222, 2222.
* Ví dụ:
Trong số 367 người bao giờ cũng tìm được hai người có ngày sinh nhật giống nhau.
DIENLOI.NET - 20 -
Xếp vật vào hộp, nếu số vật nhiều hơn số hộp thì tồn tại một hộp chứa ít
nhất 2 vật.
HD :
cho 16, hoặc hiệu số tuổi chia hết cho 16.
*Ví dụ: bài 6/68
Cần có ít nhất bao nhiêu bộ có thứ tự gồm 2 số nguyên (a,b) sao cho chắc chắn tìm được trong
số đó hai bộ (c,d) và (e,f) sao cho c-e và d-f là các số có chữ số tận cùng bằng 0?
HD:
A
ij
= {(a,b) | a tận cùng là i, b tận cùng là j }; (i,j =0,…,9)
hai bộ (c,d) và (e,f) thuộc A
ij
sẽ có c-e và d-f là các số có chữ số tận cùng bằng 0.
+hộp: là các tập A
ij
=> số hộp=100
+vật: các bộ (a,b)
có 100 hộp => số vật ít nhất là 101 vật để có hai vật thuộc cùng một hộp
=> cần ít nhất 101 bộ (a,b) để thoả yêu cầu của đề bài.
*Vi dụ:
Xét một bảng của cơ sở dữ liệu có thể cần phải lưu trữ lên đến 500.000 mẫu tin. Hỏi có thể sử
dụng một thuộc tính với nhiều nhất 4 ký tự là các mẫu tự làm khoá chính hay không?
HD:
Theo công thức cộng và công thức nhân thì số từ khoá khác nhau là:
26
4
+ 26
3
+ 26
2
+ 26
1
6
-2=62
số vật >số hộp => có ít nhất hai tập con mà tổng của các phần tử là như nhau.
8. Nguyên lý Direchlet t ổng quát
* Ví dụ: bài 7/68
17 nhà bác học đôi một viết thư trao đổi với nhau về 3 chủ đề, mỗi cặp chỉ trao đổi với nhau về
một chủ đề. Chứng minh rằng luôn tìm được 3 nhà bác học đôi một viết thư trao đổi với nhau về
cùng một chủ đề.
HD:
Xét nhà bác học a
0
trao đổi với 16 người khác về 3 chủ đề
⇒
có 16 cuộc trao đổi về 3 chủ đề
+ hộp: chủ đề => số hộp=n=3
+ vật: cuộc trao đổi => số vật=k=16
⇒
tồn tại một hộp chứa ít nhất [k/n]=[16/3]=6 vật
⇒
có ít nhất 6 cuộc trao đổi cùng 1 chủ đề, g/s đó là chủ đề 1 và 6 cuộc trao đổi là a
0
a
1
,…,a
0
a
6
.
Nếu có một cuộc trao đổi a
i
tồn tại một hộp chứa ít nhất [k/n]=[6/2]=3 vật
⇒
có ít nhất 3 nhà bác học trao đổi cùng 1 chủ đề.
* Ví dụ :
Cần phải tung một con xúc sắc ít nhất bao nhiêu lần để có một mặt xuất hiện ít nhất
a) 2 lần
b) 3 lần
c) n lần
HD:
Gọi số lần tung xúc sắc là k.
+ hộp: mặt của xúc sắc => số hộp=n=6
+ vật: việc tung xúc sắc => số vật=k
a) [k/6]=2
⇒
k/6>1
⇒
k>6
⇒
min(k)=7
b) [k/6]=3
⇒
k/6>2
⇒
k>12
⇒
min(k)=13
c) [k/6]=n
⇒
k/6>n-1
⇒
B3: so sánh c với max: nếu c>max thì lưu c vào max
B4: in biến max.
- Nhận xét:
Với CTDL là các biến nguyên rời rạc a,b,c, chương trình sẽ không thể mở rộng trong trường
hợp tìm số lớn cho n số (n là số do người sử dụng nhập vào). Ta cần xây dựng lại ctdl và
Thuật toán như sau:
b) Tìm số lớn nhất trong n số cho trước (n <=100)
- CTDL: int a[100] (mảng tĩnh chứa tối đa 100 số nguyên), int max
- Thuật toán:
B0: nhập n, nhập dãy n số nguyên a[0], a[1],…,a[n-1]
B1: max=a[0]; i=1;
B2: Trong khi i<n lặp lại các bước sau:
B2.1: Nếu a[i]>max thì max=a[i];
B2.2: i=i+1;
B3: In max.
- Nhận xét:
Nếu nsd nhập vào nhiều hơn 100 số, chương trình sẽ chạy sai vì mảng không đủ để chứa dữ
liệu. Khi đó có hai cách giải quyết: dùng mảng động hoặc dùng danh sách liên kết (dslk sẽ giới
thiệu sau)
c) Tìm số lớn nhất trong n số cho trước (n không bị giới hạn trước)
DIENLOI.NET - 24 -
CẤU TRÚC DỮ LIỆU + GIẢI THUẬT = CHƯƠNG
TRÌNH
- CTDL: sử dụng mảng động, int max
- Thuật toán:
B0: nhập n, cấp phát mảng động n phần tử, nhập dãy n số nguyên a[0], a[1],…,a[n-1]
B1,B2, B3: giống câu b.
cap phat mang dong n phan tu: int *a=new int(n);
- Nhận xét: Thuật toán khi sử dụng ctdl là mảng động với Thuật toán khi sử dụng ctdl là
mảng tĩnh xem như không đổi nhưng nếu dùng ctdl là danh sách liên kết thì Thuật toán sẽ
xuất max
a[i]>max
Đ
S
max=a[i];
DIENLOI.NET - 25 -
nhập/xuất
Biểu thức
Chương trình con
Bắt đầu/ kết thúc
Copyright: Tài liệu đại học ©