5 Chỉnh Hợp Lặp, Hoán Vị Lặp Và Tổ Hợp Lặp - Tài Liệu Text - 123doc

1. Trang chủ >
2. Thạc sĩ - Cao học >
3. Khoa học tự nhiên >

5 Chỉnh hợp lặp, hoán vị lặp và tổ hợp lặp

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (355.69 KB, 72 trang )

Định lý 1.5.1 Số các chỉnh hợp lặp chập r từ tập n phần tử bằng n rChứng minhRõ ràng có n cách chọn một phần tử từ tập n phần tử cho mỗi mộttrong r vị trí của chỉnh hợp khi cho phép lặp. Vì vậy theo quy tắc nhân, cón r chỉnh hợp lặp chập r từ tập n phần tử.Chú ý.Số các chỉnh hợp lặp chập p của n phần tử là n p .Như vậy chỉnh hợp có lặp lại là khi giữa các phần tử yếu tố thứ tự làcốt lõi, còn yếu tố khác biệt không quan trọng.1.5.2 Hoán vị lặpTrong bài toán đếm, một số phần tử có thể giống nhau. Khi đó cầnphải cẩn thận, tránh đếm chúng hơn một lần.Định lý 1.5.2 Số hoán vị của n phần tử trong đó có n1 phần tử như nhauthuộc loại 1, có n2 phần tử như nhau thuộc loại 2, … và có n k phần tửn!như nhau thuộc loại k bằng n !n !...n ! .12kChứng minhĐể xác định số hoán vị trước tiên chúng ta nhận thấy có Cnn cách giữ1n1 số cho n1 phần tử loại 1, còn lại n – n1 chỗ trống.nSau đó có Cn− n cách đặt n2 phần tử loại 2 vào hoán vị, còn lại n – n 1 – n221chỗ trống.Tiếp tục đặt các phần tử loại 3, loại 4 , … , loại k – 1 vào chỗ trống trongnhoán vị. Cuối cùng có Cn− n −n −...− n cách đặt nk phần tử loại k vào hoán vị.k12k −1Theo quy tắc nhân tất cả các hoán vị có thể là:7Cnn1 .Cnn−2 n1 ...Cnn−k n1 −...−nk −1 =n!n1 !n2 !...nk !1.5.3 Tổ hợp lặpMột tổ hợp lặp chập k của một tập hợp là một cách chọn không cóthứ tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểunày là một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Dođó có thể là k > n.Định lý 1.5.3 Số tổ hợp lặp chập k từ tập n phần tử bằng Cnk+ k −1 .Chứng minhMỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng mộtdãy n−1 thanh đứng và k ngôi sao. Ta dùng n − 1 thanh đứng để phân cáchcác ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i củatập xuất hiện trong tổ hợp.Mỗi dãy n − 1 thanh và k ngôi sao ứng với một tổ hợp lặp chập k củan phần tử . Do đó mỗi dãy ứng với một cách chọn k chỗ cho k ngôi sao từn + k − 1 chỗ chứa n – 1 thanh và k ngôi sao. Đó là điều cần chứng minh.Chú ý.Số tổ hợp có lặp chập p của n làpn −1pC n = C n+ p −1 = C n+ p −1 .Tổ hợp có lặp lại khi một phần tử có thể xuất hiện nhiều lần và thứ tựcủa các phần tử không cần để ý.8CHƯƠNG 2 - MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢNChương 1 đã trình bày lý thuyết cơ bản của toán tổ hợp. Dựa trên cơsở lý thuyết đó trong chương này khóa luận sẽ tập trung trình bày một sốbài toán tổ hợp cơ bản, phù hợp với học sinh THPT khi tham gia các kì thitốt nghiệp, cao đẳng, đại học.2.1 Một số bài toán đếm không lặpTrong các bài toán về phép đếm không lặp, mỗi phần tử cần đếm chỉcó thể xuất hiện tối đa một lần. Để giải các bài toán đếm không lặp ngườita sử dụng hai quy tắc chính của phép đếm là quy tắc cộng và quy tắc nhân,cũng như sử dụng hai phương pháp đếm trực tiếp hoặc đếm gián tiếp .2.1.1 Bài toán lập sốBài 1:Cho tập hợp các chữ số X = { 1, 2,…,9} . Từ tập hợp X có thể lậpđược bao nhiêu số chẵn có 6 chữ số khác nhau từng đôi một.Giải:Gọi số cần lập là n = a1a2a3a4a5a6 , ai ∈ X .Vì n là số chẵn nên a6 ∈ { 2; 4;6;8} có 4 cách chọn. Còn a1, a2 , a3 , a4 , a5là một bộ phân biệt có thứ tự được chọn từ X do đó nó là một chỉnh hợpchập 5 của 8 (Trừ đi số a6 đã chọn). Có A85 cách chọn.Vậy có 4. A85 = 224 số thỏa mãn bài toán.Bài 2:9Cho tập hợp các chữ số X = { 0, 1, 2,…,7} . Từ tập hợp X có thể lậpđược bao nhiêu số tự nhiên có năm chữ số khác nhau từng đôi một thỏamãn :a. Là số chẵn.b. Là số tiến (chữ số sau lớn hơn chữ số đứng trước nó).Giải:Gọi số cần lập là n = a1a2 a3 a4 a5 , ai ∈ X , a1 ≠ 0 .Vì n là số chẵn nên a5 ∈ { 0, 2, 4, 6} .Trường hợp 1: Nếu a5 = 0 thì a5 có 1 cách chọn.Khi đó a1 , a2 , a3 , a4 là một bộ phân biệt có thứ tự được chọn từ X\{0}do đó nó là một chỉnh hợp chập 4 của 7. Có A74 cách chọn.Vậy có A74 =840 số thỏa mãn bài toán.Trường hợp 2: Nếu a5 được chọn từ {2, 4, 6} thì a5 có 3 cách chọn.a1 được chọn từ tập X\{0, a5 } nên a1 có 6 cách chọn.a2 , a3 , a4 là một bộ phân biệt thứ tự được chọn từ X\{ a1 , a5 } do đónó là một chỉnh hợp 6 chập 3. Có A63 cách chọn.Vậy có 3.6. A63 =2160 số thỏa mãn bài toán.Vậy số các số chẵn gồm 5 chữ số phân biệt hình thành từ X là:840+2160=3000 số.b) Vì n là số tiến nên a1 < a2 < ... < a5 và do a1 ≠ 0nên 1 ≤ a1 < a2 < ... < a5 .Mỗi cách chọn ra 5 chữ số thì chỉ có 1 cách sắp xếp từ nhỏ đến lớn.Vậy số các số cần tìm là số cách chọn ra 5 chữ số từ tập X \ {0} .Vậy có C75 =21 số thỏa mãn điều kiện.10

