zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Khoa học tự nhiên

Khóa luận tốt nghiệp đại học: Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán sơ cấp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:44

Báo xấu

2
lượt xem 1
download

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

Khóa luận tốt nghiệp đại học "Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán sơ cấp" trình bày các nội dung chính sau: Một số khái niệm cơ bản về tập hợp và các nguyên lý đếm cơ bản; Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán tổ hợp.

Chủ đề:

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

Lưu

Nội dung Text: Khóa luận tốt nghiệp đại học: Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán sơ cấp

UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA TOÁN ---------- ĐẶNG THỊ THÙY TRANG ỨNG DỤNG NGUYÊN LÝ BÙ TRỪ VÀ PHÂN HOẠCH TẬP HỢP GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Quảng Nam, tháng 5 năm 2015
UBND TỈNH QUẢNG NAM TRƯỜNG ĐẠI HỌC QUẢNG NAM KHOA TOÁN ---------- KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC ỨNG DỤNG NGUYÊN LÝ BÙ TRỪ VÀ PHÂN HOẠCH TẬP HỢP GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP Sinh viên thực hiện ĐẶNG THỊ THÙY TRANG MSSV: 2111010158 CHUYÊN NGÀNH: SƯ PHẠM TOÁN KHÓA: 2011 – 2015 Cán bộ hướng dẫn ThS. DƯƠNG THỊ THU THÚY MSCB: T34-15111-26747 Quảng Nam, tháng 5 năm 2015
LỜI CẢM ƠN Qua 4 năm học tập và rèn luyện tại trường Đại Học Quảng Nam, dưới sự dạy dỗ của quý Thầy Cô giáo, tôi đã tích lũy cho mình những kiến thức và kinh nghiệm quý báu cả về chuyên môn lẫn nghiệp vụ. Khóa luận này chính là thành quả quan trọng của quá trình đó. Khóa luận được hoàn thành dưới sự hướng dẫn tận tình và chu đáo của Cô giáo ThS. Dương Thị Thu Thúy. Qua đây, với tất cả sự kính trọng và lòng biết ơn sâu sắc tôi xin được gửi đến Cô lời cảm ơn chân thành nhất. Tôi cũng xin được cảm ơn toàn thể quý Thầy Cô đã giảng dạy lớp ĐHSP Toán K11( khóa 2011-2015) trường Đại Học Quảng Nam, đặc biệt là quý Thầy Cô khoa Toán trường Đại Học Quảng Nam, những người không những cho tôi kiến thức mà còn quan tâm động viên, nhiệt tình giúp đỡ tôi trong quá trình học tập cũng như trong thời gian thực hiện khóa luận. Mặc dù, bản thân tôi đã rất cố gắng trong quá trình học tập và nghiên cứu đề tài của khóa luận tốt nghiệp, nhưng do thời gian có hạn, khả năng nghiên cứu và kiến thức còn nhiều hạn chế nên khóa luận của tôi vẫn không thể tránh khỏi những thiếu sót nhất định. Rất mong nhận được sự đóng góp chân thành từ quý Thầy Cô giáo để khóa luận của tôi được hoàn thiện hơn nữa. Tôi xin chân thành cảm ơn! Tam Kỳ, tháng 05 năm 2015 Sinh viên thực hiện Đặng Thị Thùy Trang
MỤC LỤC Phần 1. MỞ ĐẦU ................................................................................................. 1 1.1. Lý do chọn đề tài. .......................................................................................... 1 1.2. Mục tiêu của đề tài. ....................................................................................... 1 1.3. Đối tượng và phạm vi nghiên cứu. ............................................................... 1 1.4. Nhiệm vụ nghiên cứu. ................................................................................... 2 1.5. Phương pháp nghiên cứu.............................................................................. 2 1.6. Đóng góp của đề tài . ..................................................................................... 2 1.7. Cấu trúc đề tài. .............................................................................................. 2 Phần 2. NỘI DUNG NGHIÊN CỨU. ................................................................. 3 Chương 1. MỘT SỐ KIẾN THỨC LIÊN QUAN ĐẾN TẬP HỢP VÀ NGUYÊN LÝ ĐẾM CƠ BẢN. ............................................................................ 3 1.1. Tập hợp và nguyên lý đếm cơ bản. .............................................................. 3 1.1.1. Tập hợp. ...................................................................................................... 3 1.1.2. Nguyên lý đếm cơ bản. ............................................................................... 3 1.1.2.1. Quy tắc cộng. ........................................................................................... 3 1.1.2.2. Quy tắc nhân. ........................................................................................... 4 1.2. Giải tích tổ hợp. ............................................................................................. 6 1.2.1. Hoán vị. ....................................................................................................... 6 1.2.2. Hoán vị lặp không hạn chế. ....................................................................... 6 1.2.3. Hoán vị lặp hạn chế. ................................................................................... 7 1.2.4. Chỉnh hợp k vật từ n vật ( k ≤ n). ............................................................. 7 1.2.5. Tập con k phần tử từ tập n phần tử ( k ≤ n). ........................................... 7 1.2.6. Tổ hợp lặp. .................................................................................................. 8 1.3. Quy nạp toán học. ......................................................................................... 9 1.4. Nguyên lý Dirichlet. ...................................................................................... 9 1.5. Nguyên lý bù trừ.......................................................................................... 10 1.5.1. Nhận xét. .................................................................................................. 10 1.5.2. Nguyên lý bù trừ....................................................................................... 10 1.6. Phân hoạch tập hợp - Số Stirling loại hai và số Bell. ............................... 12
2.1. Ứng dụng nguyên lý bù trừ giải toán. ....................................................... 15 2.1.1. Bài toán mở rộng biểu đồ Vent phổ thông bằng nguyên lý bù trừ. ..... 15 2.1.2. Bài toán đếm số......................................................................................... 20 2.1.2.1 Bài toán đếm số thỏa mãn các tính chất số học. .................................. 20 2.1.2.2 Bài toán đếm số bộ nghiệm nguyên. ..................................................... 24 2.1.3. Bài toán Bernoulli – Euler. ...................................................................... 27 2.2. Ứng dụng phân hoạch tập hợp giải toán. .................................................. 30 PHẦN 3. KẾT LUẬN VÀ KIẾN NGHỊ. .......................................................... 37 1. Kết luận ........................................................................................................... 37 2. Kiến nghị ......................................................................................................... 37 PHẦN 4. TÀI LIỆU THAM KHẢO. ................................................................ 38
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Phần 1. MỞ ĐẦU 1.1. Lý do chọn đề tài. Tổ hợp có một vị trí đặc biệt trong toán học không chỉ là những đối tượng để nghiên cứu mà còn đóng vai trò như một công cụ đắc lực của các mô hình rời rạc của giải tích, đại số… Trong các kì thi học sinh giỏi quốc gia, thi toán sinh viên giữa các trường đại học và cao đẳng, thi Olympic khu vực và quốc tế các bài toán tổ hợp xuất hiện là một thách thức lớn cho các thí sinh. Rất nhiều bài toán hay và khó được giải một cách khá gọn và đẹp bằng cách sử dụng kiến thức về tổ hợp. Dù bao gồm nhiều bài toán hóc búa nhưng bản chất của lý thuyết tổ hợp chỉ quy về 4 dạng cơ bản : bài toán tồn tại, bài toán đếm, bài toán liệt kê và bài toán tối ưu tổ hợp. Tất cả các bài tập đều được nằm trong 4 bài toán chính này. Để giải 4 dạng toán cơ bản này ta có thể sử dụng rất nhiều các nguyên lý và phương pháp đếm chẳng hạn: nguyên lý bù trừ, nguyên lý quy nạp và đếm số lượng phần tử của một tập hợp hữu hạn … Nhưng phù hợp và gần gũi với chương trình toán ở phổ thông là nguyên lý bù trừ và phương pháp phân hoạch tập hợp. Áp dụng tốt hai phương pháp này học sinh có thể giải được một số bài toán khó và thường có dạng không mẫu mực của giải tích tổ hợp. Cho đến nay, ngoài một số tài liệu và sách tham khảo chuyên sâu về toán rời rạc chủ yếu để phục vụ cho tin học, việc giải bài toán tổ hợp theo phương pháp gần gũi với phổ thông chưa có nhiều tài liệu đề cập đến một cách trọn vẹn và chi tiết. Vì các lý do trên tôi xin chọn đề tài “Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán sơ cấp” làm đề tài khóa luận tốt nghiệp. 1.2. Mục tiêu của đề tài. - Làm rõ thế nào là nguyên lý bù trừ và phân hoạch tập hợp. - Thể hiện được những ứng dụng của nguyên lý bù trừ và phân hoạch tập hợp vào giải một số bài toán ở phổ thông. 1.3. Đối tượng và phạm vi nghiên cứu. - Đối tượng nghiên cứu: Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán tổ hợp. GVHD: ThS. Dương Thị Thu Thúy Trang 1
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang - Phạm vi nghiên cứu: Các bài tập trong chương trình phổ thông, trong đề thi học sinh giỏi các cấp. 1.4. Nhiệm vụ nghiên cứu. Nghiên cứu về nguyên lý bù trừ và phân hoạch tập hợp, từ đó đưa ra những ứng dụng vào giải một số bài toán tổ hợp. 1.5. Phương pháp nghiên cứu. - Nghiên cứu tài liệu, đọc hiểu tài liệu. - Phân tích, tổng hợp các kiến thức. - Trao đổi, thảo luận với chuyên gia. 1.6. Đóng góp của đề tài . Khóa luận sau khi hoàn thành sẽ là một tài liệu tham khảo giúp học sinh giải các bài toán giải tích tổ hợp khó và thường có dạng không mẫu mực . 1.7. Cấu trúc đề tài. Khóa luận gồm phần mở đầu, kết thúc và hai chương: - Chương 1: Một số khái niệm cơ bản về tập hợp và các nguyên lý đếm cơ bản. - Chương 2: Ứng dụng nguyên lý bù trừ và phân hoạch tập hợp giải một số bài toán tổ hợp. GVHD: ThS. Dương Thị Thu Thúy Trang 2
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Phần 2. NỘI DUNG NGHIÊN CỨU. Chương 1. MỘT SỐ KIẾN THỨC LIÊN QUAN ĐẾN TẬP HỢP VÀ NGUYÊN LÝ ĐẾM CƠ BẢN. 1.1. Tập hợp và nguyên lý đếm cơ bản. 1.1.1. Tập hợp. Trong toán học, tập hợp có thể hiểu tổng quát là một sự tụ tập của một số gọi là các phần tử của tập hợp. Tập hợp là một khái niệm nền tảng và quan trọng của toán học hiện đại. Ngành toán học nghiên cứu về tập hợp là lý thuyết tập hợp. Trong lý thuyết tập hợp, người ta xem tập hợp là một khái niệm nguyên thủy, không định nghĩa. Nó tồn tại theo các tiên đề được xây dựng một cách chặt chẽ. Khái niệm tập hợp là nền tảng để xây dựng các khái niệm khác như số, hình, hàm số... trong toán học. 1.1.2. Nguyên lý đếm cơ bản. 1.1.2.1. Quy tắc cộng. Nếu có m1 cách chọn đối tượng x1 , m2 cách chọn đối tượng thứ x2 ,…, mn cách chọn đối tượng xn và nếu cách chọn đối tượng xi không trùng với bất kỳ cách chọn đối tượng x j nào ( i  j ,i, j  1, n ) thì có m1  m2  ...  mn cách chọn một trong các đối tượng đã cho. Định lý 1.1. Cho n tập hữu hạn X i (i  1, n) với X i  mi , X i  X j  , i  j . Khi đó n n n n số cách chọn một phần tử thuộc tập  X i là  X i và  Xi   Xi . i 1 (1.1) i 1 i 1 i 1 Chứng minh. Ta chứng minh quy nạp theo n với n  2 . Nếu n  2 thì X 1  X 2  X 1  X 2  X 1  X 2  X 1  X 2 ,(vì X i  X j   ) . k k Giả sử (1.1) đúng với n  k ,(k  2) , tức là X i   Xi . i 1 i 1 k 1 k 1 Ta sẽ chứng minh (1.1) đúng với n  k  1 , nghĩa là X i   Xi i 1 i 1 GVHD: ThS. Dương Thị Thu Thúy Trang 3
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Thật vậy, ta có: X 1  X 2  ...  X k  X k 1  ( X 1  X 2  ...  X k )  X k 1 . Vì X i  X j  ,  i  j , nên: ( X 1  X 2  ...  X k )  X k 1  ( X 1  X k 1 )  ( X 2  X k 1 )  ...  ( X k  X k 1 )  Vậy X 1  X 2  ...  X k  X k 1  ( X 1  X 2  ...  X k )  X k 1  ( X 1  X 2  ...  X k )  X k 1 k =  Xi  X k 1 i 1 k 1   Xi i 1 k 1 k 1 Suy ra  Xi   Xi . i 1 i 1 Theo nguyên lý quy nạp toán học, quy tắc cộng là đúng với mọi n  , n2. 1.1.2.2. Quy tắc nhân. Nếu tồn tại tương ứng 1-1 giữa các cặp phần tử của các tập hữu hạn X và Y thì X và Y có cùng số phần tử. Nếu có m1 cách chọn đối tượng x1 , sau đó với mỗi cách chọn đối tượng x1 như thế có m2 cách chọn đối tượng thứ x2 , sau đó với mỗi cách chọn x1 và x2 như thế có m3 cách chọn đối tượng x3 ,…, cuối cùng, với mỗi cách chọn x1 , x2 ,...xn1 như thế có mn cách chọn đối tượng xn , thì có m1m2 ...mn cách chọn dãy các đối tượng “ x1 rồi x2 rồi x3 … rồi xn ”. Định lý 1.2. Giả sử có n tập hữu hạn X i , i  1, n , X i  mi , Chọn một bộ phận n phần tử ( a1 , a2 ,..., an ) với ai  X i . Khi đó số cách chọn khác nhau là n X 1  X 2  ...  X n và X 1  X 2  ...  X n =  mi . (1.2) i 1 GVHD: ThS. Dương Thị Thu Thúy Trang 4
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Chứng minh. Ta chứng minh (1.2) bằng phương pháp quy nạp theo n với n  2 như sau. Với n  2 ta có X 1  m1, X 2  m2 . Giả sử  X 1  a1 , a2 ,..., am1  và   X 2  b1 , b 2 ,..., b m2 thì: X 1  X 2  (a i , b j ) :1  i  m1 ,1  j  m2 , ai  X 1 , b j  X 2  . Ta viết X 1  X 2 dưới dạng bảng như sau: (a1 , b1 ) (a1 , b 2 )...(a1 , b m2 ) (a 2 , b1 ) (a 2 , b 2 )...(a 2 , b m2 ) … … … (a m1 , b1 ) (a m1 , b 2 )...(a m1 , b m2 ) Đặt Ei  (a i , b1 ),(a i , b 2 ),...,(a i , b m ) :1  i  m1  Ei  m2 . 2 Ta có X 1  X 2  E1  E2  ...  Em 1 với Ei  E j  , i  j . Theo quy tắc m1 cộng ta có: X 1  X 2  E1  E2  ...  Em   Ei  m1m2 . 1 i 1 Vậy công thức (1.2) đúng cho trường hợp n  2 . Giả sử (1.2) đúng với trường hợp n  k , (k  2) tức là X 1  X 2  ...  X k  m1.m2 ...mk . Ta chứng minh (1.2) đúng với trường hợp n  k  1 , nghĩa là: X 1  X 2  ...  X k  X k 1  m1.m2 ...mk mk 1 . Thật vậy, xét một phần tử bất kỳ  a1 , a2 ,..., ak , ak 1  của tích Descarter X 1  X 2  ...  X k  X k 1 . Đặt    a1 , a2 ,..., ak , ak 1  . Rõ ràng giữa tập hợp các bộ có dạng  a1 , a2 ,..., ak , ak 1  và tập hợp các cặp có dạng  , ak 1  có tương ứng 1-1. Vậy có bao nhiêu bộ  a1 , a2 ,..., ak , ak 1  thì có bấy nhiêu cặp  , ak 1  . Nếu ta ký hiệu tập hợp tất cả các  là X thì ta có thể nói rằng tập hợp X 1  X 2  ...  X k  X k 1 có bao nhiêu phần tử thì tập hợp X X k 1 có bấy nhiêu phần tử, tức là: X 1  X 2  ...  X k  X  X k 1 . GVHD: ThS. Dương Thị Thu Thúy Trang 5
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Theo chứng minh cho trường hợp n  2 ta có: X  X k 1  X X k 1 . Theo cách dựng thì X chính là tích Descarter X 1  X 2  ...  X k . Áp dụng giả thiết quy nạp ta có: X  X k 1  X X k 1  X 1  X 2  ...  X k  X k 1  m1.m2 ...mk mk 1 Vậy X 1  X 2  ...  X k  X k 1  m1.m2 ...mk mk 1 . Theo nguyên lý quy nạp toán học, công thức (1.2) đúng với mọi n  , n2. 1.2. Giải tích tổ hợp. 1.2.1. Hoán vị. Định nghĩa 1.1. Cho tập hữu hạn X  a1, a2 ,...an  và một số tự nhiên k  n . Khi đó: i. Bộ k phần tử  ai1 , ai 2 ,..., aik  , aij  X được gọi là bộ thứ tự nếu đổi vị trí các phần tử ta được bộ một bộ mới. Ngược lại, bộ k phần tử  ai1, ai 2 ,..., aik  , aij  X được gọi là bộ không có tính thứ tự. ii. Bộ k phần tử  ai1 , ai 2 ,..., aik  , aij  X được gọi là bộ không lặp nếu aij  ail , j , l  1,..., k , j  l . Ngược lại, bộ k phần tử  ai1 , ai 2 ,..., aik  , aij  X được gọi là bộ có lặp. Định nghĩa 1.2. Một hoán vị của m phần tử đã cho là một bộ có thứ tự gồm m phần tử, trong đó mỗi phần tử có mặt đúng một lần. Số tất cả các hoán vị của một tập hợp gồm m phần tử cho trước kí hiệu Pm . Theo quy tắc nhân, ta có: Pm  m! 1.2.2. Hoán vị lặp không hạn chế. Nếu muốn sắp xếp m vật từ k loại vật khác nhau (các vật cùng loại giống hệt như nhau) thì sẽ có k cách chọn vật thứ nhất, k cách chọn vật thứ hai,… , k cách chọn vật thứ m . Do đó có k m cách khác nhau. GVHD: ThS. Dương Thị Thu Thúy Trang 6
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang 1.2.3. Hoán vị lặp hạn chế. Có k loại vật khác nhau, loại 1 có m1 vật, loại 2 có m2 vật,…, loại k có mk vật; và tầng số vật sẽ là m   m1  m2  mk  . Nếu coi m vật này là khác nhau thì sẽ có m! cách sắp xếp, nhưng trong mỗi cách sắp xếp như vậy m1 phần tử loại 1 có thể hoán vị theo m1 ! cách, m2 phần tử loại 2 có thể hoán vị theo m2 ! cách, … , mk phần tử loại k có thể hoán vị theo mk ! cách. m! Do đó, số cách sắp xếp chỉ còn m1 !m2 !...!mk ! 1.2.4. Chỉnh hợp k vật từ n vật ( k ≤ n). Định nghĩa 1.3. 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 thành phần không được lặp lại. Ta thường ký hiệu Ank để chỉ số chỉnh hợp không lặp chập k của n phần tử. Chỉnh hợp không lặp thường được gọi tắt là chỉnh hợp. Để xây dựng một 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 khả năng chọn. Mỗi thành phần tiếp theo, số khả năng chọn giảm đi một so với thành phần đứng trước. Từ đó, theo quy tắc nhân, số n! chỉnh hợp không lặp chập k của n là Ank  n(n  1)...(n  k  1)  . (n  k)! Để tồn tại chỉnh hợp cần phải thỏa mãn k  n . Ta quy ước Ank  0 nếu k  n. 1.2.5. Tập con k phần tử từ tập n phần tử ( k ≤ n). Định nghĩa 1.4. Một tổ hợp chập k của n phần tử cho trước là một bộ không có thứ tự gồm k phần tử khác nhau lấy từ n phần tử đã cho ( k  n ). Từ định nghĩa ta thấy rằng một tổ hợp chập k của một tập hợp gồm n phần tử cho trước chính là một tập con gồm k phần tử của tập gồm n phần tử cho trước. Như vậy số tất cả các tổ hợp chập k của n phần tử đã cho chính là số cách chọn ra k phần tử từ một tập hợp gồm n phần tử cho trước theo cách chọn n không lặp và không thứ tự. Ký hiệu: Cnk hoặc   . k  GVHD: ThS. Dương Thị Thu Thúy Trang 7
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Ta có nhận xét rằng với mỗi tổ hợp chập k của n phần tử, có thể thành lập được k ! chỉnh hợp chập k của n phần tử. Suy ra: 1 k n! Cn  k An  k! k !(n  k )! Nếu cho tập hữu hạn X có X  n . Khi đó số tập con có k phần tử ( 0  k  n ) của X sẽ là Cnk . Từ định nghĩa ta suy ra được bốn tính chất của tổ hợp: k An  C  k n k!  Cn  C n  1 0 n  Cn  Cn  k k n (0  k  n)   Cn  Cnk11  Cn 1 . k k 1.2.6. Tổ hợp lặp. Giả sử có một tập k phần tử gồm k1 phần tử thuộc loại 1, k2 phần tử thuộc loại 2,…, kn phần tử thuộc loại n (k1  k2  ...  kn  k , n  k ) . Tập hợp này có thể biểu diễn trên đường thẳng bằng k điểm ngăn cách bởi n– 1 dấu | (để phân cách các phần tử khác loại nhau): bắt đầu bằng k1 điểm (biểu thị các phần tử loại 1) đi theo bởi 1 dấu |, kế đến k2 điểm (biểu thị các phần tử loại 2) đi theo bởi 1 dấu |, …., rồi sau cùng là kn điểm (biểu thị các phần tử loại n). Có thể có một vài k  0 nên có thể cũng sẽ xảy ra trường hợp một số dấu | đi liền với nhau. • • • •…• • | • • • •…• | • …… | • • •…• • k1 điểm k2 điểm …… kn điểm Những cách chọn khác nhau tập k phần tử sẽ cho ra các cách sắp xếp khác nhau k điểm và n  1 dấu | trên đường thẳng. Do đó số các tập k phần tử thuộc nhiều nhất n loại khác nhau ( n  k ) sẽ bằng số cách sắp xếp k  n  1 phần tử trong đó k phần tử cùng một loại và n  1 phần tử thuộc loại khác. Theo hoán vị (k  n  1)! lặp hạn chế số này bằng: hay bằng Ckk n 1 . k !.(n  1)! GVHD: ThS. Dương Thị Thu Thúy Trang 8
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang 1.3. Quy nạp toán học. Định lý 1.3. Cho no là một số nguyên dương và P  n  là một mệnh đề có nghĩa với mọi số tự nhiên n  no . Nếu: (1) P  no  là đúng. (2) Nếu P  k  đúng thì P  k  1 cũng đúng với mọi số tự nhiên k  no . Thì mệnh đề P  n  đúng với mọi số tự nhiên n  no . Chứng minh. Ta sẽ chứng minh bằng phản chứng. Giả sử ngược lại, mệnh đề khẳng định P  n  trong định lí không đúng với một số tự nhiên n  no nào đó. Nghĩa là tồn tại số tự nhiên m  no , P  m  đúng. Ta lấy số tự nhiên m nhỏ nhất mà P  m  không đúng (điều này thực hiện được do tiên đề thứ tự). Theo điều kiện (1) ta có bất đẳng thức m  no , từ đó suy ra m  1  no . Từ bất đẳng thức vừa lập và cách chọn số tự nhiên m suy ra P  m  1 là đúng, nhưng nó không kéo theo được P  m  đúng cho số tiếp theo m  ( m  1)  1 . Điều này trái với giả thiết (2). Như vậy, điều giả sử là sai và định lí được chứng minh. 1.4. Nguyên lý Dirichlet. Định lý 1.4. Nếu phân phối hết m đồ vật vào n cái hộp thì luôn tồn tại một hộp m  1 có ít nhất là 1   đồ vật.  n    Chứng minh.  m  1 Giả sử trái lại mọi cái hộp đều không có đến   1 đồ vật, thì số đồ  n    m  1 vật trong mỗi hộp đều nhỏ hơn hoặc bằng  cái.  n   GVHD: ThS. Dương Thị Thu Thúy Trang 9
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang  m  1 Từ đó suy ra tổng số đồ vật không vượt quá n.   m  1 đồ vật (vô  n   lý). Vậy giả thuyết chứng minh là sai, nguyên lý Dirichlet mở rộng được chứng minh. 1.5. Nguyên lý bù trừ. 1.5.1. Nhận xét. Khi hai công việc có thể làm đồng thời, ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Ta có thể phát biểu nguyên tắc đếm này bằng ngôn ngữ tập hợp. Cho 2 tập A, B . Ta có : A B  A  B  A B . Tương tự: Cho A1 , A2 , A3 là 3 tập hợp bất kỳ. Khi đó, ta có: A1  A2  A3  A1  A2  A3  ( A1  A2 )  A3  A 1  A2  A1  A2  A3  ( A1  A3 )  ( A2  A3 )  A1  A2  A3  ( A1  A2  A2  A3  A1  A3 )  A1  A2  A3 3   Ak  (1) Ai  Aj  (1) 2 1 31 k 1  1 i  j 3  1 i  j  k 3 Ai  Aj  Ak 1.5.2. Nguyên lý bù trừ. Định lý 1.5. Khi ta cho n tập X 1 , X 2 , ..., X n , thì: n X 1  X 2  ...  X 3   (1) X (n, k ) k 1 (1.3) k 1 Trong đó, X (n, 0)  X X (n, k )   1i1 ...ik  n X i1  X i2  ...  X ik GVHD: ThS. Dương Thị Thu Thúy Trang 10
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Chứng minh. Với n=2, ta có : X1  X 2  X1  X 2  X1  X 2 . Giả sử (1.3) đúng đến n, tức là: n X  X  ...  X   X k  (1) 2  1  X i  X j  ... 1 2 n k 1 1 i  j  n (1) k  1  X i1  X i2  ...  X ik  ...  X  X  ...  X 1 i1 ... ik  n 1 2 n Ta chứng minh (1.3) đúng với n+1, ta có : X 1  X 2  ...  X n  X n 1  ( X 1  X 2  ...  X n )  X n 1  X 1  X 2  ...  X n  X n 1  ( X 1  X 2  ...  X n )  X n 1 Ta có : X 1  X 2  ...  X n n   X k  ...  (1) k  1  n 1 X i1  X i2  ...  X ik  ...  (1) X  X  ...  X k 1 1 i1 ... ik  n 1 2 n Và ( X 1  X 2  ...  X n )  X n 1  ( X 1  X n 1 )  ( X 2  X n 1 )  ...  ( X n  X n 1 )  ( X 1  X n 1 )  ( X 2  X n 1 )  ...  ( X n  X n 1 ) n   X k  X n 1  ...  (1) k 1.  X i1  X i2  ...  X ik  X n 1  ...  k 1 1i1 ...ik  n (1) n 1 X 1  X 2  ...  X n  X n 1 Khi đó : n n 1  k 1 X k  X n 1   X k : k 1 n   1 i  j  n X i  X j   X k  X n 1   k 1  1i  j  n 1 Xi  X j ; (1) k  1  X i1  X i2  ...  X ik  X n 1 1i1 ...ik  n  (1) k  1i1 ...ik  n 1 X i1  X i2  ...  X ik ; GVHD: ThS. Dương Thị Thu Thúy Trang 11
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang (1) n  1 X  X  ... X  X  (1) n X  X  ... X  X 1 2 n n 1 1 2 n n 1 . n Vậy ta có: X  X  ...  X   (1) X (n, k ) , k 1 1 2 n k 1 với X (n, k )   1 i1 ... ik  n X i1  X i2  ...  X ik . Định lý 1.6. Công thức Sieve . Cho X 1 , X 2 ,..., X n là n tập hợp. Khi đó: ___ ___ ___ n X 1  X 2  ...  X n   (1) k X (n, k ) k 0 Chứng minh. Theo tính chất tập hợp, ta có: ___ ___ ___ __________________________ X 1  X 2  ...  X n  X 1  X 2  ...  X n n  X  X 1  X 2  ...  X n  X   (1) k 1X (n, k ) k 1 n n  X (n, 0)   (1) k X (n, k )   (1) k X (n, k ) k 1 k 0 1.6. Phân hoạch tập hợp - Số Stirling loại hai và số Bell. Định nghĩa 1.5. Cho A là một tập hữu hạn có n phần tử. Một phân hoạch của A thành k phần (khối) là một hệ gồm các tập con không rỗng A1 , A2 ,..., A k của A thỏa mãn hai tính chất sau: i. A1  A2  ...  A k  A . ii. Ai  A j   i  j , i, j  1, 2,..., k  . Định nghĩa 1.6. Mỗi tập con Ai được gọi là phần (khối) của phép phân hoạch. Số tất cả các phân hoạch thành k phần của A được gọi là Stirling loại hai và được ký hiệu là Sn,k . Định nghĩa 1.7. Dễ thấy rằng S n,k  0 nếu k  n và với mọi n  1 ta có: Sn ,0  0 , S n ,1  1 , S n ,n  1 . Ta cũng thừa nhận rằng S0,0  1 vì theo định nghĩa họ rỗng các khối là phân hoạch của tập rỗng. GVHD: ThS. Dương Thị Thu Thúy Trang 12
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Số Bn  Sn,0  Sn ,1  ...  Sn,n được gọi là số Bell thứ n . Như vậy, số Bell thứ n là số tất cả các phân hoạch của tập A lực lượng n . Định lý 1.7. Ta có Sn 1,k  k .Sn ,k  Sn ,k 1 , (k  n) Chứng minh. Xét tập bất kì có n  1 phần tử, chẳng hạn tập A   x1 , x2 ,..., xn1 Theo định nghĩa có S n1,k phần tử tập A thành k khối. Mặt khác ta có thể chia tập B tất cả các phân hoạch trên thành hai tập con B1 và B2 rời nhau như sau: B1 gồm tất cả các phân hoạch tập A thành k khối, trong đó có một khối là  xn1 , còn B2 bao gồm tất cả các phân hoạch tập A thành k khối, trong đó không có một khối nào là  xn1 . Khi đó mỗi phân hoạch thuộc B1 sẽ chia tập  x1 , x2 ,..., xn  thành  k  1 khối và có Sn,k 1 cách chia như thế. Do đó B1  Sn ,k 1 . Nếu  xn1 không là một khối thì xn1 sẽ nằm trong một khối với ít nhất một phần tử khác của A . Vì có Sn,k cách phân hoạch tập  x1 , x2 ,..., xn  thành k khối và xn1 có thể thuộc một khối bất kì trong k khối đó, nên ta có tất cả là k .S n ,k cách phân hoạch tập A thành k khối sao cho  xn1 không là một khối của phân hoạch. Suy ra B2  k .Sn ,k . Vì B  B1  B2 và B1  B2   nên theo quy tắc cộng ta có: S n1,k  B  B1  B2  k .S n ,k  S n ,k 1 . Dựa vào hệ thức truy hồi trên, ta tính được các số S n ,k và Bn . Sau đây là bảng cho cụ thể với một vài giá trị n đầu tiên. GVHD: ThS. Dương Thị Thu Thúy Trang 13
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Bảng các số Stirling loại hai và số Bell: S n ,k k 0 k 1 k 2 k 3 k 4 k 5 k 6 k 7 k 8 Bn n0 1 1 n 1 0 1 1 n2 0 1 1 2 n3 0 1 3 1 5 n4 0 1 7 6 1 15 n5 0 1 15 25 10 1 52 n6 0 1 31 90 65 15 1 203 n7 0 1 63 301 350 140 21 1 877 n8 0 1 127 966 1701 1050 266 28 1 4140 GVHD: ThS. Dương Thị Thu Thúy Trang 14
Khóa luận tốt nghiệp SVTH: Đặng Thị Thùy Trang Chương 2. ỨNG DỤNG NGUYÊN LÝ BÙ TRỪ VÀ PHÂN HOẠCH TẬP HỢP GIẢI MỘT SỐ BÀI TOÁN TỔ HỢP. 2.1. Ứng dụng nguyên lý bù trừ giải toán. 2.1.1. Bài toán mở rộng biểu đồ Vent phổ thông bằng nguyên lý bù trừ. Phương pháp giải bài toán bằng biểu đồ ven là phương pháp đi đến lời giải một cách tường minh và thuận lợi nhờ mô tả mối liên hệ giữa các tập hợp trong bài toán trực quan bằng biểu đồ. Phương pháp này sẽ phức tạp và khó khăn hơn nếu số tập hợp tăng lên cao. Các bài toán này được giải một cách ngắn gọn và dễ hiểu khi ta mở rộng biểu đồ ven bằng cách áp dụng nguyên lý bù trừ . Bài 1. Lớp toán học rời rạc có 25 sinh viên giỏi tin học, 13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán và tin học. Hỏi lớp có bao nhiêu sinh viên nếu mỗi sinh viên hoặc giỏi toán hoặc giỏi tin học hoặc giỏi cả hai môn. Lời giải. Gọi A là tập các sinh viên giỏi tin học. B là tập các sinh viên giỏi toán. Khi đó A  B là tập sinh viên giỏi cả toán và tin học. Vì mỗi sinh viên trong lớp hoặc giỏi toán hoặc giỏi tin học hoặc giỏi cả hai môn nên ta có tổng số sinh viên trong lớp là A  B . Do vậy, ta có: A  B  A  B  A  B = 25 + 13 – 8 = 30 (sinh viên). Bài 2. Trong hội khỏe Phù Đổng có 100 vận động viên đăng kí dự thi. Mỗi vận động viên được đăng kí một hoặc hai trong ba môn: ném tạ, bơi lội hoặc đấu cờ vua. Kết quả có 30 vận động viên chỉ thi đấu cờ vua, 53 người đăng kí thi ném tạ GVHD: ThS. Dương Thị Thu Thúy Trang 15

CÓ THỂ BẠN MUỐN DOWNLOAD

TL.01: Bộ Tiểu Luận Triết Học

207 tài liệu

1487 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright ©2025 TaiLieu.VN. All rights reserved.