Bài giảng Toán rời rạc 1 - Chương III: Phép đếm - Võ Văn Phúc

hữ 
 số khác nhau, được lập từ các chữ số 0,1,2,3? 
Giải: 
 - Ta thấy số hàng trăm có 3 cách chọn một số từ các 
 số trên (vì không chọn số 0). 
- Số hàng chục có 3 cách chọn một con số. 
- Số hàng đơn vị có 2 cách chọn một con số. 
Vậy, số các con số có 3 chữ số khác nhau, được lập từ 
 các chữ số trên là: 3.3.2 = 18 (số). 
1.1 Những cơ sở của phép đếm 
Ví dụ 2: Có bao nhiêu xâu nhị phân có độ dài n? 
- Ta có n bit ký tự trong xâu nhị phân có độ dài n. 
- Mỗi bit ký tự chỉ có thể là 0 hoặc 1. Số cách chọn 
 cho một bit ký tự là 2. 
- Theo nguyên lý nhân, ta có tổng cộng 2n xâu nhị 
 phân khác nhau có độ dài bằng n. 
1.1 Những cơ sở của phép đếm 
 Nhận xét: Nguyên lý nhân được phát biểu bằng 
 ngôn ngữ tập hợp như sau: 
  Nếu A1, A2, ,Ak là các tập hợp hữu hạn, khi đó ta có: 
 |AAAAAA1 2 .. kk || 1 |.| 2 |...| |
1.1 Những cơ sở của phép đếm 
Ví dụ: Đoạn mã tính giá trị m theo nguyên lý nhân 
 như sau: 
 Kết quả: 
 m=n1.n2nk 
1.1 Những cơ sở của phép đếm 
Một số ví dụ về nguyên lý nhân: 
Ví dụ 1. Đếm số chỉnh hợp không lặp. Một chỉnh hợp không lặp 
 chập k của n phần tử là một bộ có thứ tự gồm k thành 
 phần lấy từ n phần tử đã cho. Các phần tử không được 
 phép lặp lại. 
 Lời giải. 
  Để xây dựng các chỉnh hợp không lặp ta xây dựng từ thành phần 
 đầu tiên, thành phần này có n cách lựa chọn. 
  Ứng với mỗi cách lựa chọn của thành phần đầu tiên ta xây dựng 
 tiếp thành phần thứ 2, thành phần này có (n-1) cách lựa chọn. 
  Tương tự như vậy, thành phần thứ k có (n-k+1) cách lựa 
 chọn. Như vậy, theo nguyên lý nhân số các chỉnh hợp không lặp 
 chập k của n phần tử là: 
 n!
 n(n-1)(n-2)..(n-k+1) =( ( nk )! ) 
1.1 Những cơ sở của phép đếm 
 Ví dụ 2. Đếm số chỉnh hợp lặp. Một chỉnh hợp lặp 
 chập k của n phần tử là một bộ có thứ tự gồm k 
 thành phần lấy từ n phần tử đã cho. Các phần 
 tử được phép lặp lại. 
  Lời giải. Gọi |A|=n là số cách chọn một phần tử 
 trong k phần tử lấy từ bộ n phần tử. Số cách chọn 
 bộ k phần tử theo nguyên lý nhân là tích đề các: 
 |A| |A| .. |A| với k lần. Ta có số cách là: 
 |A| |A| .. |A| = |Ak|= nk. 
 1.1 Những cơ sở của phép đếm 
 1.1.2 Nguyên lý bù trừ 
  Nguyên lý bù trừ là một mở rộng của nguyên lý cộng 
 đã được trình bày trong mục 1.1.1. Trong nguyên lý 
 này, nếu không có giả thiết về tính rời nhau của các 
 tập hợp thì: 
 |AB| = |A| + |B| - |AB| 
  Tổng quát, giả sử A1, A2,..,An là các tập hợp hữu 
 hạn. Khi đó, 
 n 1
|AAAAAAAAAAAA1 2 ..|||n i  | i  j |  | i  j k |..(1)| 1  2 ..| n
 1 i n 1 i j n 1 i j k n
1.1 Những cơ sở của phép đếm 
Ví dụ: Có tất cả 52 sinh viên. 
Trong đó có 11 sinh viên học tiếng Anh; 
10 sinh viên học tiếng Pháp; 
12 sinh viên học tiếng Nga; 
7 sinh viên học hai thứ tiếng Anh và Pháp; 
4 sinh viên học học hai thứ tiếng Pháp và Nga; 
2 sinh viên học hai thứ tiếng Nga và Anh. 
Có duy nhất 1 sinh viên học cả ba thứ tiếng trên. 
Hỏi có bao nhiêu sinh viên không học thứ tiếng nào 
 trong các thứ tiếng trên? 
