Chương 1: Các kiến thức cơ sở

Chia sẻ: Bùi Ngọc Thành | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

129
lượt xem 13
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các cấu hình tổ hợp, Các phương pháp lựa chọn phần tử hoặc bộ các phần tử trong tập hợp hữu hạn theo các cách khác nhau. → Là cơ sở để xây dựng thuật toán vét cạn, các thuật toán sinh phần tử mới, các thuật toán lựa chọn phương án tối ưu, v..v…

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 1: Các kiến thức cơ sở

CHƯƠNG 1. CÁC KIẾN THỨC CƠ SỞ 1.1. Các khái niệm cơ bản 1.2. Lý thuyết tổ hợp 1.3. Hai nguyên lý cơ bản 1.4. Lý thuyết số và các hệ đếm 1.5. Bài tập
LÝ THUYẾT TỔ HỢP 1. Khái niệm. 2. Chỉnh hợp lặp. 3. Chỉnh hợp không lặp. 4. Hoán vị. 5. Tổ hợp. 6. Tổ hợp lặp. 7. Hoán vị của tập hợp có các phần tử giống nhau. 8. Một số công thức tổ hợp. 9. Một số ví dụ.
KHÁI NIỆM Lý thuyết tổ hợp nghiên cứu: Các cấu hình tổ hợp, 1. Các phương pháp lựa chọn phần tử hoặc bộ các phần tử trong 2. tập hợp hữu hạn theo các cách khác nhau. → Là cơ sở để xây dựng thuật toán vét cạn, các thuật toán sinh phần tử mới, các thuật toán lựa chọn phương án tối ưu, v..v… Một số bài toán: Các bài toán đếm, 1. Các bài toán về sự tồn tại, 2. Các phương pháp biểu diễn các cấu hình tổ hợp… 3.
CHỈNH HỢP LẶP KN: Chỉnh hợp lặp chập k của tập n phần tử là một cách sắp xếp có thứ tự k phần tử lấy từ tập gồm n phần tử đã cho, mỗi phần tử có thể được lấy lặp lại. KH: Số chỉnh hợp lặp chập k của tập n phần tử An  n k k Ví dụ 1:  Tập A = {1, 2, 3, 4, 5} n = 5. Các bộ (1, 1, 2) ; (1, 2, 1) ; (2, 3, 5) và (2, 3, 2 ) là các chỉnh hợp lặp chập 3 từ 5 phần tử.
CHỈNH HỢP LẶP  Ví dụ 2. • Từ tập  = { a, b, c } có thể đặt được bao nhiêu tên biến có độ dài 4 ký tự? • Giải: Mỗi tên biến có 4 ký tự được chọn từ tập  là một bộ 4 phần tử được lấy từ tập  vậy có số tên biến có 4 ký tự được chọn từ  là N()xN()xN()xN() = 3x3x3x3 = 81.  Ví dụ 3. • Các dãy nhị phân có độ dài n là một chỉnh hợp lặp chập n từ hai phần tử {0, 1}. Vậy theo công thức chỉnh hợp lặp chập n từ 2 phần tử là : 2n.
CHỈNH HỢP KHÔNG LẶP KN: Chỉnh hợp không lặp chập k từ n phần tử (gọi tắt là chỉnh hợp chập k) là một cách sắp xếp có thứ tự k phần tử của tập n phần tử, mỗi phần tử không được lấy lặp lại. KH: Số chỉnh hợp chập k của n phần tử: n! P  n.(n  1)(n  2).....(n  k  1)  k (n  k )! n
CHỈNH HỢP KHÔNG LẶP Ví dụ 4. • Tập A = {1, 2, 3, 4, 5} các bộ (2, 3, 5); (2, 5, 3) là các chỉnh hợp không lặp chập 3 từ 5 phần tử, còn các bộ (1, 1, 2) ; (1, 2, 1) ; và (2, 3, 2) không phải là chỉnh hợp không lặp chập 3 từ 5 phần tử, nhưng mặt khác đó lại là chỉnh hợp lặp chập 3 từ 5 phần tử. Ví dụ 5. • Có bao nhiêu số có 4 chữ số khác nhau được chọn từ các số sau B = {1,3, 4, 5, 7, 6}? • Giải: Số các số có 4 chữ số khác nhau được chọn từ tập B là số chỉnh hợp chập 4 của 6: 6! 6!    6.5.4.3  360 (số) 4 P • (6  4)! 2! 6
HOÁN VỊ KN: Hoán vị của n phần tử khác nhau là một cách sắp xếp có thứ tự n phần tử đó. KH: Số hoán vị của n phần tử P  n.(n  1)(n  2).....1  n ! n Ví dụ 6:  Có bốn người rủ nhau đi chụp ảnh là Anh, Bắc, Cúc, Dương. Hãy tính xem có bao nhiêu kiểu ảnh chụp mà tất cả bốn người đứng thành một hàng ? P4  4! (kiểu)  Số kiểu ảnh =
TỔ HỢP KN:Tổ hợp chập k từ n phần tử là cách chọn không phân biệt thứ tự k phần tử lấy từ tập n phần tử đã cho, mỗi phần tử không được lấy lặp lại. KH: Số tổ hợp chập k của n phần tử n!  k C (n  k )!k ! n Từ công thức trên có thể suy ra rằng: n! n!  Cn k   k n C (n  k )!k ! k !(n  k )! n
TỔ HỢP Ví dụ 7:  Với tập A = {1, 2, 3, 4, 5} thì các bộ (1, 2, 3 ), (1, 2, 4) là các tổ hợp chập 3 từ 5 phần tử, còn các bộ (1, 1, 2 ), (2, 3, 2 ) không phải là tổ hợp chập 3 từ 5 phần tử đã cho. Theo định nghĩa hai bộ (2, 3, 5 ), (3, 5, 2) chỉ được tính là một tổ hợp chập 3. Ví dụ 8:  Có 12 đội bóng tham dự giải chuyên nghiệp quốc gia, các đội thi đấu vòng tròn một lượt. Hỏi có bao nhiêu trận đấu được tổ chức ?  Giải : Mỗi trận đấu là một cặp 2 đội được chọn từ 12 đội đã cho, không kể đến thứ tự và phải khác nhau, vậy số trận đấu là tổ hợp chập 2 từ 12 : 12!/(10!.2!) = 66 trận
TỔ HỢP LẶP KN: Tổ hợp lặp chập k từ n phần tử là một bộ gồm k phần tử không phân biệt thứ tự, mỗi phần tử có thể được lấy lặp lại từ n phần tử đã cho. KH: Số tổ hợp lặp chập k từ n phần tử là (n  k  1)! R C  k k n  k 1 k!(n  1)! n
TỔ HỢP LẶP Ví dụ 9:  Phương trình sau có bao nhiêu nghiệm nguyên không âm: x1 + x2 + x3 = 11  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 11 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, x3 phần tử loại 3 được chọn. Vì vậy số nghiệm bằng số tổ hợp chập 11 từ tập gồm 3 phần tử. Theo công thức trên ta có 13.12 R3 1  C1131  C13  C13   78 1 11 11 2 1.2
HOÁN VỊ CỦA TẬP HỢP CÓ CÁC PHẦN TỬ GIỐNG NHAU KN: Giả sử có n phần tử trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2, …, và nk phần tử giống nhau thuộc loại k. Khi đó số cách sắp xếp n phần tử được tính như sau: n Cn 1 Số cách chọn n1 chỗ loại 1 là  n2 Cn  n1 Số cách chọn n2 chỗ loại 2 là   .... KH: Số hoán vị từ n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, n2 phần tử như nhau thuộc loại 2, …, và nk phần tử như nhau thuộc loại k là: (n  n1 )! n! n  nk n Cn 1 Cn  n ...Cn  n ... 2 ....n k 1 n1 ! (n  n1 )! n2 ! ( n  n1  n2 )! 1 1 ( n  n1  ...  nk 1 )! n!  nk !0! n1 ! n2 !...nk !
HOÁN VỊ CỦA TẬP HỢP CÓ CÁC PHẦN TỬ GIỐNG NHAU Ví dụ 10 :  Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp lại các chữ cái của từ SUCCESS?  Giải: Từ SUCCESS có 7 chữ cái (3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E). Do vậy câu trả lời không phải là số hoán vị của 7 chữ cái được!!! Theo công thức hoán vị của tập hợp có các phần tử giống nhau ta có: 7!4!3!1! 7! CCCC    420 3 1 2 1 7 4 3 1 3!4!1!3!2!1!1!0! 3!2!1!1!0!
MỘT SỐ CÔNG THỨC TỔ HỢP Cn  Cn  1 0 n 1. Cn  Cn k k n 2. Cn  Cn 1  Cn1 k k k (hằng đẳng thức Pascal) 3. n ( x  y)   Cin x i y n i n (nhị thức Newton) 4. i 0 k   CnCmi k ik (hằng đẳng thức Vandermonde) Cn  m 5. i 0
MỘT SỐ CÔNG THỨC TỔ HỢP  Chứng minh: k   CnCmi k ik Cn  m i 0  Giải :  VT của đẳng thức là số tập con có k phần tử của tập có (n + m) phần tử.  Giả sử có tập  = a1, a2, …, an, an+1, …, an+m}= 1  2 , trong đó 1 = a1, a2, …, an và 2 = an+1, an+2, …, an+m, như vậy để chọn tập con có k phần tử của  ta có thể chọn như sau:  Chọn i phần tử từ tập 1 → có C(n,i) cách chọn  Sau đó chọn k – i phần tử từ tập 2 → có C(m,k-i) cách chọn → có C(n,i) .C(m,k-i) cách chọn ứng với mỗi i từ 0 đến k.  Như vậy, số cách chọn là: k  CnCm1  Cn Cm 2  Cn 1Cm   CnCmi  Cm  ...  Cn k k 1k 2k k 1 k ik Cn  m i 0
BÀI TẬP 1. Cho n là số nguyên dương, chứng minh n n C 2  k n ( 1)k Cn  0 k c. a. n k 0 k 0 n  kCn  n2 n -1 k b. k 1 2. Có tất cả bao nhiêu hoán vị của tập hợp {a,b,c,d,e,f} với phần tử cuối cùng bằng a? 3. Một tập hợp có 100 phần tử, có bao nhiêu tập con có nhiều hơn 2 phần tử? 4. Tìm hệ số của x101y99 trong khai triên của (2x – 3y)200 ? 5. Có bao nhiêu xâu nhị phân chứa đúng tám số 0 và mười số 1, và ngay sau mỗi số 0 nhất thiết là một số 1?
BÀI TẬP 6. Có bao nhiêu cách chọn 8 đồng tiền xu từ hộp chứa 100 đồng một xu giống nhau và 80 đồng năm xu giống nhau? 7. Phương trình : x1 + x2 + x3 + x4 + x5 =21 có bao nhiêu nghiệm nguyên không âm sao cho: a. x1 ≥ 1? b. xi ≥ 2 với i = 1, 2, 3, 4, 5 c. 0 ≤x1≤ 10? d. *0 ≤x1 ≤ 3 và 1≤ x2 ≤4 và x3≥ 15? 8. Bất đẳng thức x1 + x2 + x3≤ 21 có bao nhiêu nghiệm nguyên không âm?
BÀI TẬP 9. Có bao nhiêu xâu nhị phân khác nhau nếu chúng được bắt đầu bằng bít 1 và chứa thêm 3 bít 1 nữa, nó còn chứa tất cả 12 bít 0 và sau mỗi bít 1 có ít nhất hai bít 0? 10. Có bao nhiêu xâu khác nhau có thể lập được từ chữa cái trong từ MISSISSIPPI, yêu cầu phải dùng tất cả các chữ?