Xem Thêm

Tài liệu liên quan

• ĐỀ tài một số bài TOÁN tổ hợp đếm
  • 72
  • 5,227
  • 8
• Châm cứu học t t thích tâm ấn
  • 183
  • 0
  • 0
• Chăm sóc khi bé bị bệnh nhiều tác giả
  • 144
  • 0
  • 0
• Đề ôn thi vào 10 chuyên toán
  • 54
  • 1
  • 16
• Cơ thể người nhiều tác giả
  • 147
  • 0
  • 0
• Để lành bệnh tự nhiên trần viết hoài đồng
  • 275
  • 0
  • 0
• Giải đáp một số thắc mắc khi nuôi con bằng sữa mẹ nguyễn thị kim hưng
  • 29
  • 0
  • 0
• Giới tính theo cuộc đời gilbert tordjman
  • 185
  • 0
  • 0
• Giới tính tuổi hoa j p maslova
  • 65
  • 151
  • 0
• Hẹp đường mật phạm thị thu thủy
  • 5
  • 271
  • 1
• HIỆP KHÍ đạo koichi tohei
  • 108
  • 0
  • 0

Tải bản đầy đủ (.doc) (72 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(1.89 MB) - ĐỀ tài một số bài TOÁN tổ hợp đếm -72 (trang) Tải bản đầy đủ ngay ×