- 3.3.1 Bài toán chọn các phần tử riêng biệt. - 3.3.2 Bài toán chọn các phần tử có lặp. - Tập hợp B gọi là tập con của tập A khi mọi phần tử của tập B đều thuộc A. - m Số phần tử của một số tập hợp. - A n được tiến hành bằng cách chọn lần lượt một phần tử. - của A 1 , một phần tử của A 2. - một phần tử của A n . - Cho tập hợp A , gồm n phần tử ( n 1. - Một cách sắp thứ tự n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó.. - Kí hiệu: P n là số các hoán vị của n phần tử.. - Cho tập hợp A gồm n phần tử ( n 1. - Kí hiệu: A n k là số các chỉnh hợp chập k của n phần tử.. - Một chỉnh hợp n chập n được gọi là một hoán vị của n phần tử.. - Giả sử tập A có n phần tử ( n 1). - k n ) là số các tổ hợp chập k của n phần tử.. - Vì vậy số chỉnh hợp lặp chập r từ tập n phần tử là n k. - Đị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 r. - n r chỉnh hợp lặp chập r từ tập n phần tử.. - Số các chỉnh hợp lặp chập p của n phần tử là n p. - Trong bài toán đếm, một số phần tử có thể giống nhau. - Sau đó có C n n n 2 1 cách đặt n 2 phần tử loại 2 vào hoán vị, còn lại n – n 1 – n 2 chỗ trống.. - Tiếp tục đặt các phần tử loại 3, loại 4. - n k 1 cách đặt n k phần tử loại k vào hoán vị.. - Mộ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 lý 1.5.3 Số tổ hợp lặp chập k từ tập n phần tử bằng 1 k. - 2;4;6;8 có 4 cách chọn. - Có A 8 5 cách chọn.. - Có A 7 4 cách chọn.. - Có A 6 3 cách chọn.. - nên a 1 có 4 cách chọn.. - Có 4! cách chọn.. - Số cách chọn là C 3 5 10. - Có A 4 3 cách chọn. - có 3 cách chọn. - 1 209 cách chọn.. - 1 27 cách chọn.. - Hỏi có bao nhiêu cách chọn như vậy?. - C 45 5 cách chọn thỏa mãn bài toán.. - Tính số hoán vị vòng quanh của n phần tử khác nhau.. - phần tử còn lại được sắp xếp vào n 1 vị trí còn lại. - Số cách chọn đó là n 1. - Chọn m phần tử khác nhau trong n phần tử đã cho (không kể thứ tự sắp xếp).. - Số cách chọn là. - Theo trên có 9 cách chọn.. - Số cách chọn là n 1 C 6 4 15. - 31 Số cách chọn n 2 A 3 2 6. - Số cách chọn là n 1 C 6 5 6. - Số cách chọn n 2 A 1 3 3. - Có 5 cách chọn.. - Có 9 cách chọn (loại 0).. - Có 10 cách chọn.. - Đó là cách chọn 3 phần tử (kể cả thứ tự sắp xếp) trong 10 phần tử. - Có A cách chọn.. - Ứng với một cách chọn ra 6 phần tử phân biệt từ tập A. - Vì vậy số dãy số có 6 chữ số sắp xếp theo thứ tự tăng dần chính bằng số cách chọn ra 6 phần tử phân biệt tại tập hợp A.. - Số cách chọn là C 6 2 15 . - Số cách chọn 6 hộp bánh bằng số tổ hợp lặp chập 6 của 4 phần tử.. - Đảo lại nếu có một tổ hợp lặp chập n của m phần tử kiểu ( k k 1 2. - x m phần tử loại m. - a m phần tử loại m. - phần tử thuộc một trong m loại.. - Gọi N là số cần đếm, N là số phần tử của U. - là tổ hợp chập m của tập n phần tử (số cách chọn m đối tượng trong n đối tượng được cho). - 3.3.1 Bài toán chọn các phần tử riêng biệt.. - Có bao nhiêu cách chọn n phần tử phân biệt từ tập hợp k phần tử.. - Cụ thể Đầu tiên ta xét tập hợp có một phần tử. - 1 cách chọn 0 phần tử.. - 1 cách chọn 1 phần tử.. - 0 cách chọn 2 phần tử trở lên.. - Suy ra hàm sinh cho số cách chọn n phần tử từ tập. - Tương tự như vậy, hàm sinh cho số cách chọn n phần tử từ tập. - Tiếp tục xét tập 2 phần tử a a 1 , 2 ta có 1 cách chọn 0 phần tử.. - 2 cách chọn 1 phần tử.. - 1 cách chọn 2 phần tử. - 0 cách chọn 3 phần tử trở lên.. - Suy ra hàm sinh cho số cách chọn n phần tử từ tập a a 1 , 2 là. - Tiếp tục áp dụng quy tắc này ta sẽ được hàm sinh cho số cách chọn các phần tử từ tập k phần tử.. - Như vậy hệ số của x n trong 1 x k là C k n và bằng số cách chọn n phần tử phân biệt từ tập k phần tử.. - là hàm sinh cho cách chọn các phần tử từ tập hợp A và B x. - hàm sinh cho cách chọn các phần tử từ tập hợp B. - Nếu A và B rời nhau thì hàm sinh cho cách chọn các phần tử từ tập A B là A x B x. - Có bao nhiêu cách chọn k phần tử từ tập hợp có n phần tử, trong đó cho phép một phần tử có thể được chọn nhiều lần.. - Chia tập n phần tử thành hợp của n tập A i ,1. - 1 cách chọn 2 phần tử.. - Áp dụng quy tắc xoắn suy ra hàm sinh của cách chọn có lặp các phần tử từ tập hợp n phần tử sẽ là. - Như vậy số cách chọn k phần tử có lặp từ tập hợp có n phần tử là C n k k. - 1 cách chọn 0 quả táo.. - 0 cách chọn 1 quả táo.. - 1 cách chọn 2 quả táo.. - 0 cách chọn 3 quả táo.. - 1 cách chọn 0 quả cam.. - 1 cách chọn 1 quả cam.. - 1 cách chọn 2 quả cam.. - 1 cách chọn 3 quả cam.. - 1 cách chọn 4 quả cam.. - 0 cách chọn 5 quả cam.. - Có bao nhiêu phần tử chứa trong tất cả 1985 tập hợp đó.. - Suy ra các phần tử thuộc A thuộc 1984 tập hợp khác (mâu thuẫn).. - 2 A 46 tại 46 phần tử khác nhau. - Do đó A * có ít nhất 46 phần tử (mâu thuẫn với giả thiết).