1.1 Những cơ sở của phép đếm 
  Giải: Gọi A1, A2, và A3 lần lượt là các tập hợp các sinh 
 viên học tiếng Anh, Pháp, và Nga. Khi đó ta có: 
 . |A1|=11, |A2|=10, |A3|=12 (số sinh viên học 1 thứ tiếng) 
 . |A1  A2|=7, |A2  A3|=4,|A1  A3|=2 (số sinh viên học 
 2 thứ tiếng) 
 . |A1  A2  A3|=1 (số sinh viên học 3 thứ tiếng) 
 Khi đó số sinh viên có học một trong các thứ tiếng trên là: 
 | A1  A2  A3 |=21 
 Do đó, số sinh viên không học thứ tiếng nào trong các thứ 
 tiếng trên là: 
 52-21=31 
1.2 Nguyên lý Dirichlet 
1.2.1 Mở đầu 
 Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu 
 số chim nhiều hơn số ngăn chuồng thì có ít nhất một 
 ngăn có nhiều hơn một con chim bồ câu. Ta có 
 mệnh đề sau: 
 Mệnh đề: Nếu có k+1 (hoặc nhiều hơn) đồ vật 
 được đặt vào trong k hộp thì tồn tại một hộp có ít 
 nhất hai đồ vật. 
1.2 Nguyên lý Dirichlet 
Chứng minh mệnh đề: 
 Giả sử không có hộp nào trong k hộp chứa nhiều 
 hơn một đồ vật. 
 Khi đó, tổng số vật được chứa trong các hợp nhiều 
 nhất là bằng k. Điều này trái giả thiết là có ít nhất 
 k+1 vật. 
1.2 Nguyên lý Dirichlet 
 Ví dụ 1: 
 Trong bất kỳ một nhóm 367 người thế nào cũng có ít 
 nhất 2 người có ngày sinh nhật giống nhau bởi vì chỉ 
 có tất cả 366 ngày sinh khác nhau. 
 Ví dụ 2: 
 Trong kỳ thi học sinh giỏi, điểm bài thi được đánh 
 giá bởi một số nguyên trong khoảng từ 0 đến 100. 
 Hỏi rằng ít nhất có bao nhiêu học sinh dự thi để cho 
 chắc chắn tìm được hai học sinh có kết quả giống 
 nhau? Theo nguyên lý Dirichlet, số học sinh cần tìm 
 là 102, vì ta có 101 kết quả điểm thi khác nhau. 
1.2 Nguyên lý Dirichlet 
 1.2.2 Nguyên lý Dirichlet tổng quát 
 Mệnh đề: Nếu có N đồ vật được đặt vào trong k hộp thì 
 sẽ tồn tại một hợp chứa ít nhất [N/k] đồ vật. (Ở đây, 
 [x]= [N/k] là một số nguyên nhỏ nhất không nhỏ hơn 
 x= N/k, tức lá: x≤[x]<x+1) 
 Ví dụ 1: Trong 100 người, có ít nhất 9 người sinh cùng 
 một tháng. 
 Thật vậy, xếp những người sinh cùng tháng vào cùng 
 một nhóm. Có tất cả 12 tháng. Vậy theo nguyên lý 
 Dirichlet, tồn tại một nhóm có ít nhất 
 [100/12]=[8,3]=9 người. 
1.2 Nguyên lý Dirichlet 
 Ví dụ 2: 
 Có 5 loại học bổng khác nhau. Hỏi rằng phải có ít 
 nhất bao nhiêu sinh viên để chắc chắn rằng có ít 
 nhất là 6 người cùng nhận học bổng như nhau. 
 Giải: 
 Gọi N là số sinh viên, khi đó [N/5]=6 khi và chỉ khi 
 5<N/5≤6 hay 25<N≤30. Vậy N cần tìm là 26. 
1.2 Nguyên lý Dirichlet 
1.2.3 Một số ứng dụng của nguyên lý Dirichlet 
 VD1: Trong một phòng hợp có n người, bao giờ cũng tìm được 2 
 người có số người quen trong số những người dự hợp là như 
 nhau. 
Giải: 
- Số người quen của mỗi người trong phòng hợp nhận các giá trị từ 
 0 đến n-1. 
- Đặc biệt, trong phòng không thể đồng thời có người có số người 
 quen là 0 (tức là không quen người nào) và có người có số người 
 quen là n-1 (quen tất cả). 
