ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
------------------
Lê Quang Việt
MỘT SỐ PHƯƠNG PHÁP VÀ KỸ
THUẬT ĐẾM CƠ BẢN TRONG LÝ
THUYẾT TỔ HỢP VÀ ÁP DỤNG
LUẬN VĂN THẠC SỸ TOÁN HỌC
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số: 60460113
Người hướng dẫn khoa học
GS. TSKH. NGUYỄN VĂN MẬU
THÁI NGUYÊN - NĂM 2013
1
.
2
Mục lục
Mở đầu
4
Lời cảm ơn
5
1 Các quy tắc đếm cơ bản trong tổ hợp
1.1 Một số kiến thức cơ bản của tổ hợp . . . . . . . . .
1.1.1 Tập hợp . . . . . . . . . . . . . . . . . . . .
1.1.2 Công thức tính lực lượng của tập hợp . . . .
1.1.3 Công thức bao hàm và loại trừ . . . . . . . .
1.2 Hai quy tắc cơ bản của phép đếm . . . . . . . . . .
1.2.1 Quy tắc cộng . . . . . . . . . . . . . . . . .
1.2.2 Quy tắc nhân . . . . . . . . . . . . . . . .
1.3 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Hoán vị không lặp . . . . . . . . . . . . . . .
1.3.2 Hoán vị có lặp . . . . . . . . . . . . . . . . .
1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Chỉnh hợp không lặp . . . . . . . . . . . . .
1.4.2 Chỉnh hợp có lặp . . . . . . . . . . . . . . .
1.5 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.1 Tổ hợp không lặp . . . . . . . . . . . . . . .
1.5.2 Tổ hợp có lặp . . . . . . . . . . . . . . . . .
1.5.3 Khai triển lũy thừa của nhị thức . . . . . . .
1.5.4 Tính số phần tử của một tập hợp các tập hợp
2 Các phương pháp đếm sử dụng hàm sinh
2.1 Chuỗi lũy thừa hình thức . . . . . . . . . . . .
2.1.1 Định nghĩa . . . . . . . . . . . . . . .
2.1.2 Các phép toán trên CN . . . . . . . . .
2.2 Phương pháp đếm bằng hàm sinh thông thường
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
6
7
9
10
10
12
14
14
16
17
17
19
20
20
21
22
23
.
.
.
.
27
27
27
28
30
3
2.3
2.2.1 Định nghĩa hàm sinh thường . . . . . . . . . . . .
2.2.2 Sử dụng hàm sinh thường để giải các bài toán đếm
Phương pháp đếm bằng hàm sinh mũ . . . . . . . . . . . .
2.3.1 Định nghĩa hàm sinh mũ . . . . . . . . . . . . . .
2.3.2 Sử dụng hàm sinh mũ để giải các bài toán đếm . .
3 Phương pháp đếm bằng các công thức nghịch đảo
3.1 Công thức nghịch đảo các đồng nhất thức tổ hợp . .
3.2 Công thức nghịch đảo nhị thức . . . . . . . . . . . .
3.3 Công thức nghịch đảo Stirling . . . . . . . . . . . .
3.4 Công thức sàng . . . . . . . . . . . . . . . . . . . .
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . .
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
30
33
37
37
37
.
.
.
.
.
.
40
43
44
45
46
50
51
4
Mở đầu
Trong lý thuyết tổ hợp các phép đếm luôn chiếm một phần vô cùng quan
trọng và có ứng dụng vô cùng đa dạng. Các phương pháp đếm số lượng phần
tử của một tập hợp đóng vai trò quan trọng trong một số môn khoa học,
đặc biệt là Tin học và Toán học ứng dụng. Đối với chương trình toán phổ
thông các phương pháp đếm luôn là chuyên đề quan trọng và hết sức cần
thiết trong việc bồi dưỡng học sinh giỏi Toán ở bậc học phổ thông, đồng thời
các ứng dụng đa dạng của nó cũng luôn đem lại sự hấp dẫn đối với nhiều đối
tượng học sinh và giáo viên khi nghiên cứu vấn đề này.
Mục tiêu của Luận văn " Một số phương pháp và kĩ thuật đếm cơ bản trong
lý thuyết tổ hợp và áp dụng" nhằm trình bày một số phép đếm cơ bản nhất
và những ứng dụng của nó nhằm tạo ra được một đề tài phù hợp cho việc
giảng dạy, bồi dưỡng học sinh trung học phổ thông.
Luận văn bao gồm phần mở đầu, kết luận, tài liệu tham khảo và 3 Chương.
Chương 1 trình bày tóm tắt một số kiến thức cơ bản của tổ hợp và các quy
tắc cơ bản của phép đếm. Trong chương này cũng trình bày một số ví dụ và
các bài toán về tính lực lượng tập hợp, bài toán về khai triển nhị thức.
Chương 2 trình bày các phương pháp đếm bằng hàm sinh thông thường và
phương pháp đếm bằng hàm sinh mũ cùng các ví dụ áp dụng.
Chương 3 trình bày các phương pháp đếm bằng các công thức nghịch đảo
các đồng nhất thức tổ hợp bao gồm công thức nghịch đảo nhị thức, nghịch
đảo Stirling, công thức sàng và các ví dụ áp dụng.
5
Lời cảm ơn
Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và
giúp đỡ tận tình của GS.TSKH Nguyễn Văn Mậu. Tôi xin được bày tỏ lòng
biết ơn sâu sắc nhất đến thầy.
Trong quá trình học tập tôi cũng đã nhận được sự quan tâm giúp đỡ và sự
giảng dạy nhiệt tình của các Thầy, các Cô dạy lớp cao học toán K5B (2011
-2013), tôi xin được bày tỏ lòng biết ơn đến các Thầy, các Cô.
Tôi xin chân thành cảm ơn các Thầy cô trong BGH trường ĐH Khoa Học ĐH Thái Nguyên đã tạo kiều kiện thuận lợi cho tôi trong suốt thời gian học
cao học.
Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu sót.
Tác giả mong nhận được những ý kiến đóng góp của quý thầy, cô và bạn đọc
để luận văn được hoàn thiện hơn.
Xin trân trọng cảm ơn !
Hải phòng, tháng 5 năm 2013
Người viết Luận văn
Lê Quang Việt
6
Chương 1
Các quy tắc đếm cơ bản trong tổ hợp
1.1
1.1.1
Một số kiến thức cơ bản của tổ hợp
Tập hợp
Khái niệm về tập hợp
Tập hợp ( còn gọi là tập ) là một khái niệm cơ bản của toán học, không định
nghĩa. Giả sử cho tập hợp A. Để chỉ a là một phần tử của tập hợp A, ta viết
a ∈ A ( đọc là a thuộc A). Để chỉ a không là một phần tử của tập hợp A, ta
viết a ∈
/ A ( đọc là a không thuộc A).
Một tập hợp được coi là xác định nếu ta có thể chỉ ra được tất cả các phần
tử của nó.
Các cách xác định tập hợp:
Tập hợp được xác định bằng một trong hai cách sau:
- Liệt kê chúng(thường dùng để biểu thị các tập hữu hạn). Ví dụ: Tập các
số tự nhiên chẵn nhỏ hơn 10
A = {0, 2, 4, 6, 8}
- Chỉ ra tính chất đặc trưng của chúng. Ví dụ:
B = x ∈ Z|x2 − 3x + 2 ≥ 0
Tập con.
- Tất cả các phần tử của tập B đều thuộc tập A thì ta nói tập B là tập con
của tập A và viết B ⊆ A
- Trường hợp B ⊆ A và B 6= A thì B được gọi là tập con không tầm thường
7
(hay tập con thực sự) của tập A và viết B ⊂ A
Tập rỗng
-Tập hợp rỗng (hay tập hợp trống) là tập hợp không chứa một phần tử nào
và thường được ký hiệu là ∅
- Quy ước tập rỗng là con của bất kỳ tập nào
Hợp, giao, hiệu và phần bù của hai tập hợp.
Giả sử có các tập A, B.
- Tập hợp gồm các phần tử hoặc thuộc tập A hoặc thuộc tập B được gọi là
hợp của tập A và tập B và ký hiệu là A ∪ B hoặc A ∨ B.
- Tập hợp gồm các phần tử thuộc đồng thời cả tập A và tập B được gọi là
giao của tập A và tập B ký hiệu là A ∩ B hoặc A ∧ B .
- Tập hợp gồm các phần tử thuộc tập A mà không thuộc tập B được gọi là
hiệu của tập A và tập B. Kí hiệu A\B
- Trường hợp tập B là tập con của tập A. Hiệu của tập A và tập B được
gọi là tập phần bù (hay phần bù) của tập B (đối với tập A) và ký hiệu hoặc
bằng hoặc bằng CA (B) hoặc bằng C (B).
Lực lượng của tập hợp.
Giả sử có tập A. Số phần tử trong tập A được gọi là lực lượng của tập A,
ký hiệu là |A|.
1.1.2
Công thức tính lực lượng của tập hợp
Với hai tập hợp V1 , V2 ta có
|V1 ∪ V2 | = |V1 | + |V2 | − |V1 ∩ V2 | .
(1.1)
Với ba tập hợp V1 , V2 , V3 ta có
|V1 ∪ V2 ∪ V3 | = |V1 | + |V2 | + |V3 | − |V1 ∩ V2 | − |V2 ∩ V3 | − |V1 ∩ V3 | +
|V1 ∩ V2 ∩ V3 | .
(1.2)
Tổng quát với các tập tùy ý V1 , V2 , . . . , Vn bằng phương pháp quy nạp
8
theo n (n ≥ 2) ta có công thức
n
n
[
X
X
| Vi ∩ Vj | + | V1 ∩ V2 ∩ V 3 | + | V1 ∩ V2 ∩ V4 |
| Vi | −
Vi =
i=1
i=1
i6=j
+ · · · + | Vn−2 ∩ Vn−1 ∩ Vn | − · · · − (−1)n | V1 ∩ V2 ∩ · · · ∩ Vn |.
(1.3)
Ví dụ 1.1 (Tài liệu tập huấn phát triển chuyên môn giáo viên trường THPT
Chuyên - 2012). Chứng minh rằng bản báo cách thành tích cuối năm của
một lớp sau đây là sai.
"Lớp có 45 học sinh, trong đó có 30 em nam. Lớp có 30 em đạt loại giỏi và
trong số này có 16 nam. Lớp có 25 em chơi thể thao và trong số này có 18 em
nam và 17 em đạt loại giỏi. Có 15 em nam vừa đạt loại giỏi và chơi thể thao."
Giải.
Kí hiệu : V = 45 là tổng số học sinh của lớp
V1 số học sinh nam
V2 số học sinh đạt giỏi
V3 số học sinh chơi thể thao.
Khi đó
|V1 ∪ V2 ∪ V3 | = |V1 |+|V2 |+|V3 |−|V1 ∩ V2 |−|V2 ∩ V3 |−|V1 ∩ V3 |+|V1 ∩ V2 ∩ V3 | =
(30 + 30 + 25) − 16 − 18 − 17 + 15 = 49 > 45 = |V |
Vậy bản báo cáo thành tích của lớp đó là sai.
Ví dụ 1.2 (VMO 2005, Bảng B). Tìm kết quả học tập của một lớp học,
người ta thấy: hơn 32 số học sinh đạt điểm giỏi ở môn Toán cũng đồng thời
đạt điểm giỏi ở môn Vật Lý ; hơn 23 số học sinh đạt điểm giỏi ở môn Vật Lý
cũng đồng thời đạt điểm giỏi ở môn Ngữ văn; hơn 23 số học sinh đạt điểm
giỏi ở môn Ngữ Văn cũng đồng thời đạt điểm giỏi ở môn Lịch sử; hơn 23 số
học sinh đạt điểm giỏi ở môn Lịch Sử cũng đồng thời đạt điểm giỏi ở môn
Toán. Chứng minh rằng tồn tại ít nhất một học sinh đạt điểm giỏi ở cả bốn
môn nêu trên.
Giải.
Ký hiệu T, L, V, S lần lượt là tập hợp các học sinh đạt điểm giỏi ở môn Toán,
9
Vật Lý, Ngữ Văn, Lịch Sử. Đặt Tl = T ∩ L, Lv = L ∩ V, Vs = S ∩ V . Từ giả
thiết suy ra: |Tl | > 23 |T | , |Lv | > 32 |L| , |Vs | > 23 |V | ..
Ta cần chứng minh : |T ∩ L ∩ V ∩ S| > 0.
Vì T ∩ L ∩ V ∩ S = (T ∩ L) ∩ (L ∩ V ) ∩ (V ∩ S) nên ta cần chứng minh
|(T ∩ L) ∩ (L ∩ V ) ∩ (V ∩ S)| > 0.
Thật vậy, không mất tính tổng quát, giả sử |T | ≥ |L| ≥ |V | ≥ |S|. Ta có
|Tl ∩ Lv ∩ Vs | = |(Tl ∩ Lv ) ∩ Vs | = |Tl ∩ Lv | + |Vs | − |(Tl ∩ Lv ) ∪ Vs |
= |Tl | + |Lv | + |Vs | − |Tl ∪ Lv | − |(Tl ∩ Lv ) ∪ Vs |
> 32 |T | + 32 |L| + 32 |V | − |L| − |V | = 32 |T | − 13 |L| − 13 |V |
≥ 32 |T | − 31 |T | − 31 |T | = 0.
Vậy ta có điều phải chứng minh.
1.1.3
Công thức bao hàm và loại trừ
Cho V là tập hữu hạn và V1 ⊂ V . Ta sẽ có V 1 = V \V1 Khi đó
V 1 = |V | − |V1 | .
(1.4)
Cho tập hợp V và V1 , V2 ⊂ V . Khi đó
V 1 ∩ V 2 = |V | − |V1 ∪ V1 | = |V | − |V1 | − |V1 | + |V1 ∩ V1 | .
(1.5)
Cho tập hợp V và V1 , V2 , V3 ⊂ V . Khi đó.
V 1 ∩ V 2 ∩ V 3 = |V | − |V1 ∪ V2 ∪ V3 |
= |V | − |V1 | − |V2 | − |V3 | + |V1 ∩ V2 | + |V2 ∩ V3 | + |V1 ∩ V3 | − |V1 ∩ V2 ∩ V3 | .
(1.6)
Tổng quát với các tập tùy ý V1 , V2 , . . . , Vn ⊂ V bằng phương pháp quy nạp
theo n (n ≥ 2) ta có công thức
n
n
\
X
X
V
=
|V
|
−
|
|
+
| Vi ∩ Vj | − | V1 ∩ V2 ∩ V3 | − | V1 ∩ V2 ∩ V 4 |
Vi
i
i=1
i=1
i6=j
− · · · − | Vn−2 ∩ Vn−1 ∩ Vn | + · · · + (−1)n | V1 ∩ V2 ∩ · · · ∩ Vn |.
(1.7)
10
Ví dụ 1.3 ([1], Chuyên đề chọn lọc tổ hợp và toán rời rạc - Nguyễn Văn
Mậu). Một cuộc Hội thao cấp Thị xã có 4 môn thi: Cầu lông, bóng bàn,
chạy và cờ tướng. Có 100 vận động viên tham gia. Khi tổng kết, Ban tổ chức
nhận thấy rằng: Môn cầu lông có 18 vận động viên tham gia, môn bóng bàn
có 26 vận động viên tham gia, môn chạy có 19 vận động viên tham gia, môn
cờ tướng có 24 vận động viên tham gia; trong đó 5 người tham gia cả cầu
lông và bóng bàn; 2 người tham gia cầu lông và chạy; 3 người tham gia cầu
lông và cờ tướng; 5 người tham gia bóng bàn và chạy; 4 người tham gia bóng
bàn và cờ tướng; 3 người tham gia chạy và cờ tướng; 2 người tham gia đồng
thời cầu lông, bóng bàn, và chạy; 3 người tham gia cầu lông, bóng bàn và cờ
tướng; 2 người tham gia cầu lông, chạy và cờ tướng; 4 người tham gia bóng
bàn, chạy và tờ tướng; 1 người tham gia đồng thời cả 4 môn của Hội thao.
Hỏi có bao nhiêu vận động viên không tham gia thi đấu một môn nào của
Hội thao?
Giải.
Dùng V để ký hiệu tập hợp các vận động viên tham gia hội thao.
V1 tập hợp các vận động viên tham gia môn cầu lông.
V2 tập hợp các vận động viên tham gia môn bóng bàn.
V3 tập hợp các vận động viên tham gia môn chạy.
V4 tập hợp các vận động viên tham gia môn cờ tướng.
Khi đó số vận động viên không tham gia môn nào của Hội thao chính bằng
lực lượng của tập V1 ∩ V2 ∩ V3 ∩ V4 :
V1 ∩ V2 ∩ V3 ∩ V4 = 100 − (18 + 26 + 19 + 24)+
+(5 + 2 + 3 + 5 + 4 + 3) − (2 + 3 + 2 + 4) + 1 = 25
Vậy có 25 người không tham gia thi đấu môn nào của Hội thao.
1.2
1.2.1
Hai quy tắc cơ bản của phép đếm
Quy tắc cộng
Nội dung quy tắc: Giả sử có n hành động H1 , H2 , . . . , Hn không hành
động nào xảy ra đồng thời. Trong đó hành động Hi có mi cách thực hiện
11
(1 ≤ i ≤ n). Khi đó sẽ có m1 + m2 + · · · + mn cách thực hiện hành động H:
hoặc H1 xảy ra, hoặc H2 xảy ra , . . . , hoặc Hn xảy ra .
Quy tắc cộng có chuyển sang ngôn ngữ tập hợp như sau: Cho n tập hợp
V1 , V2 , . . . , Vn với |Vk | = mk (1 ≤ k ≤ n) và ∀i, j(1 ≤ i, j ≤ n)Vi ∩ Vj = ∅
khi i 6= j . Khi đó số cách thực hiện hành động H1 , hoặc H2 , . . . , hoặc Hn sẽ
n
S
S
P
bằng số cách chọn phần tử v thuộc nk=1 Vk và bằng | ni=1 Ak | =
|Ak |.
k=1
Ví dụ 1.4 (Đề tuyển sinh vào trường ĐH Y Hà Nội - 1999). Có thể lập được
bao nhiêu số chẵn gồm năm chữ số khác nhau lấy từ các chữ số 0, 2, 3, 6, 9
Giải.
Gọi n = a1 a2 a3 a4 a5 là số cần lập.
Vì n chẵn, nên a5 chẵn suy ra a5 ∈ {0, 2, 6}. Có hai trường hợp:
Trường hợp 1 a5 = 0 thì ta có
1 cách chọn a5 = 0
4 cách chọn a1 = 0
3 cách chọn a2 = 0
2 cách chọn a3 = 0
1 cách chọn a4 = 0
Vậy ta có 1 × 4 × 3 × 2 × 1 = 24 số n.
Trường hợp 2 a5 6= 0 thì ta có
2 cách chọn a5 ( vì a5 = 2 hoặc a5 = 6)
3 cách chọn a1
3 cách chọn a2
2 cách chọn a3
2 cách chọn a4
Vậy ta có 2 × 3 × 3 × 2 × 1 = 36 số n.
Tổng cộng hai trường hợp ta có 24+36 = 60 số n thỏa mãn yêu cầu bài toán.
Ví dụ 1.5 (Đề thi tuyển sinh đại học khối A,B - 2001). Có bao nhiêu số tự
nhiên có 4 chữ số sao cho không có chữ số nào lặp lại đúng 3 lần ?
Giải.
12
Gọi n = a1 a2 a3 a4 là số tự nhiên cần lập. Tổng các số n có bồn chữ số ( không
chú ý đến điều kiện không có chữ số nào lại lại đúng ba lần).
Ta có 9 cách chọn a1 ( do a1 6= 0 )
10 cách chọn a2
10 cách chọn a3
10 cách chọn a4
Do đó ta có 9 × 10 × 10 × 10 = 9000 số n
Tính các số n có bốn chữ số và có chữ số lập lại đúng ba lần.
+) Trường hợp 1 : Ta có 9 cách chọn a1 (a1 6= 0, a1 lặp lại ba lần)
Chọn a2 = a3 = a1 , có 1 cách chọn.
Chọn a4 6= a1 , 9 cách chọn.
Vậy ta có 9 × 9 = 81 cách.
+) Trường hợp 2 : Chọn a1 6= 0 có 9 cách.
Chọn a2 = a3 = a4 , có 1 cách (a2 lặp lại 3 lần)
Chọn a4 6= a1 , a4 có 9 cách chọn.
Vậy ta có 9 × 9 = 81 cách.
+) Trường hợp 3 : Chọn a1 6= 0 có 9 cách.
Chọn a3 = a4 = a1 , có 1 cách (a3 lặp lại 3 lần)
Chọn a2 6= a3 , a2 có 9 cách chọn.
Vậy ta có 9 × 9 = 81 cách.
+) Trường hợp 4 : Chọn a1 6= 0 có 9 cách.
Chọn a2 = a3 = a4 , có 1 cách (a4 lặp lại 3 lần)
Vậy ta có 9 × 9 = 81 cách.
Từ 4 trường hợp ta có 81 + 81 + 81 + 81 = 324 số n có một chữ số lặp lại
đúng ba lần.
Do đó các số n thỏa mãn yêu cầu bài toán là 9000 − 324 = 8676 số.
1.2.2
Quy tắc nhân
Nội dung quy tắc : Giả sử một hành động H bao gồm n giai đoạn kế tiếp
và độc lập với nhau, trong đó giai đoạn thứ i là hành động Hi , (1 ≤ i ≤ n).
Ta cũng giả sử rằng hành động Hi có mi , (1 ≤ i ≤ n) cách thực hiện. Khi
13
đó hành động H sẽ có m1 m2 . . . mi cách thực hiện.
Quy tắc nhân ta có thể chuyển sang ngôn ngữ tập hợp như sau :Cho n tập
hợp V1 , V2 , . . . , Vn hữa hạn bất kì và|Vk | = mk (1 ≤ k ≤ n). Khi đó số cách
thực hiện hành động H sẽ tương ứng bằng với lực lượng của tập tích Đề các
của các tập đó :
|V1 × V2 × · · · × Vn | = |V1 | |V2 | . . . |Vn | = m1 m2 . . . mn
Ví dụ 1.6. Từ thành phố A đến thành phố B có 3 con đường, từ thành phố
B đến thành phố C có 4 con đường. Một ô tô trở hàng từ thành phố A đến
C rồi quay lại thành phố A ( cả hai lượt đi và về ô tô đều đi qua B) . Hỏi
có tất cả bao nhiêu cách đi sao cho đoạn đường lúc đi không trùng với đoạn
đường về.
Giải.
Tìm đường đi từ A đến B có 3 còn đường, đi từ B đến C có 4 con đường.
Vậy ta có 3 × 4 = 12 con đường đi từ A đến C qua B.
Tìm đường đi từ C về B có 3 con đường, đi từ B về A có 2 ( vì đoạn đường
lúc đi không trùng với đoạn đường về)
Vậy ta có 3 × 2 = 6 con đường đi từ C về A qua B.
Do đó ta sẽ có 12 × 6 = 72 cách đi từ thành phố A đến thành phố C rồi quay
lại thành phố A sao cho đoạn đường lúc đi không trùng với đoạn đường về.
Ví dụ 1.7. Từ các số 0,1,2,3,4,5,6 có thể lập được bao nhiêu số tự nhiên có
5 chữ số khác nhau đôi một mà bắt buộc phải có chữ số 5.
Giải.
Gọi n = a1 a2 a3 a4 a5 là số tự nhiên cần lập.Có hai trường hợp.
+) Nếu a1 = 5 thì ta có 1 cách chọn a1
6 cách chọn a2
5 cách chọn a3
4 cách chọn a4
3 cách chọn a5
Trường hợp này ta có 1 × 6 × 5 × 4 × 3 = 360 số.
14
+) Nếu a1 6= 5 : Có bốn vị trí chữ số 5 trong n ứng với một vị trí của 5 ta
có chẳng hạn n = a1 a2 5a4 a5 thì ta có
5 cách chọn a1 ( vì a1 6= 0, a1 6= 5)
1 cách chọn a2
5 cách chọn a3
4 cách chọn a4
3 cách chọn a5
Trong trường hợp này ta có 4 × 5 × 1 × 5 × 4 × 3 = 1200 số n.
Vậy tổng hai trường hợp ta có 1200 + 360 = 1560 số n.
1.3
Hoán vị
Hoán vị thực chất là một cách sắp xếp nào đó các phần tử của một tập
hợp.
1.3.1
Hoán vị không lặp
Định nghĩa 1.1 ([1]-[4]). Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi
cách sắp xếp n phần tử này theo một tứ tự nào đó (mỗi phần tử có mặt đúng
một lần) được gọi là một hoán vị của n phần tử đã cho. Kí hiệu số hoán vị
của n phần tử bằng Pn .
Ta có công thức: Pn = n!
Ví dụ 1.8. Với sáu chữ số 1, 2, 3, 4, 5,6 có thể lặp được bao nhiêu số gồm
sáu chữ số, không trùng nhau.
Giải.
Mỗi số cần lập là một hoán vị của 6 số đã cho. Do đó, số cần lập bằng đúng
số các hoán vị của 6 phần tử. Do đó ta có tổng số các số có 6 chữ số cần lập
là : P6 = 6! = 720
Ví dụ 1.9. Từ các chữ sô 0,1,2,3,4,5 có thể lập được bao nhiêu số tự nhiên
có 6 chữa số, không trùng nhau.
15
Giải.
Do các số có 6 chữ số cần lập là các số tự nhiên nên chữa số 0 không được
đứng vị trí đầu tiên.
Xét trường hợp số 0 đứng vị trí đầu tiên các vị trí còn lại được sắp sếp từ
các số 1,2,3,4,5 ta có P5 = 5! = 120
Nếu sắp sếp 6 chữa số trên thành số có 6 chữ số trong đó có cả trường hợp
số 0 đứng vị trí đầu tiên ta sẽ có P6 = 6! = 720
Vậy tổng số các số tự nhiên có 6 chữa số cần lập là : P6 − P5 = 600 số.
Ví dụ 1.10 ([1], Chuyên đề chọn lọc tổ hợp và toán rời rạc - Nguyễn Văn
Mậu). Cho tập S = {1, 2, . . . , n} với n ≥ 1 và f là một hoán vị của tập S.
Phẩn tử i của S được gọi là một điểm cố định nếu f (i) = i. Gọi Pn (k) là số
hoán vị của tập S có đúng k điểm cố định. Hãy chứng minh rằng
n
X
kPn (k) = n!
(1.8)
k=0
Giải.
1) Vì tổng tất cả các hoán vị của n phần tử có 0,1,2,. . . ,n điểm cố định bằng
tất cả các hoán vị có thể của n phần tử, tức bằng n!, nên có đẳng thức
n
X
Pn (k) = n!
(1.9)
k=0
2) Ta chứng minh rằng: ∀k (1 ≤ k ≤ n)đều có kPn (k) = n.Pn−1 (k − 1) Dùng
(f, i) để kí hiệu cặp gồm hoán vị f tùy ý của n phần tử với k điểm cố định
và i là điểm tùy ý trong k điểm cố định đó ( tức f (i) = i ).
Thừa nhận P0 (0) = 1
Để lý giải quan hệ (1.11), ta hãy tính số N cáp cặp (f,i) bằng hai cách. Một
mặt, i chạy qua k điểm cố định đã xác định, nên mỗi hoán vị trong Pn (k)
hoán vị đó có mặt trong k cặp (f,i). Bởi vậy N = k.Pn (k). Mặt khác, nếu
f (i) = i, thì trên tập gồm n − 1 phần tử còn lại ( tức các phần tử khác i
) hoán vị f có k − 1 điểm cố định, nên mỗi một trong n phần tử i có mặt
trong Pn−1 (k − 1) cặp. Do đó N = n.Pn−1 (k − 1), nên đẳng thức (1.11) được
chứng minh.
Tính tổng các đẳng thức ở (1.11) theo k = 1, 2, . . . , n và dựa vào đẳng thức
16
(1.10) bằng cách thay n bằng n − 1 ta có
n
X
k=0
1.3.2
kPn (k) =
n
X
nPn−1 (k − 1) = n
k=1
n
X
Pn−1 (k − 1) = n (n − 1)! = n!.
k=1
Hoán vị có lặp
Định nghĩa 1.2. Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp
xếp n phần tử này theo một tứ tự nào đó (mỗi phần tử có mặt ít nhất một
lần) được gọi là là hoán vị lặp.
Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i(1 ≤ i ≤ k)
xuất hiên ni luần được kí hiệu là P (n1 , n2 , . . . , nk ) và được tính bằng công
thức
n!
P (n1 , n2 , . . . , nk ) =
n1 !n2 !...nk !
Ví dụ 1.11 (Đề tuyển sinh vào trường ĐH - Khối D - 2001). Từ các chữ
số 0,1,2,3,4 có thể lập được bao nhiêu số có bảy chữ số trong đó chữ số 4 có
mặt đúng ba lần, còn các chữ số khác có mặt đúng một lần.
Giải.
Gọi n = a1 a2 a3 ...a7 (ai ∈ X = {0, 1, 2, 3, 4, 4, 4}) là số cần lập.
Áp dụng công thức ta có số n được lập kể cả các số n có dạng 0a2 a3 ...a7 là
7!
3! .
Số các số n có dạng 0a2 a3 ...a7 là 6!
3! .
7!
Vậy số các số n đúng yêu cầu bài toán là : 3!
− 6!
3! = 720 số.
Ví dụ 1.12. Với sáu chữ số 0,1,2,3,4,5 có thể lập được bao nhiêu số chia hết
cho 5 gồm 11 chữ số, trong đó chữ số 1 có mặt 4 lần, chữ số 2 có mặt 3 lần,
chữ số 3 có mặt 2 lần, chữ số 4 có mặt 1 lần và tổng số lần xuất hiện của
chữ số 0 và chữ số 5 là 1.
Giải.
Gọi số cần lập là n = a1 a2 a3 ...a11 . Do n chia hết cho 5 nên n phải tận cùng
bằng 0 hoặc 5.
Vì tổng số lần xuất hiện trong n của 0 và 5 bằng 1 nên nếu n tận cùng
17
bằng 0 thì 5 không có mặt và ngược lại nếu n tận cùng bằng 5 thì chữ số 0
không xuất hiện. Bởi vậy ai (1 ≤ i ≤ 10) chỉ có thể là một trong những chữ
số 1,2,3,4.
Bởi vậy số khả năng lập phần dầu độ dài 10a1 a2 a3 ...a10 của số n bằng số
hoán vị lặp của 10 phần tử thuộc 4 loại chữ sô : 1,2,3,4 với 1 xuất hiện 4 lần,
2 xuất hiện 3 lần, 3 xuất hiện 2 lần và 4 xuất hiện 1 lần, sẽ bằng P(1,2,3,4).
Ngoài ra a11 lại có thể nhận giá trị 0 hoặc 5 nên số cần tìm sẽ là
2P (1, 2, 3, 4) =
1.4
1.4.1
10!
.2 = 25200
1!2!3!4!
Chỉnh hợp
Chỉnh hợp không lặp
Định nghĩa 1.3. Cho tập hợp A gồm n phần tử. Mỗi bộ gồm k 0 ≤ k ≤ n
phần tử được sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k
của n phần tử thuộc A.
Kí hiệu số chỉnh hợp chập k của n phần tử bằng Akn . Số chỉnh hợp chập k
của n phần tử được tính bởi công thức
Akn = n(n − 1)...(n − k + 1) =
n!
(n − k)!
Ví dụ 1.13. Một lớp học có 25 học sinh. Muốn chọn ra một lớp trưởng, một
lớp phó và một thủ quỹ mà không cho kiêm nhiệm. Hỏi có bao nhiêu cách
chọn ?
Giải.
Mỗi cách chọn tra một lớp trưởng, một lớp phó và một thủ quỹ là một chỉnh
hợp chập ba 3 của tập 25 phần tử.
Số các chỉnh hợp là :
A325 =
25!
= 13800
(25 − 3)!
Vậy có 13800 cách chọn ra một lớp trưởng, một lớp phó và một thủ quỹ trong
lớp học có 25 học sinh.
18
Ví dụ 1.14. Từ các số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên
(số nguyên không âm); mà trong mỗi số này các chữ số không lặp lại.
Giải.
Vì có 6 chữ số khác nhau, nên số dài nhất trong các số cần tìm cũng chỉ gồm
6 chữ số.
Ta lập các loại số tự nhiên dạng a1 a2 ...an
Dùng S1 để kí hiệu tập số dạng a1
Dùng S2 để kí hiệu tập số dạng a1 a2
Dùng S3 để kí hiệu tập số dạng a1 a2 a3
Dùng S4 để kí hiệu tập số dạng a1 a2 a3 a4
Dùng S5 để kí hiệu tập số dạng a1 a2 a3 a4 a5
Dùng S6 để kí hiệu tập số dạng a1 a2 a3 a4 a5 a6
Kí hiệu một chỉnh hợp chập k của 6 phần tử 0, 1, 2, 3, 4, 5 bằng (Ci1 , Ci2 , . . . , Cik ).
Mỗi số tự nhiên Ci1 Ci2 Cik với các chữ số khác nhau Cij thuộc tập 0, 1, 2, 3, 4, 5,
(1 ≤ j ≤ k) đều tương ứng với một chỉnh hợp chập k của sáu phần tử 0, 1, 2,
3, 4, 5. Ngược lại, mỗi chỉnh hợp chập k (k ≥ 2) (Ci1 , Ci2 , . . . , Cik ) của sáu
phần tử 0, 1, 2, 3, 4, 5 tương ứng với một số tự nhiên, nếu Ci1 6= 0. Ngược lại,
nếu Ci1 = 0, thì nó không tương ứng với số tự nhiên gồm k chữ số. Nhưng
tương ứng với một chỉnh hợp chập k – 1 (Ci2 , Ci3 . . . , Cik ) của năm phần tử
1, 2, 3, 4, 5. Từ đó có
6! 5!
− = 720 − 120 = 600;
0! 0!
|S5 | = A56 − A45 = 720 − 120 = 600;
|S6 | = A66 − A55 =
|S4 | = A46 − A35 = 300;
|S3 | = A36 − A25 = 100;
|S2 | = A26 − A25 = 25;
|S1 | = 6
Vậy các số tự nhiên có thể lập là:
S = |S1 |+|S2 |+|S3 |+|S4 |+|S5 |+|S6 | = 6+25+100+300+600+600 = 1631.
19
Ví dụ 1.15. ( Bài toán đếm số tất cả các hàm đơn ánh từ một tập hữu hạn
vào một tập hữu hạn) Giả sử N và M là hai tập hữu hạn với |N | = n và
|M | = m . Hãy xác định số các hàm đơn ánh f : N → M .
Giải.
Giả sử N = {a1 , a2 , ..., an } . Khi đó một hàm đơn ánh f : N → M tương ứng
với đúng một bộ có thứ tự gồm n thành phần là (f (a1 ) , f (a2 ) , ..., f (an ))
với f (a1 ) , f (a2 ) , ..., f (an ) ∈ M . và f (ai ) 6= f (aj ) nếu i 6= j
Do đó số các hàm f : N → M bằng số chỉnh hợp chập n của m phần tử của
M, tức là bằng Anm
Vậy ta có số tất cả các hàm đơn ánh f : N → M với |N | = n và |M | = m
bằng Anm
1.4.2
Chỉnh hợp có lặp
Định nghĩa 1.4. Cho tập hữu hạn X gồm n phần tử. Mỗi dãy có độ dài k
các phần tử của tập X, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp
xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n
phần tử thuộc tập X.
Số chỉnh hợp lặp chập k của n phần tử, ký hiệu là Akn , bằng số ánh xạ từ tập
k phần tử đến tập n phần tử và bằng nk , tức Akn = nk .
Ví dụ 1.16. Từ bốn chữ số 1, 2, 3, 5 có thể thành lập được bao nhiêu số
chẵn gồm 4 chữ số?
Giải.
Vì tập 1, 2, 3, 5 chỉ có duy nhất một chữ số chẵn là 2, nên x = abcd với a, b,
c, d thuộc tập 1, 2, 3, 5 là số chẵn khi và chỉ khi d bằng 2.
Mặt khác a, b, c có thể bằng nhau, nên y = abc là một chỉnh hợp lặp chập
3 của bốn phần tử 1, 2, 3, 5.
Để thành lập số x ta chỉ cần lấy một số y nào đó rồi thêm 2 vào cuối. Bởi
vậy, số các số x = abc2 bằng các số y = abc và bằng A34 = 43 = 64.
Chẳng hạn 1112, 1122, 1132, 1152, . . . , 5542, 5552.
Ví dụ 1.17. ( Bài toán đếm số các hàm từ một tập hữu hạn vào một tập
- Xem thêm -