2.1 Các nguyên lý đếm cơ bản 23
Định lý 2.7 Cho ntập hữu hạn A1,A2,...,An. Khi đó,
|A1∪A2∪...∪An|=
n
∑
k=1
(−1)k−1∑
1≤i1<i2<...<ik≤n
|Ai1∩Ai2∩...∩Aik|.
2.1.6 Bài tập
1.
Khóa 59 của viện Toán ứng dụng và Tin học có 23 sinh viên định
hướng Toán và 95 sinh viên định hướng Tin.
(a)
Hỏi có bao nhiêu cách chọn ra hai đại diện sinh viên sao cho
có một sinh viên định hướng Tin và một sinh viên định hướng
Toán?
(b)
Hỏi có bao nhiêu cách chọn ra một đại diện sinh viên định
hướng Tin hoặc Toán?
2.
Bài thi trắc nghiệp có 10 câu hỏi, mỗi câu sinh viên chỉ được chọn
một trong bốn đáp án.
(a)
Hỏi có bao nhiêu cách sinh viên làm bài nếu sinh viên đó trả
lời tất cả các câu hỏi?
(b)
Hỏi có bao nhiêu cách sinh viên làm bài nếu sinh viên đó có
thể bỏ trống phần trả lời?
3.
Tính số chuỗi nhị phân độ dài
n
và số chuỗi nhị phân độ dài không
quá n.
4.
Tính số chuỗi nhị phân độ dài
n
có tính chất: không thay đổi khi
viết theo thứ tự ngược.
5.
Có bao nhiêu chuỗi nhị phân độ dài 10 bắt đầu bằng hai chữ số 1
hoặc kết thúc bằng 3 chữ số 0.
6.
Có bao nhiêu chuỗi nhị phân độ dài 10 chứa hoặc 5 chữ số 0 liên
tiếp hoặc 5 chữ số 1 liên tiếp.
7.
Có bao nhiêu chuỗi nhị phân độ dài 10 rơi vào chỉ một trong hai
khả năng hoặc 4 chữ số 0 liên tiếp hoặc 5 chữ số 1 liên tiếp?
8.
Có bao nhiêu số nguyên dương không vượt quá 100 chia hết cho
hoặc 4 hoặc 6?
24 Bài toán đếm
9.
Có bao nhiêu số nguyên dương không vượt quá 100 rơi vào chỉ một
trong hai khả năng hoặc chia hết cho 4 hoặc chia hết cho 6?
10.
Mã Morse: Trong hệ mã Morse, mỗi chữ cái trong đươc biểu diễn
bằng một chuỗi các ký hiệu telex gồm các "chấm" và "vạch". Tính
số chữ cái chó thể biểu diễn được bằng chuỗi nký hiệu.
11.
Một bảng chữ cái, một cách tổng quát, là một tập hợp
L={l1,l2,...,ln}
gồm
n
chữ cái khác nhau. Một bộ
k
chữ cái của bảng chữ cái
L
là
một
k
-từ. Tính số 3-từ của bảng chữ cái
L
, số 3-từ không cho phép
lặp lại chữ cái và số 3-từ chứa chữ cái ln.
12.
Trong một lớp trung học có 40 học sinh. Trong số đó có 14 thích
học môn toán, 16 thích môn vậy lý, và 11 thích môn hóa học. Đồng
thời, bảy học sinh thích cả toán và lý, tám thích cả lý và hóa, năm
thích cả toán và hóa, bốn thích cả ba môn. Hỏi có bao nhiêu học
sinh không thích cả toán, lý lẫn hóa.
13. Sử dụng nguyên lý cộng chứ minh nguyên lý nhân.
2.2 Hoán vị, chỉnh hợp và tổ hợp
Nhiều bài toán đếm có thể đưa về bài toán tìm số cách sắp xếp một số
phần tử đặc biệt của một tập hơp theo một thứ tự nào đó. Cũng có nhiều
bài toán giải bằng việc tìm số cách chọn một số phần tử từ một tập hợp
nào đó mà không kể đến thứ tự. Ví dụ, tìm số cách chọn ra ban chấp hành
chi đoàn thanh niên gồm ba thành viên từ một chi đoàn có 15 thành viên.
Trong phần này chúng ta sẽ tìm hiểu các công cụ liên quan đến những
bài toán dạng này.
2.2.1 Chỉnh hợp và hoán vị
Định nghĩa 2.2
Một hoán vị của một tập hợp gồm các đối tượng khác
nhau là một thứ tự sắp xếp các đối tượng này.
Nếu chỉ chọn ra kphần tử để sắp xếp thì được gọi là k-chỉnh hợp.
Một
k
-chỉnh hợp của tập hợp
n
số tự nhiên đầu tiên
{1,2,...,n}
được
2.2 Hoán vị, chỉnh hợp và tổ hợp 27
Định lý 2.10
Số chỉnh hợp vòng chập
k
của
nn!
k·(n−k)!
. Đặc biệt số
hoán vị vòng của tập gồm nphần tử là (n−1)!
Ví dụ 2.9
Có bao nhiêu cách xếp sáu sinh viên ngồi trên một bài tròn
trong đó có hai sinh viên không thích ngồi cạnh nhau?
Lời giải:
Chỉnh hợp lặp và tổ hợp lặp
2.2.4 Bài tập
1.
Có bao nhiêu cách xếp bốn sinh viên An, Bình, Cường, Dũng thành
một hàng dọc sao cho Bình không đứng ngay sau An.
2.
Đoàn tàu thống nhất có hai toa hành lý, một toa ăn, năm toa giường
nằm và ba toa ghế ngồi. Hỏi có bao nhiêu cách xếp các toa?
3.
Trong kỳ thi tuyển sinh đại học, một trường dựa trên kết quả thi của
bốn môn. Để đỗ, thí sinh phải đạt tối thiểu 5 điểm mỗi môn, đồng
thời tổng điểm bốn môn không thấp hơn 25. Hỏi có bao nhiêu kết
quả thi có thể để thí sinh đỗ?
4.
Phương trình
x1+x2+x3+x4+x5=20
có bao nhiêu nghiệm
nguyên dương?
5. Tìm số nghiệm nguyên của phương trình
x1+x2+x3+x4+x5=30
với x1≥3,x2≥2,x3≥0,x4≥5và x5≥−5.
6. Có bao nhiêu cách chia mười người thành bốn cặp đôi?
7.
Có bao nhiêu cách xếp tám quân xe trên bàn cờ
8×8
sao cho không
có hai con nào ăn nhau?
8.
Có bao nhiêu cách xếp 52 lá bài tú lơ khơ sao cho tất cả các quân
bài cùng chất luôn đi với nhau.
28 Bài toán đếm
9.
Có bao nhiêu số tự nhiên lớn hơn 5400 sao cho (i) không có hai
chữ số nào giống nhau, (ii) chữ số 3 và 5 không xuất hiện.
10.
Có bao nhiêu cách xếp năm người đàn ông ngồi xen kẽ năm người
phụ nữ trên bàn tròn?
11.
Có bao nhiêu cách xếp 10 người ngồi trên bàn tròn sao cho B không
ngồi cạnh A? Sao cho B không ngồi bên phải A?
12.
Có bao nhiêu cách chọn một hội đồng năm người từ một câu lạc
bộ gồm 8 người đàn ông và 10 người phụ nữ sao cho có ít nhất hai
người phụ nữ được chọn? Sao cho có thêm điều kiện người đàn
ông A và người phụ nữ B không cùng có trong hội đồng?
13.
Có bao nhiêu tập ba số nguyên lấy trong các số từ 1 đến 20 không
chứa hai số nguyên liên tiếp?
14.
Đội tuyển thi olympic sinh viên toán gồm 12 sinh viên, 7 người thi
đại số và 5 người thi giải tích, được chọn từ 15 người trong đó 4
người có thể thi đai số, 5 người có thể thi giải tích và 6 người có
thể thi cả hai môn. Hỏi có bao nhiêu cách chọn đội tuyển có thể?
15.
Một lớp học có hai hàng ghế, mỗi hàng có 8 ghế. Có 14 sinh viên,
trong đó 6 sinh viên chỉ ngồi ở hàng bên trái, 5 sinh viên chỉ ngồi
ở hàng bên phải. Hỏi có bao nhiêu cách xếp chỗ các sinh viên này?
16. Một bữa tiệc có 10 người đàn ông và 15 người phụ nữ.
(a)
Có bao nhiêu cách ghép 10 căp đôi gồm một người đàn ông
và một người phụ nữ?
(b)
Có bao nhiêu cách ghép 8 cặp đôi gồm một người đàn ông
và một người phụ nữ?
17.
Sáu người thi chạy với nhau, hỏi có bao nhiêu thứ tự về đích? (cho
phép hòa)
18.
Có bao nhiêu cách xếp 6 sinh viên nam, 6 sinh viên nữ và một
giảng viên ngồi trên một bàn tròn sao cho không có hai sinh viên
nữ nào ngồi cạnh nhau, không có hai sinh viên nam nào ngồi cạnh
nhau? Câu hỏi tương tự nếu có hai giảng viên?
19.
Một giải bóng đá có 20 đội. Ba đội đứng đầu sẽ được nhận cúp
vàng, bạc và đồng tương ứng. Ba đội đứng cuối sẽ xuống hạng. Hai