- Vì vậy, theo số lượng người quen ta chỉ có thể phân n thành n-1 
 nhóm (0,..,n-2 hoặc 1,..,n-1). 
- Vậy nên theo nguyên lý Dirichlet tồn tại một nhóm có ít nhất 2 
 người có số người quen là như nhau. 
1.2 Nguyên lý Dirichlet 
1.2.3 Một số ứng dụng của nguyên lý Dirichlet (tt) 
 VD2: Trong một tháng gồm 30 ngày, một đội bóng 
 chuyền thi đấu mỗi ngày ít nhất một trận, nhưng chơi 
 không quá 45 trận. 
 Chứng minh rằng tìm được một giai đoạn gồm một số 
 ngày liên tục nào đó trong tháng sao cho trong giai 
 đoạn đó đội chơi đúng 14 trận. 
1.2 Nguyên lý Dirichlet 
1.2.3 Một số ứng dụng của nguyên lý Dirichlet (tt) 
 Giải: 
  Gọi aj là số trận mà đội đã chơi từ ngày đầu tháng đến hết 
 ngày j. Khi đó: 
 1 a1 < a2 < ... < a30 < 45 
 15 a1+14 < a2+14 < ... < a30+14 < 59. 
  Ta có: Sáu mươi số nguyên a1, a2, ..., a30, a1+ 14, a2 + 14, 
 ..., a30+14 nằm giữa 1 và 59. 
  Do đó, theo nguyên lý Dirichlet có ít nhất 2 trong 60 số này 
 bằng nhau. 
  Vì vậy tồn tại i và j sao cho ai = aj + 14 (j < i). Điều này 
 có nghĩa là từ ngày j + 1 đến hết ngày i, đội đã chơi 
 đúng 14 trận. 
1.2 Nguyên lý Dirichlet 
1.2.3 Một số ứng dụng của nguyên lý Dirichlet (tt) 
VD3: Giả sử trong một nhóm 6 người, mỗi cặp hai, 
 hoặc là bạn hoặc là thù. 
 Chứng tỏ rằng, trong nhóm có ba người là bạn lẫn 
 nhau hoặc có ba người là kẻ thù lẫn nhau. 
1.2 Nguyên lý Dirichlet 
1.2.3 Một số ứng dụng của nguyên lý Dirichlet (tt) 
 Giải: 
  Gọi A là một trong 6 người. Trong số 5 người của nhóm 
 hoặc là có ít nhất ba người là bạn của A hoặc có ít nhất ba 
 người là kẻ thù của A, điều này suy ra từ nguyên lý 
 Dirichlet tổng quát, vì [5/2] = 3. 
  Trong trường hợp đầu ta gọi B, C, D là bạn của A. nếu 
 trong ba người này có hai người là bạn thì họ cùng với A 
 lập thành một bộ ba người bạn lẫn nhau. Ngược lại, tức là 
 nếu trong ba người B, C, D không có ai là bạn ai cả thì 
 chứng tỏ họ là bộ ba người thù lẫn nhau. 
  Tương tự có thể chứng minh trong trường hợp có ít nhất 
 ba người là kẻ thù của A. 
1.3 Chỉnh hợp và tổ hợp suy rộng 
1.3.1 Chỉnh hợp có lặp 
a. Định nghĩa: Một cách sắp xếp có thứ tự k phần 
 tử có thể lặp lại của một tập n phần tử được gọi là 
 một chỉnh hợp lặp chập k từ tập n phần tử. 
b. Định lý: Số chỉnh hợp lặp chập k từ tập n phần tử 
 là: k k
 Ann 
1.3 Chỉnh hợp và tổ hợp suy rộng 
 1.3.2 Tổ hợp có lặp 
 Bài Toán: Một người vào một cửa hàng ăn uống muốn chọn mua 7 phần ăn, 
 mỗi phần ăn sẽ được chọn một trong 4 loại khác nhau: A, B, C, D. Hỏi có 
 bao nhiêu cách chọn 7 phần ăn. 
  Trong ví dụ trên, 7 phần ăn có thể được chọn là A, B, A, C, C, D, C trong đó 
 gồm 2 phần loại A, một loại B, 3 loại C và một loại D. 
  Bài toán trong ví dụ trên có thể phát biểu dưới dạng tập hợp như sau: Cho 
 tập hợp X = { A, B, C, D} có 4 phần tử. 
  Giải sử ta cần chọn 7 phần tử thuộc tập X, được phép chọn lặp lại và không 
 phân biệt trình tự trước sau của việc chọn. Mỗi cách chọn 7 phần tử như thế 
 được gọi là một tổ hợp lặp 4 chập 7. 
  Một cách tổng quát, ta gọi một tổ hợp lặp n chập k là một cách chọn k phần 
 tử được phép lặp lại trong n phần tử cho trước và không phân biệt thứ tự 
 đối với k phần tử được chọn. (k có thể lớn hơn n) 
