Đề tài Phép đếm

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINHĐẠI HỌC CÔNG NGHỆ THÔNG TIN * Nội dung: I. Các nguyên lí II. Hoán vị, Chỉnh hợp và Tổ hợp. Nhị thức Newton III. Hoán vị lặp, Chỉnh hợp lặp và Tổ hợp lặp. Đa thức Newton IV. Đệ quy * I. Các nguyên lí: 1. Nguyên lý cộng Giả sử để làm công việc A có 2 phương pháp Phương pháp 1 có n cách làm Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n+m. * Ví dụ: Nam có 3 áo tay dài, 5 áo tay ngắn. Để chọn 1 cái áo thì Nam có mấy cách? Đáp án: Áp dụng nguyên lí cộng thì: Phương pháp 1: Có 3 cách chọn áo dài tay Phương pháp 2: Có 5 cách chọn áo ngắn tay Vậy để chọn một áo thì Nam có 3 + 5 cách chọn. I. Các nguyên lí: * 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước Bước 1 có n cách làm Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m I. Các nguyên lí: * Ví dụ: Đáp án: Có 3.2 =6 con đường đi từ A đến C I. Các nguyên lí: * Ví dụ: Cho tập X ={1,2,3,4,5,0}. Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Đáp án: Gọi số có 3 chữ số là abc TH1: c=0. Khi đó, c có 1 cách chọn a có 5 cách chọn ( a € X\{0} ) TH1 có 1.4.5 = 20. b có 4 cách chọn ( b € X\{ a, 0}) TH2 . c≠0. Khi đó c có 2 cách chọn a có 4 cách chọn ( a € X\{c, 0} ) TH2 có 2.4.4 = 32. b có 4 cách chọn ( b € X\{ a, c}) Vậy có 20+32 = 52. I. Các nguyên lí: * 3. Nguyên lý chuồng bồ câu (Derichlet) Nguyên lý Dirichlet do nhà toán học người Đức là Dirichlet đề xuất từ thế kỉ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ mệnh đề gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý  “chuồng chim bồ câ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ì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim. * I. Các nguyên lí: 3. Nguyên lý chuồng bồ câu (Derichlet) 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ừ [n/ k] bồ câu trở lên. Ví dụ: Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày I. Các nguyên lí: * Ví dụ: Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng bằng 10 Đáp án: Ta lập các chuồng như sau: {1,9} {2,8} {3,7} {4,6} {5} Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm I. Các nguyên lí: * I. Các nguyên lí: * I. Các nguyên lí: * II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton 2.1 Hoán vị Bài toán: Trong giờ học môn Giáo dục quốc phòng, một tiểu đội học sinh gồm 10 người được xếp thành một hàng dọc. Hỏi có bao nhiêu cách xếp? * 2.1 Hoán vị Định nghĩa hoán vị : Cho tập hợp A gồm 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à 1 hoán vị của n phần tử. Áp dụng vào bài toán: A= { 10 học sinh } ; n =10 >0 Số cách sắp xếp = hoán vị của 10h/s  II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton * 2.1 Hoán vị Định lý: Số các Hoán vị của một tập hợp có n phần tử là: Pn= n!=n(n-1)....2.1 Quy ước : 0! = 1 AD: số cách sắp xếp = P10 = 10! = 10.9….2.1 =? VD: Sắp xếp 6 học sinh vào 6 cái ghế. Hỏi có bao nhiêu cách sắp xếp? Đáp án: P6 = 6!=1.2.3…6=720 II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton * 2.1 Hoán vị Ví dụ 1: Cho A ={a,b,c}. Khi đó A có các hoán vị sau: abc, acb, bac, bca, cab, cba Ví dụ 2: 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 từ tập X? Đáp án: 5! II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton * 2.2 Chỉnh hợp Bài toán: Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu 11m . Huấn luyện viên của mỗi đội cần trình với trọng tài một danh sách sắp thứ tự 5 cầu thủ trong số 11 cầu thủ của đội để tham gia đá. Có bao nhiêu cách sắp xếp danh sách thứ tự 5 cầu thủ? II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton * 2.2 Chỉnh hợp Định nghĩa chỉnh hợp : Cho A là tập hợp gồm n phần tử (khác nhau). Mỗi bộ gồm k phần tử(0 Bất kỳ 5 viên bi b> 5 viên trong đó có 2 bi xanh Chỉnh Hợp: Cho tập hợp :{1,2,3,4,5,6} số cách lập thành số có 4 chữ số khác nhau Nhị Thức NewTon: Cho tìm hệ số của Khai triển tổng quát : = Ở đây k =2 : => hệ số của = II. Hoán vị, tổ hợp và chỉnh hợp. Công thức nhị thức Newton * III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * 3.1 Hoán vị lặp Ví dụ: Có bao nhiêu cách sắp xếp 3 cuốn sách toán, 1 cuốn sách lý, 2 cuốn sách hóa và 1 cuốn tin học vào giá sách có 7 chỗ? Toán: 3 Lý: 1 Hóa: 2 Tin học: 1 Tổng: 7 III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * 3.2 Tổ hợp lặp Định nghĩa: Có k loại vật, mỗi loại vật có nhiều vật giống hệt nhau (không phân biệt) Có k loại vật -> III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * 3.3 Đa thức Newton Công thức: III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * 3.3 Đa thức Newton Ví dụ 1: III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * 3.3 Đa thức Newton Ví dụ 2: III. Hoán vị lặp, tổ hợp lặp và Công thức Đa thức Newton * IV. ĐỆ QUY Một hệ thức đệ quy tuyến tính cấp k là một hệ thức có dạng: Trong đó: ak ≠ 0, a1,…, ak-1 là các hệ số thức {fn} là một dãy số thực cho trước {xn} là dãy ẩn nhận các giá trị thực a0xn + a1xn-1 + … + akxn-k = fn * a0xn + a1xn-1 + … + akxn-k = 0 IV. ĐỆ QUY * NGHIỆM TỔNG QUÁT Mỗi dãy { xn } thõa (1) được gọi là một nghiệm của (1). Nhận xét rằng mỗi nghiệm { xn } của (1) được hoàn toàn xác định bởi k giá trị ban đầu x0, x1,…, xk-1. Họ dãy số { xn = xn(C1, C2,…, Ck) } phụ thuộc vào k họ tham số C1, C2,…, Ck được gọi là nghiệm tổng quát của (1) nếu mọi dãy của họ này đều là nghiệm của (1). IV. ĐỆ QUY * IV. ĐỆ QUY * MỤC ĐÍCH GIẢI HỆ THỨC Giải một hệ thức đệ quy là đi tìm nghiệm tổng quát của nó. Nếu hệ thức đệ quy có kèm theo điều kiện ban đầu, ta phải tìm nghiệm riêng thõa điều kiện ban đầu đó. IV. ĐỆ QUY * Ví dụ 1: Một cầu thang có n bậc. Mỗi bước đi gồm 1 hoặc 2 bậc. Gọi xn là số cách đi hết cầu thang. Tìm một hệ thức đệ quy cho xn. IV. ĐỆ QUY * Với n = 1, ta có x1 = 1. Với n = 2, ta có x2 = 2. Với n > 2, để khảo sát xn, ta chia thành 2 trường hợp loại trừ lẫn nhau: Trường hợp 1: Bước đầu tiên gồm 1 bậc. Khi đó cầu thang trong trường hợp này là xn-1. IV. ĐỆ QUY * Trường hợp 2: Bước đầu tiên gồm 2 bậc. Khi đó cầu thang còn n-2 bậc nên số cách đi hết cầu thang trong trường hợp này là xn-2. Theo nguyên lý cộng, số cách đi hết cầu thang là xn-1 + xn-2. Do đó ta có: Xn = Xn-1 + Xn-2 Vậy ta có hệ thức đệ quy tuyến tính thuần nhất cấp 2: Xn = Xn-1 + Xn-2 X1 = 1, X2 = 2 IV. ĐỆ QUY * Ví dụ 2: Bài toán tháp Hà Nội: Có 3 cọc A, B, C và n đĩa (có lỗ để đặt vào cọc) với đường kính đôi một khác nhau. Nguyên tắc đặt đĩa vào cọc là: mỗi đĩa chỉ được chồng lên đĩa lớn hơn nó. Ban đầu, cả n đĩa được đặt chồng lên nhau ở cọc A, hai cọc B và C để trống. Vấn đề đặt ra là chuyển cả n đĩa ở cọc A sang cọc C (có thể qua trung gian cọc B), mỗi lần chỉ chuyển một đĩa. Gọi xn là số lần chuyển đĩa. Tìm một hệ thức đệ quy cho xn. IV. ĐỆ QUY * Hanoi Tower IV. ĐỆ QUY * Với n = 1 ta có x1 = 1. Với n > 1, trước hết ta chuyển n-1 đĩa bên trên sang cọc B qua trung gian cọc C (giữ nguyên đĩa thứ n dưới cùng ở cọc A). Số lần chuyển đĩa thứ n từ cọc A sang cọc C. Cuối cùng ta chuyển n-1 đĩa từ cọc B sang cọc C. Số lần chuyển n-1 đĩa đó lại là xn-1. IV. ĐỆ QUY * Như vậy số lần chuyển toàn bộ n đĩa từ A sang C là: Xn-1 + 1 + Xn-1 = 2Xn-1 + 1 Nghĩa là xn = 2xn-1 +1, ta có hệ thức đệ quy tuyến tính không thuần nhất cấp 1: Xn = 2Xn-1 + 1 X1 = 1 IV. ĐỆ QUY * Hệ thức đệ quy tuyến tính thuần nhất Xét hệ thức đệ quy tuyến tính thuần nhất Phương trình đặc trưng của (2) là phương trình bậc k định bởi: a0xn + a1xn-1 + … + akxn-k = 0 k - a1k-1 - … - ak = 0 IV. ĐỆ QUY * Trường hợp k = 1 Phương trình đặc trưng (*) trở thành:  - a1 = 0 nên có nghiệm là 0 = a1 Khi đó, (2) có nghiệm tổng quát là: xn = C 0n IV. ĐỆ QUY * Ví dụ: Hệ thức đệ quy là một hệ thức đệ quy tuyến tính thuần nhất cấp 1. 2xn – 3xn-1 = 0 x1 = 1 IV. ĐỆ QUY * Phương trình đặc trưng: 2 - 3 = 0 có nghiệm là: 0 = 3/2 Do đó nghiệm tổng quát là: xn = C(3/2)n IV. ĐỆ QUY * IV. ĐỆ QUY * Trường hợp k=2: Phương trình đặc trưng (*) trở thành: 2 - a1 - a2 = 0 (*) Nếu (*) có hai nghiệm thực phân biệt 1 và 2 thì (2) có nghiệm tổng quát là: xn = A1n + B2n IV. ĐỆ QUY * b) Nếu (*) có nghiệm kép thực 0 thì (2) có nghiệm tổng quát là: Xn = (A + nB) 0n IV. ĐỆ QUY * c) Nếu (*) có hai nghiệm phức liên hợp được viết dưới dạng lượng giác: thì (2) có nghiệm tổng quát là: IV. ĐỆ QUY * Hệ thức đệ quy tuyến tính không thuần nhất: Hệ thức ĐQ thuần nhất tương ứng: * IV. ĐỆ QUY a0xn + a1xn-1 + … + akxn-k =fn a0xn + a1xn-1 + … + akxn-k = 0 (1) (2) Phương trình đặc trưng của (2): * a0k + a1k-1 + … + ak = 0 NGHIỆM TỔNG QUÁT CỦA (1) = NGHIỆM TỔNG QUÁT CỦA (2) + MỘT NGHIỆM RIÊNG CỦA (1) IV. ĐỆ QUY Tìm nghiệm riêng của (1) khi fn có dạng đặc biệt: fn = βnPn(n), trong đó Pr(n) là một đa thức bậc r theo n; β là hằng số fn = fn1 + fn2 + … + fns, (fn1, fn2, …, fns thuộc dạng xét phía trên) * IV. ĐỆ QUY Dạng fn = βnPn(n) có 3 trường hợp nhỏ: β không là nghiệm của phương trình đặc trưng β là nghiệm đơn của phương trình đặc trưng β là nghiệm kép của phương trình đặc trưng * IV. ĐỆ QUY TH β không là nghiệm của phương trình đặc trưng thì (1) có một nghiệm riêng dạng: * Xn = βnQr(n) IV. ĐỆ QUY TH β là nghiệm đơn của phương trình đặc trưng thì (1) có một nghiệm riêng dạng: * Xn = nβnQr(n) IV. ĐỆ QUY TH β là nghiệm kép của phương trình đặc trưng thì (1) có một nghiệm riêng dạng: * Xn = n2βnQr(n) Qr(n) = Arnr +Ar-1nr-1 + … + A0n0 IV. ĐỆ QUY Để xác định các hệ số của Qr(n) ta cần thế xn, xn-1,…, xn-k vào (1) và cho n nhận r+1 giá trị nguyên nào đó hoặc đồng nhất các hệ số tương ứng ở hai vế để được 1 hệ phương trình. Các hệ số trên là nghiệm của hệ phương trình này. * IV. ĐỆ QUY Dạng fn = fn1 + fn2 + … + fns Bằng cách như trên, ta tìm được nghiệm riêng xni của hệ thức đệ quy: a0xn + a1xn-1 + … + akxn-k = fni Khi đó xn = xn1 +xn2 + … + xns là một nghiệm riêng của (1) * IV. ĐỆ QUY *