Bài giảng Toán rời rạc - Chương 3: Phép đếm - Nguyễn Anh Thi

Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Bài giảng môn học Toán Rời Rạc
Nguyễn Anh Thi
Trường Đại học Khoa học Tự nhiên, Tp Hồ Chí Minh
2017
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Chương 3
Phép đếm
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Nội dung
1 Các nguyên lý
2 Giải tích tổ hợp
3 Hoán vị lặp, tổ hợp lặp
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Các nguyên lý
Nguyên lý cộng: Giả sử để làm công việc A ta có thể chọn một
trong hai biện pháp khác nhau (theo nghĩa là cách thực hiện
biện pháp thứ nhất luôn luôn khác cách thực hiện biện pháp
thứ hai). Nếu biện pháp thứ nhất có m cách, biện pháp thứ hai
có n cách, thì ta có số cách làm công việc A là m + n.
Tổng quát, giả sử để làm công việc A ta có thể chọn một trong
k biện pháp khác nhau, mỗi biện pháp có mi cách làm với
i = 1, 2, . . . , k, khi đó số cách làm công việc A là
m1 + m2 + · · ·+ mk.
Ví dụ
Ta chọn một viên bi bất kỳ từ hai hộp A và B. Biết rằng hộp A
chứa 5 viên bi màu đỏ, hộp B chứa 3 viên bi màu xanh. Vậy
số cách chọn là 5 + 3 = 8.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Các nguyên lý
Nguyên lý nhân: Giả sử chúng ta phải thực hiện một công việc
bao gồm hai công việc kế tiếp nhau. Để thực hiện công việc
thứ nhất chung ta có m cách, và ứng với mỗi cách chọn thực
hiện công việc thứ nhất ta có n cách thực hiện công việc thứ
hai.Vậy ta có số cách thực hiện công việc đó là m.n.
Tổng quát, Giả sử một công việc bao gồm k bước kế tiếp nhau,
nếu mỗi bước ta có ni cách làm với i = 1, 2, . . . , k. Vậy ta có
n1.n2. . . . .nk cách để thực hiện công việc.
Ví dụ
Ta chọn hai viên bi màu khác nhau từ hai hộp A và B. Biết
rằng hộp A chứa 5 viên bi màu đỏ, hộp B chứa 3 viên bi màu
xanh. Vậy số cách chọn là 5.3 = 15.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Các nguyên lý
Nguyên lý chuồng bồ câu (Derichlet) Gọi dxe là số nguyên nhỏ
nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu trong k
chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ dn/ke bồ
câu trở lên.
Ví dụ
Trong nhóm có 367 người thì ít nhất có 2 người sinh cùng
ngày.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Các nguyên lý
Nguyên lý bù trừ: Cho A và B là hai tập hữu hạn. Khi đó
|A ∪ B| = |A|+ |B| − |A ∩ B|
Ví dụ
Trong lớp có 24 học sinh học tiếng Pháp, 26 học sinh học
tiếng Anh, có 15 học sinh vừa học tiếng Anh, vừa học tiếng
Pháp. Hỏi lớp có bao nhiêu học sinh?
Gọi A là tập hợp những học sinh học tiếng Pháp, B là tập hợp
những học sinh học tiếng Anh. Khi đó số học sinh của lớp là
A ∪ B = |A|+ |B| − |A ∩ B| = 24 + 26− 15 = 35.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Nguyên lý bù trừ: Cho A,B và C là các tập hữu hạn. Khi đó
|A∪B∪C| = |A|+|B|+|C|−|A∩B|−|B∩C|−|A∩C|+|A∩B∩C|.
Ví dụ
Ở một trường trung học có 14 học sinh chơi bóng đá, 17 học
sinh chơi bóng rổ, 18 học sinh chơi bóng bầu dục. Trong đó có
4 học sinh chơi cả bóng đá và bóng rổ, 3 học sinh chơi cả
bóng đá và bóng bầu dục, 5 học sinh chơi cả bóng rổ và bóng
bầu dục, và có 1 học sinh chơi cả 3 môn. Hỏi có bao nhiêu
học sinh chơi ít nhất một trong những môn thể thao trên?
Gọi A là tập hợp những học sinh chơi bóng đá, B là tập hợp
những học sinh chơi bóng rổ, và C là tập hợp những học sinh
chơi bóng bầu dục. Số học sinh chơi ít nhất một trong những
môn thể thao trên là:
|A∪B∪C| = |A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C| =
14 + 17 + 18− 4− 3− 5 + 1 = 38.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Giải tích tổ hợp
Định nghĩa
Cho tập hợp A có n phần tử. Mỗi cách sắp đặt có thứ tự n
phần tử của A được gọi là một hoán vị có n phần tử. Số các
hoán vị của n phần tử ký hiệu là Pn, và
Pn = n! = n.(n− 1).(n− 2)...2.1, quy ước 0! = 1.
Ví dụ
• Cho X là tập hợp có n phần tử thì số song ánh từ X vào X
là n!
• Cho A = {a, b, c}. Khi đó A có các hoán vị sau: abc, acb,
bac, bca, cab, cba.
• Cho X = {1, 2, 3, 4, 5}, hỏi có bao nhiêu số tự nhiên gồm
5 chữ số khác nhau được tạo thành từ tập X?
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Giải tích tổ hợp
Định nghĩa
Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử
(1 ≤ k ≤ n) 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ử. Số các chỉnh hợp chập k của n, ký
hiệu là Akn. Ta có công thức Akn = n!(n−k)!
Ví dụ
Cho X = {a, b, c}. Khi đó X có các chỉnh hợp chập 2 của các
phần tử của X là: ab, ac, bc, ba, ca, cb.
Ví dụ
Có bao nhiêu số tự nhiên gồm 3 chữ số khác nhau được tạo
thành từ {1, 2, 3, 4, 5, 6} ?
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Giải tích tổ hợp
Định nghĩa
Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k phần tử của
A được gọi là một tổ hợp chập k của n phần tử. Số các tổ hợp
chập k của n phần tử được ký hiệu là Ckn hay
(
n
k
)
. Ta có
công thức
Ckn =
n!
k!(n− k)!
Tính chất
Cn−kn = Ckn
Ckn + Ck−1n = Ckn+1
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Ví dụ
Cho X = {1, 2, 3, 4}. Tổ hợp chập 3 của 4 phần tử của X là
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}
Ví dụ
Một lớp có 30 học sinh, hỏi có bao nhiêu cách chọn 10 bạn.
Số cách chọn là tổ hợp chập 10 của 30: C1030.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Giải tích tổ hợp
Định lý
Với x, y là các biến thực, n là số nguyên không âm tùy ý, thì:
(x + y)n =
n∑
i=0
Cinxn−iyi
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Hoán vị lặp, tổ hợp lặp
Định nghĩa
Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau
(i = 1, 2, . . . , k;n1 + n2 + · · ·+ nk = n). Mỗi cách sắp xếp có
thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n.
Số hoán vị của n đối tượng, trong đó có n1 đối tượng giống
nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,. . . , nk
đối tượng giống nhau thuộc loại k, là
n!
n1!n2! . . .nk!
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Hoán vị lặp, tổ hợp lặp
Ví dụ
Có bao nhiêu chuỗi ký tự khác nhau bằng cách sắp xếp các
chữ cái của từ SUCCESS?
Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C, và 1 chữ E.
Do đó số chuỗi có được là
7!
3!1!2!1! = 420
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc
Bài giảng môn
học Toán Rời
Rạc
Nguyễn Anh
Thi
Nội dung
Các nguyên lý
Giải tích tổ
hợp
Hoán vị lặp, tổ
hợp lặp
Nội dung
Các nguyên lý
Giải tích tổ hợp
Hoán vị lặp, tổ hợp lặp
Hoán vị lặp, tổ hợp lặp
Định nghĩa
Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi
loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp
chập k của n. Số các tổ hợp lặp chập k của n được ký hiệu là
Kkn.
Kkn = Ckn+k−1
Ví dụ
Có 3 loại nón A,B,C. An mua 2 cái nón. Hỏi An có bao nhiêu
cách chọn?
Mỗi cách chọn là một tổ hợp lặp chập 2 của 3. Cụ thể
AA,AB,BB,BC,CC,AC, K23 = C23+2−1 = C24 = 6.
Nguyễn Anh Thi Bài giảng môn học Toán Rời Rạc