1.3 Chỉnh hợp và tổ hợp suy rộng 
1.3.2 Tổ hợp có lặp (tt) 
a. Định nghĩa: 
 Một tổ hợp lặp chập k của một tập hợp n phần tử 
 là một bộ gồm k phần tử có thể lặp lại của n phần 
 tử đã cho. 
b. Định lý: 
 Số tổ hợp lặp chập k từ tập n phần tử bằng là: 
 k kk N ! với N=n+k-1 
 CCCn n k1 N 
 k!( N k )!
1.3 Chỉnh hợp và tổ hợp suy rộng 
 Ví dụ 1: Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két 
 đựng tiền gồm những tờ 1000đ, 2000đ, 5000đ, 10.000đ, 
 20.000đ, 50.000đ, 100.000đ. 
 Giả sử thứ tự mà các tờ tiền được chọn là không quan trọng, 
 các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 
 5 tờ. 
 Giải: 
  Vì ta không kể tới thứ tự chọn tờ tiền, 
  và vì ta chọn đúng 5 lần, 
  mỗi lần lấy một từ 1 trong 7 loại tiền. 
  Nên mỗi cách chọn 5 tờ giấy bạc này chính là một tổ hợp lặp 
 chập 5 từ 7 phần tử. 
 5 5
 Do đó số cần tìm là: CC 7 7 5 1 462
1.3 Chỉnh hợp và tổ hợp suy rộng 
  Ví dụ 2: Phương trình x1 + x2 + x3 = 15 có bao 
 nhiêu nghiệm không âm? 
  Giải: 
  Chúng ta nhận thấy mỗi nghiệm của phương trình ứng 
 với một cách chọn 15 phần tử từ một tập có 3 loại, 
 sao cho có x1 phần tử loại 1, x2 phần tử loại 2 và x3 
 phần tử loại 3 được chọn. 
  Vì vậy số nghiệm bằng số tổ hợp lặp chập 15 từ tập có 
 3 phần tử và bằng: 
 15 15
 CC3 3 15 1 136
BÀI TẬP 
 Bài tập 1: Chúng ta cần chọn một sinh viên toán 
 năm thứ 3 hay năm thứ 4 đi dự một hội nghị. Hỏi có 
 bao nhiêu cách chọn lựa một sinh viên như thế biết 
 rằng có 100 sinh viên toán học năm thứ 3 và 85 sinh 
 viên toán học năm thứ tư? 
 Bài tập 2: Một sinh viên có thể chọn một đề tài từ 
 một trong 3 danh sách các đề tài. Số đề tài trong 
 các danh sách đề tài lần lượt là 23, 15, 19. Hỏi sinh 
 viên có bao nhiêu cách chọn một đề tài. 
BÀI TẬP (tt) 
 Bài tập 3: Hỏi có bao nhiêu chuỗi bit khác nhau có 
 độ dài 8 (tức là gồm 8 bits)? 
 Bài tập 4: Giả sử ta phải đi từ một địa điểm A đến 
 một địa điểm C, ngang qua một địa điểm B. Để đi từ 
 A đến B ta có 8 cách đi khác nhau, và có 6 cách đi 
 từ B đến C. Hỏi có bao nhiêu cách để đi từ A đến C? 
BÀI TẬP (tt) 
 Bài tập 5: Một mã bao gồm 6 ký tự, trong đó gồm 3 mẫu tự rồi đến 
 3 ký số thập phân. Hỏi có bao nhiêu mã khác nhau? 
 Bài tập 6: Phương án đánh số điện thoại. 
 Giả sử một số điện thoại gồm 10 ký số được chia thành 3 nhóm: 2 
 nhóm gồm 3 ký số và một nhóm 4 ký số. 
 Do một số lý do nào đó, có một số hạn chế trên các ký số của số 
 điện thoại. Để xác định dạng hợp lệ của một số điện thoại. ta dùng 
 ký hiệu X để chỉ một ký số có thể lấy giá trị từ 0 đến 9, N để chỉ một 
 ký số từ 2 đến 9, và Y chỉ một ký số là 0 hoặc 1. 
 Chúng ta có 2 phương án để đánh số điện thoại: một phương án cũ 
 và một phương án mới. Theo phương án cũ, số điện thoại có dạng 
 NYX NNX XXXX; và theo phương án mới thì số điện thoại có dạng 
 NXX NXX XXXX. Hỏi số lượng số điện thoại khác nhau của mỗi 
 phương án là bao nhiêu? 
