Giải tích tổ hợp

Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

309
lượt xem 109
download

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

Nguyên lý nhân: Một công việc được chia làm k giai đoạn. Cón 1cách hoàn thành giai đoạn 1, Có n2 cách hoàn thành giai đoạn 2, . . . , Có nk cách hoàn thành giai đoạnk. Số cách thực hiện công việc

Chủ đề:

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

Lưu

Nội dung Text: Giải tích tổ hợp

GIẢI TÍCH TỔ HỢP 1.1 Nguyên lý nhân: Một công việc được chia làm k giai đoạn. Có n1 cách hoàn thành giai đoạn 1, Có n2 cách hoàn thành giai đoạn 2, . . . , Có nk cách hoàn thành giai đoạn k. Số cách thực hiện công việc n = n1.n2 ...nk Ví dụ. Có tất cả bao nhiêu xâu nhị phân có độ dài bằng 4?
1.2 Hoán vị: Cho A là tập hợp khác ∅ có số phần tử là n. Một hoán vị của A là một cách sặp xếp có thứ tự các phần tử của A. Mệnh đề. Số hoán vị của tập A có n phần tử bằng n!. Ví dụ. Có bao nhiêu cách sắp 5 người vào một bàn dài có 5 chỗ ngồi.
1.3 Chỉnh hợp. Cho A là tập hợp có n phần tử. Một cách sắp xếp có thứ tự m phần tử trong n phần tử của tập hợp A được gọi là một chỉnh hợp chập m của n phần tử Mệnh đề. Số chỉnh hợp châp m của n phần tử là: m n! An = (n - m)! Ví dụ có bao nhiêu cách sắp xếp 5 cuốn sách khác nhau vào kệ sách có 15 ô.
1.4 Chỉnh hợp lặp. Một bộ thứ tự gồm m phần tử không nhất thiết khác nhau cùa 1 tập hợp A gồm n phần tử được gọi là một chình hợp lặp chập m cùa n phần tử, Mệnh đề. Số chỉnh hợp lặp chập m của n phận từ bằmg: An = n m . m Ví dụ. Cho A là tập có n phần tử tính số tập con của nó
1.5 Tổ hợp. Một cách chọn m phần tử trong một tập hợp gồm n phần tử được gọi là một tổ hợp chập m cùa n phần tử. Mệnh đề. Số tổ hợp chập m của n phần tử bằng: m n! Cn = m!(n - m)! Ví dụ. Có bao nhiêu cách chia 12 cuốn sách cho bốn học sinh mỗi em được 3 cuốn
1.6 Tổ hợp lặp: Một nhóm có m phần tử không phân biệt thứ tự, có thể trùng nhau được gọi là một tổ hợp lặp chập m của n phần tử. Mệnh đề. Số tổ hợp lặp chập m của n phần tử bằng. Cn = Cn+ m- 1 = Cn+ 1 - 1 m m n- m Định lý. Số cách chia m vật đồng chất giống nhau vào n hộp khác nhau là m C n
Ví dụ 1. Có bao nhiêu cách chia 10 viên bi giống nhau cho 5 đứa trẻ trong các trường hợp sau: a. Không có một hạn chế nào. b. Đứa trẻ lớn nhất được ít nhất 2 viên bi. Ví dụ 2. Có bao nhiêu cách chia 10 viên bi khác nhau cho 5 đứa trẻ trong các trường hợp sau: a. Không có một hạn chế nào. b. Đứa trẻ lớn nhất được ít nhất 2 viên bi.
1.7 Phân hoạch: Cho A là tập hợp có n phần tử. Ký hiệu A = n. Một sự phân chia tập A thành những tập con A1 , A2 ,K , Ak khác rỗng sao cho: k A= U Ai ; Ai I i= 1 A j = Æ(i ¹ j ) Được gọi là một phân hoạch của tâp A thành k tập con. Mệnh đề. Số phân hoạch khác nhau thành k tập con của tập A là n! n1 !n2 !K nk !