Chỉnh Hợp Lặp Chỉnh Hợp Không Lặp - Tài Liệu Text - 123doc

1. Trang chủ >
2. Giáo Dục - Đào Tạo >
3. Cao đẳng - Đại học >

Chỉnh hợp lặp Chỉnh hợp không 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 (3.41 MB, 197 trang )

Chương 2: Bài toán đếm và bài toán tồn tại

2.3. ĐẾM CÁC HOÁN VỊ TỔ HỢP

2.3.1. Chỉnh hợp lặp

Định nghĩa 1. Một chỉnh hợp lặp chập k của n phần tử là bộ có thứ tự gồm k thành phần lấytừ n phần tử của tập đã cho. Như vậy, một chỉnh hợp lặp chập k của n phần tử có thể xem là phần tử của tích đề các Akvới A là tập đã cho. Theo nguyên lý nhân, số các tất cả các chỉnh hợp lặp chập k của n sẽ là nk.Ví dụ 1. Tính số hàm từ tập có k phần tử vào tập có n phần tử. Giải: Biểu diễn mỗi hàm bằng một bộ k thành phần, trong đó thành phần thứ i là ảnh củaphần tử thứ i 1=i=k. Mỗi thành phần được lấy ra từ một trong n giá trị. Từ đó suy ra số hàm là số bộ k thành phần lấy từ n thành phần bằng nk.Ví dụ 2. Từ bảng chữ cái tiếng Anh có thể tạo ra được bao nhiêu xâu có độ dài n. Giải: Bảng chữ cái tiếng Anh gồm 26 kí tự [‘A’..’Z’], số các xâu có độ dài n được chọn từ26 chữ cái chính là chỉnh hợp lặp n của 26 phần tử và bằng 26n.Ví dụ 3. Tính xác xuất lấy ra liên tiếp được 3 quả bóng đỏ ra khỏi bình kín chứa 5 quả đỏ, 7quả xanh nếu sau mỗi lần lấy một quả bóng ra lại bỏ nó trở lại bình.Giải: Số kết cục có lợi để ta lấy ra liên tiếp 3 quả bóng đỏ là 53vì có 5 quả đỏ ta phải lấy 3 quả chú ý vì có hồn lại. Tồn bộ kết cục có thể để lấy ra ba quả bóng bất kỳ trong 12 quả bónglà 123. Như vậy, xác suất để có thể lấy ra 3 quả bóng đỏ liên tiếp là 53123.

2.3.2. Chỉnh hợp không lặp

Định nghĩa 2. Chỉnh hợp không lặp chập k của n phần tử là bộ có thứ tự gồm k thành phầnlấy ra từ n phần tử đã cho. Các phần tử không được lặp lại. Để 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àycó n khả năng chọn. Mỗi thành phần tiếp theo những khả năng chọn giảm đi 1 vì khơng được lấy lặp lại. Tới thành phần thứ k có n-k + 1 khả năng chọn. Theo nguyên lý nhân ta có số chỉnh hợplặp k của tập hợp n phần tử ký hiệu là Pn, k được tính theo cơng thức:1 ..1 ,k nn kn nn kn P− =+ −− =Ví dụ 1. Tìm số hàm đơn ánh có thể xây dựng được từ tập k phần tử sang tập n phần tử. Giải: Số hàm đơn ánh từ tập k phần tử sang tập n phần tử chính là Pn,k.Ví dụ 2. Giả sử có tám vận động viên chạy thi. Người về nhất sẽ được nhận huy chươngvàng, người về nhì nhận huy chương bạc, người về ba nhận huy chương đồng. Hỏi có bao nhiêu cách trao huy chương nếu tất cả các kết cục đều có thể xảy ra.Giải: Số cách trao huy chương chính là số chỉnh hợp chập 3 của tập hợp 8 phần tử. Vì thếcó P8,3 = 8.7.6 = 336 cách trao huy chương. 28Chương 2: Bài tốn đếm và bài tốn tồn tạiVí dụ 3. Có bao nhiêu cách chọn 4 cầu thủ khác nhau trong đội bóng gồm 10 cầu thủ đểtham gia các trận đấu đơn.Giải: Có P10,4 = 10.9.8.7 = 5040 cách chọn.

2.3.3. Hoán vị

Xem Thêm

Tài liệu liên quan

• Giao trinh Toan roi rac toan tap.pdf
  • 197
  • 4,510
  • 41

Tải bản đầy đủ (.pdf) (197 trang)

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

(3.41 MB) - Giao trinh Toan roi rac toan tap.pdf-197 (trang) Tải bản đầy đủ ngay ×