BÀI TẬP (tt) 
 Bài tập 7: Các ghế ngồi trong một hội trường sẽ 
 được ghi nhãn gồm một mẫu tự và một số nguyên 
 dương không lớn hơn 100. Hỏi số ghế tối đa có thể 
 được ghi nhãn khác nhau là bao nhiêu? 
 Bài tập 8: Mỗi người sử dụng trên một hệ thống 
 máy tính có một "password" dài từ 6 đến 8 ký tự, 
 trong đó mỗi ký tự là một chữ in hoa hoặc là một ký 
 số thập phân. Mỗi "password" phải có ít nhất một ký 
 số. Hỏi có bao nhiêu password khác nhau? 
BÀI TẬP (tt) 
 Bài tập 9: Trong tổng số 2504 sinh viên của một 
 khoa công nghệ thông tin, có 1876 theo học môn 
 ngôn ngữ lập trình Pascal, 999 học môn ngôn ngữ 
 Fortran và 345 học ngôn ngữ C. Ngoài ra còn biết 
 876 sinh viên học cả Pascal và Fortran, 232 học cả 
 Fortran và C, 290 học cả Pascal và C. Nếu 189 sinh 
 viên học cả 3 môn Pascal, Fortran và C thì trong 
 trường hợp đó có bao nhiêu sinh viên không học 
 môn nào trong 3 môn ngôn ngữ lập trình kể trên. 
BÀI TẬP (tt) 
 Bài tập 10: Một cuộc họp gồm 12 người tham dự 
 để bàn về 3 vấn đề. Có 8 người phát biểu về vấn đề 
 I, 5 người phát biểu về vấn đề II và 7 người phát 
 biểu về vấn đề III, 4 người phát biểu cả hai vấn đề I 
 và II, 6 người phát biểu cả hai vấn đề II và III, 2 
 người phát biểu về vấn đề I và 3. Ngoài ra, có đúng 
 1 người không phát biểu vấn đề nào. Hỏi nhiều lắm 
 là có bao nhiêu người phát biểu cả 3 vấn đề. 
BÀI TẬP (tt) 
 Bài tập 11: Chỉ ra rằng có ít nhất 4 người trong số 
 25 triệu người có cùng tên họ viết tắt bằng 3 chữ cái 
 sinh cùng ngày trong năm (không nhất thiết trong 
 cùng một năm). 
 Bài tập 12: Một tay đô vật tham gia thi đấu giành 
 chức vô địch trong 75 giờ. Mỗi giờ anh ta có ít nhất 
 một trận đấu, nhưng toàn bộ anh ta có không quá 
 125 trận. Chứng tỏ rằng có những giờ liên tiếp anh 
 ta đã đấu đúng 24 trận. 
Bài 11 
 Giải: (bảng chữ cái có 26 chữ --> có 
 17576 tên viết tắt có thể của một 
 người 
 --> có 25 triệu/17576=1422 người 
 cùng tên. 
 --> có 1422/365=4 người cùng tên 
 sinh cùng ngày) 
 BÀI TẬP (tt) 
  Bài Tập 13: Trong một cuộc lấy ý kiến về 7 vấn đề, 
 người được hỏi ghi vào một phiếu trả lời sẵn bằng 
 cách để nguyên hoặc phủ định các câu trả lời tương 
 ứng với 7 vấn đề đã nêu. Chứng minh rằng với 1153 
 người được hỏi luôn tìm được 10 người trả lời giống 
 hệt nhau. 
Giải: 2 trạng thái trả lời cho 7 câu hỏi, tổng 
số là 27=128. [1153/128]=10, theo nguyên 
lý Dirichlet. 
BÀI TẬP (tt) 
 Bài tập 14: Trong kỳ thi kết thúc học phần toán học 
 rời rạc có 10 câu hỏi. Có bao nhiêu cách gán điểm 
 cho các câu hỏi nếu tổng số điểm bằng 100 và mỗi 
 câu ít nhất được 5 điểm. 
 Bài tập 15: Phương trình x1 + x2 + x3 + x4 + x5 = 
 21 có bao nhiêu nghiệm nguyên không âm? 
 Bài tập 16: Có bao nhiêu xâu khác nhau có thể lập 
 được từ các chữ cái trong từ MISSISSIPI, yêu cầu 
 phải dùng tất cả các chữ?