Tập hợp - Giải tích tổ hợp
Bài Giảng Môn học Xác Suất và Thống Kê
Khoa Toán - Tin Học Đại Học Khoa Học Khoa Học Tự Nhiên Tp.HCM
Mai Hoàng Bảo Ân
Ngày 8 tháng 9 năm 2011
Tập hợp - Giải tích tổ hợp
Thông tin môn học
Điểm bài tập: Điểm gk: 3 Điểm ck: 7
Tập hợp - Giải tích tổ hợp
Nội dung
Tập hợp - Giải tích tổ hợp
Tập hợp Giải tích tổ hợp
• Tập hợp có thể hiểu tổng quát là một sự tựu tập của một số
hữu hạn hay vô hạn các đối tượng nào đó. Các đối tượng này được gọi là các phần tử của tập hợp.
• Ta thường dùng các chữ cái in hoa A, B, C , . . . để kí hiệu tập
hợp. Nếu a là phần tử thuộc tập A ta kí hiệu a ∈ A. Ngược lại, a không thuộc A ta kí hiệu a /∈ A
• Tập hợp không có phần tử nào gọi là tập rỗng. Kí hiệu ∅
Tập hợp - Giải tích tổ hợp
Khái niệm về tập hợp
• Khái niệm tập hợp là một khái niệm không có định nghĩa,
tương tự như khái niệm điểm, đường thẳng trong hình học.
• Ta thường dùng các chữ cái in hoa A, B, C , . . . để kí hiệu tập
hợp. Nếu a là phần tử thuộc tập A ta kí hiệu a ∈ A. Ngược lại, a không thuộc A ta kí hiệu a /∈ A
• Tập hợp không có phần tử nào gọi là tập rỗng. Kí hiệu ∅
Tập hợp - Giải tích tổ hợp
Khái niệm về tập hợp
• Khái niệm tập hợp là một khái niệm không có định nghĩa,
tương tự như khái niệm điểm, đường thẳng trong hình học.
• Tập hợp có thể hiểu tổng quát là một sự tựu tập của một số
hữu hạn hay vô hạn các đối tượng nào đó. Các đối tượng này được gọi là các phần tử của tập hợp.
Tập hợp - Giải tích tổ hợp
Khái niệm về tập hợp
• Khái niệm tập hợp là một khái niệm không có định nghĩa,
tương tự như khái niệm điểm, đường thẳng trong hình học.
• Tập hợp có thể hiểu tổng quát là một sự tựu tập của một số
hữu hạn hay vô hạn các đối tượng nào đó. Các đối tượng này được gọi là các phần tử của tập hợp.
• Ta thường dùng các chữ cái in hoa A, B, C , . . . để kí hiệu tập hợp. Nếu a là phần tử thuộc tập A ta kí hiệu a ∈ A. Ngược lại, a không thuộc A ta kí hiệu a /∈ A
• Tập hợp không có phần tử nào gọi là tập rỗng. Kí hiệu ∅
Ví dụ Tập hợp các số tự nhiên nhỏ hơn 5 là
A = {0, 1, 2, 3, 4}
Tập hợp các số tự nhiên chẵn từ 0 đến 100 là
Tập hợp - Giải tích tổ hợp
B = {0, 2, 4, . . . , 98, 100}
Biểu diễn tập hợp
Có hai cách xác định một tập hợp:
• Liệt kê các phần tử của nó.
Tập hợp - Giải tích tổ hợp
Biểu diễn tập hợp
Có hai cách xác định một tập hợp:
• Liệt kê các phần tử của nó.
Ví dụ Tập hợp các số tự nhiên nhỏ hơn 5 là
A = {0, 1, 2, 3, 4}
Tập hợp các số tự nhiên chẵn từ 0 đến 100 là
B = {0, 2, 4, . . . , 98, 100}
Ví dụ Tập hợp các số thực lớn hơn 0 và bé hơn 1 là
Tập hợp - Giải tích tổ hợp
C = {x|x ∈ R và 0 ≤ x ≤ 1}
Biểu diễn tập hợp
• Chỉ ra tính chất đặc trưng của các phần tử của nó.
Không phải mọi tập hợp đều có thể liệt kê rõ ràng từng phần tử. Tuy nhiên ta có thể dùng tính chất đặc trưng nào đó để mô tả nó, từ đó có thể xác định được một phần tử có thuộc tập hợp này hay không.
Tập hợp - Giải tích tổ hợp
Biểu diễn tập hợp
• Chỉ ra tính chất đặc trưng của các phần tử của nó.
Không phải mọi tập hợp đều có thể liệt kê rõ ràng từng phần tử. Tuy nhiên ta có thể dùng tính chất đặc trưng nào đó để mô tả nó, từ đó có thể xác định được một phần tử có thuộc tập hợp này hay không.
Ví dụ Tập hợp các số thực lớn hơn 0 và bé hơn 1 là
C = {x|x ∈ R và 0 ≤ x ≤ 1}
• Tập hợp bằng nhau
Tập hợp - Giải tích tổ hợp
Cho 2 tập hợp A và B. Nếu mỗi phần tử của A đều thuộc B và ngược lại, mỗi phần tử của B đều thuộc A thì ta nói hai tập hợp A và B bằng nhau và kí hiệu A = B. Ta viết A = B ⇔ (A ⊂ B và B ⊂ A)
Quan hệ giữa các tập hợp
• Tập hợp con
Cho 2 tập hợp A và B. Nếu mọi phần tử của tập hợp A đều thuộc tập hợp B, thì ta nói tập hợp A là con tập hợp B và kí hiệu A ⊂ B hoặc B ⊃ A. Ta viết A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B)
Tập hợp - Giải tích tổ hợp
Quan hệ giữa các tập hợp
• Tập hợp con
Cho 2 tập hợp A và B. Nếu mọi phần tử của tập hợp A đều thuộc tập hợp B, thì ta nói tập hợp A là con tập hợp B và kí hiệu A ⊂ B hoặc B ⊃ A. Ta viết A ⊂ B ⇔ (x ∈ A ⇒ x ∈ B)
• Tập hợp bằng nhau
Cho 2 tập hợp A và B. Nếu mỗi phần tử của A đều thuộc B và ngược lại, mỗi phần tử của B đều thuộc A thì ta nói hai tập hợp A và B bằng nhau và kí hiệu A = B. Ta viết A = B ⇔ (A ⊂ B và B ⊂ A)
Tập hợp - Giải tích tổ hợp
Các phép toán trên các tập hợp
• Giao của hai tập hợp
Giao của hai tập hợp A và B đã cho là tập hợp các phần tử đồng thời thuộc cả hai tập hợp này, kí hiệu là A ∩ B Ta viết
(cid:40) x ∈ A ∩ B ⇔ x ∈ A x ∈ B
Tập hợp - Giải tích tổ hợp
Các phép toán trên các tập hợp
• Giao của hai tập hợp
Giao của hai tập hợp A và B đã cho là tập hợp các phần tử đồng thời thuộc cả hai tập hợp này, kí hiệu là A ∩ B Ta viết
(cid:40) x ∈ A ∩ B ⇔ x ∈ A x ∈ B
Tập hợp - Giải tích tổ hợp
• Hợp của hai tập hợp
Hợp của hai tập hợp A và B đã cho là tập hợp các phần tử thuộc ít nhất một trong hai tập hợp này, kí hiệu là A ∪ B Ta viết
x ∈ A ∪ B ⇔ (cid:20) x ∈ A x ∈ B
Tập hợp - Giải tích tổ hợp
• Hợp của hai tập hợp
Hợp của hai tập hợp A và B đã cho là tập hợp các phần tử thuộc ít nhất một trong hai tập hợp này, kí hiệu là A ∪ B Ta viết
x ∈ A ∪ B ⇔ (cid:20) x ∈ A x ∈ B
Tập hợp - Giải tích tổ hợp
Các phép toán trên các tập hợp
• Hiệu của hai tập hợp
Hiệu hai tập hợp A và B đã cho là tập hợp các phần tử thuộc A mà không thuộc B, kí hiệu A \ B Ta viết
A \ B = {x|x ∈ A và x /∈ B}
Tập hợp - Giải tích tổ hợp
Các phép toán trên các tập hợp
• Hiệu của hai tập hợp
Hiệu hai tập hợp A và B đã cho là tập hợp các phần tử thuộc A mà không thuộc B, kí hiệu A \ B Ta viết
A \ B = {x|x ∈ A và x /∈ B}
• Tính kết hợp
(A ∪ B) ∪ C = A ∪ (B ∪ C )
Tập hợp - Giải tích tổ hợp
(A ∩ B) ∩ C = A ∩ (B ∩ C )
Các phép toán trên các tập hợp
Tính chất
• Tính giao hoán
A ∪ B = B ∪ A; A ∩ B = B ∩ A
Tập hợp - Giải tích tổ hợp
Các phép toán trên các tập hợp
Tính chất
• Tính giao hoán
A ∪ B = B ∪ A; A ∩ B = B ∩ A
• Tính kết hợp
(A ∪ B) ∪ C = A ∪ (B ∪ C )
(A ∩ B) ∩ C = A ∩ (B ∩ C )
• Công thức De Morgan
A ∪ B = A ∩ B
Tập hợp - Giải tích tổ hợp
A ∩ B = A ∪ B
Các phép toán trên các tập hợp
Tính chất (tt)
• Tính phân phối
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
Tập hợp - Giải tích tổ hợp
Các phép toán trên các tập hợp
Tính chất (tt)
• Tính phân phối
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
• Công thức De Morgan
A ∪ B = A ∩ B
A ∩ B = A ∪ B
Bài giải
Có 4 số có một chữ số thỏa yêu cầu:
0, 1, 2, 3
Có 9 số có hai chữ số thỏa yêu cầu:
Tập hợp - Giải tích tổ hợp
10, 20, 30, 12, 21, 13, 31, 23, 32
Quy tắc cộng
Giả sử để chọn một đối tượng ta có thể chọn một trong n đối tượng khác nhau, x1, . . . , xn, trong đó mỗi xi có mi cách chọn với i = 1, . . . , n. Khi đó ta có m1 + m2 + . . . + mn cách chọn đối tượng.
Ví dụ Từ các số 0, 1, 2, 3 có thể lập được bao nhiêu số có các chữ số khác nhau?
Có 4 số có một chữ số thỏa yêu cầu:
0, 1, 2, 3
Có 9 số có hai chữ số thỏa yêu cầu:
Tập hợp - Giải tích tổ hợp
10, 20, 30, 12, 21, 13, 31, 23, 32
Quy tắc cộng
Giả sử để chọn một đối tượng ta có thể chọn một trong n đối tượng khác nhau, x1, . . . , xn, trong đó mỗi xi có mi cách chọn với i = 1, . . . , n. Khi đó ta có m1 + m2 + . . . + mn cách chọn đối tượng.
Ví dụ Từ các số 0, 1, 2, 3 có thể lập được bao nhiêu số có các chữ số khác nhau?
Bài giải
Có 9 số có hai chữ số thỏa yêu cầu:
Tập hợp - Giải tích tổ hợp
10, 20, 30, 12, 21, 13, 31, 23, 32
Quy tắc cộng
Giả sử để chọn một đối tượng ta có thể chọn một trong n đối tượng khác nhau, x1, . . . , xn, trong đó mỗi xi có mi cách chọn với i = 1, . . . , n. Khi đó ta có m1 + m2 + . . . + mn cách chọn đối tượng.
Ví dụ Từ các số 0, 1, 2, 3 có thể lập được bao nhiêu số có các chữ số khác nhau?
Bài giải Có 4 số có một chữ số thỏa yêu cầu:
0, 1, 2, 3
Tập hợp - Giải tích tổ hợp
Quy tắc cộng
Giả sử để chọn một đối tượng ta có thể chọn một trong n đối tượng khác nhau, x1, . . . , xn, trong đó mỗi xi có mi cách chọn với i = 1, . . . , n. Khi đó ta có m1 + m2 + . . . + mn cách chọn đối tượng.
Ví dụ Từ các số 0, 1, 2, 3 có thể lập được bao nhiêu số có các chữ số khác nhau?
Bài giải Có 4 số có một chữ số thỏa yêu cầu:
0, 1, 2, 3
Có 9 số có hai chữ số thỏa yêu cầu:
10, 20, 30, 12, 21, 13, 31, 23, 32
Có 18 số có bốn chữ số thỏa yêu cầu:
1023, 1032, 1203, 1230, 1302, 1320, 2013, 2031, 2103, 2130,
2301, 2310, 3012, 3021, 3102, 3120, 3201, 3210
Tập hợp - Giải tích tổ hợp
Vậy theo quy tắc cộng, có 4 + 9 + 18 + 18 = 49 cách lập các số có các chữ số khác nhau từ các chữ số 0, 1, 2, 3
Quy tắc cộng
Có 18 số có ba chữ số thỏa yêu cầu:
102, 120, 103, 130, 123, 132, 201, 210, 203, 230,
213, 231, 301, 310, 302, 320, 312, 321
Tập hợp - Giải tích tổ hợp
Vậy theo quy tắc cộng, có 4 + 9 + 18 + 18 = 49 cách lập các số có các chữ số khác nhau từ các chữ số 0, 1, 2, 3
Quy tắc cộng
Có 18 số có ba chữ số thỏa yêu cầu:
102, 120, 103, 130, 123, 132, 201, 210, 203, 230,
213, 231, 301, 310, 302, 320, 312, 321
Có 18 số có bốn chữ số thỏa yêu cầu:
1023, 1032, 1203, 1230, 1302, 1320, 2013, 2031, 2103, 2130,
2301, 2310, 3012, 3021, 3102, 3120, 3201, 3210
Tập hợp - Giải tích tổ hợp
Quy tắc cộng
Có 18 số có ba chữ số thỏa yêu cầu:
102, 120, 103, 130, 123, 132, 201, 210, 203, 230,
213, 231, 301, 310, 302, 320, 312, 321
Có 18 số có bốn chữ số thỏa yêu cầu:
1023, 1032, 1203, 1230, 1302, 1320, 2013, 2031, 2103, 2130,
2301, 2310, 3012, 3021, 3102, 3120, 3201, 3210
Vậy theo quy tắc cộng, có 4 + 9 + 18 + 18 = 49 cách lập các số có các chữ số khác nhau từ các chữ số 0, 1, 2, 3
Tập hợp - Giải tích tổ hợp
Quy tắc nhân
Giả sử để hoàn thành một công việc thì phải thực hiện k giai đoạn. Giai đoạn thứ nhất có n1 cách thực hiện, giai đoạn thứ hai có n2 cách thực hiện, . . . , giai đoạn thứ k có nk cách thực hiện. Khi đó ta có n = n1n2 . . . nk
cách hoàn thành công việc.
Tập hợp - Giải tích tổ hợp
Quy tắc nhân
Ví dụ Giả sử đi từ A đến C ta bắt buộc phải đi qua B. Có 3 đường khác nhau từ A đến B và có 2 đường khác nhau từ B đến C . Vậy có n = 3.2 = 6 cách khác nhau để đi từ A đến C .
• Nhóm không có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta không nhận được nhóm khác.
• Nhóm có lặp
Các phần tử của nhóm có thể có mặt nhiều lần trong nhóm.
• Nhóm không lặp
Tập hợp - Giải tích tổ hợp
Các phần tử của nhóm chỉ có mặt một lần trong nhóm.
Tính chất của một nhóm (bộ) k phần tử
• Nhóm có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta nhận được nhóm khác.
• Nhóm có lặp
Các phần tử của nhóm có thể có mặt nhiều lần trong nhóm.
• Nhóm không lặp
Tập hợp - Giải tích tổ hợp
Các phần tử của nhóm chỉ có mặt một lần trong nhóm.
Tính chất của một nhóm (bộ) k phần tử
• Nhóm có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta nhận được nhóm khác.
• Nhóm không có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta không nhận được nhóm khác.
• Nhóm không lặp
Tập hợp - Giải tích tổ hợp
Các phần tử của nhóm chỉ có mặt một lần trong nhóm.
Tính chất của một nhóm (bộ) k phần tử
• Nhóm có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta nhận được nhóm khác.
• Nhóm không có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta không nhận được nhóm khác.
• Nhóm có lặp
Các phần tử của nhóm có thể có mặt nhiều lần trong nhóm.
Tập hợp - Giải tích tổ hợp
Tính chất của một nhóm (bộ) k phần tử
• Nhóm có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta nhận được nhóm khác.
• Nhóm không có thứ tự
Khi đổi vị trí các phần tử khác nhau của nhóm này ta không nhận được nhóm khác.
• Nhóm có lặp
Các phần tử của nhóm có thể có mặt nhiều lần trong nhóm.
• Nhóm không lặp
Các phần tử của nhóm chỉ có mặt một lần trong nhóm.
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 5 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 5 cách chọn. Vậy có n = 4.5.5 = 100 số.
• Các chữ số không lặp
Tập hợp - Giải tích tổ hợp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 4 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 3 cách chọn. Vậy có n = 4.4.3 = 48 số.
Tính chất của một nhóm (bộ) k phần tử
Ví dụ Từ các số 0, 1, 2, 3, 4 lập số có 3 chữ số
• Các chữ số có lặp
• Các chữ số không lặp
Tập hợp - Giải tích tổ hợp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 4 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 3 cách chọn. Vậy có n = 4.4.3 = 48 số.
Tính chất của một nhóm (bộ) k phần tử
Ví dụ Từ các số 0, 1, 2, 3, 4 lập số có 3 chữ số
• Các chữ số có lặp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 5 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 5 cách chọn. Vậy có n = 4.5.5 = 100 số.
Tập hợp - Giải tích tổ hợp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 4 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 3 cách chọn. Vậy có n = 4.4.3 = 48 số.
Tính chất của một nhóm (bộ) k phần tử
Ví dụ Từ các số 0, 1, 2, 3, 4 lập số có 3 chữ số
• Các chữ số có lặp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 5 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 5 cách chọn. Vậy có n = 4.5.5 = 100 số.
• Các chữ số không lặp
Tập hợp - Giải tích tổ hợp
Tính chất của một nhóm (bộ) k phần tử
Ví dụ Từ các số 0, 1, 2, 3, 4 lập số có 3 chữ số
• Các chữ số có lặp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 5 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 5 cách chọn. Vậy có n = 4.5.5 = 100 số.
• Các chữ số không lặp
Công việc 1: Chọn chữ số hàng trăm có n1 = 4 cách chọn. Công việc 2: Chọn chữ số hàng chục có n2 = 4 cách chọn. Công việc 3: Chọn chữ số hàng đơn vị có n3 = 3 cách chọn. Vậy có n = 4.4.3 = 48 số.
n là số chỉnh hợp chập k của n phần tử. Khi đó,
Gọi Ak
n = n.(n − 1) . . . (n − k + 1) =
Tập hợp - Giải tích tổ hợp
n! Ak (n − k)!
Chỉnh hợp
Định nghĩa Chỉnh hợp chập k của n phần tử (k ≤ n) là một nhóm có thứ tự gồm k phần tử khác nhau chọn từ n phần tử đã cho.
Tập hợp - Giải tích tổ hợp
Chỉnh hợp
Định nghĩa Chỉnh hợp chập k của n phần tử (k ≤ n) là một nhóm có thứ tự gồm k phần tử khác nhau chọn từ n phần tử đã cho. Gọi Ak n là số chỉnh hợp chập k của n phần tử. Khi đó,
n = n.(n − 1) . . . (n − k + 1) =
Ak n! (n − k)!
Bài giải
Một cách chọn một lớp trưởng và một lớp phó là một nhóm có hai phần tử có thứ tự và không lặp. Nên có
12 = 12.11 = 132
A2
Tập hợp - Giải tích tổ hợp
cách chọn thỏa yêu cầu.
Chỉnh hợp
Ví dụ Một lớp học tiếng Anh có 12 người tham dự. Hỏi có bao nhiêu cách chọn một lớp trưởng và một lớp phó?
Tập hợp - Giải tích tổ hợp
Chỉnh hợp
Ví dụ Một lớp học tiếng Anh có 12 người tham dự. Hỏi có bao nhiêu cách chọn một lớp trưởng và một lớp phó?
Bài giải Một cách chọn một lớp trưởng và một lớp phó là một nhóm có hai phần tử có thứ tự và không lặp. Nên có
12 = 12.11 = 132
A2
cách chọn thỏa yêu cầu.
Số hoán vị của n phần tử là
Pn = n!
Quy ước 0! = 1
Ví dụ Mỗi cách xếp 4 học sinh ngồi vào một bàn có 4 chỗ ngồi là một hoán vị của 4 phần tử. Do đó số cách xếp sẽ là P4 = 4! = 24 cách.
Nhận xét
n
Tập hợp - Giải tích tổ hợp
Hoán vị là một trường hợp đặc biệt của chỉnh hợp vì Pn = An
Hoán vị
Định nghĩa Hoán vị của n phần tử là một nhóm có thứ tự không lặp có đủ n phần tử đã cho.
Ví dụ Mỗi cách xếp 4 học sinh ngồi vào một bàn có 4 chỗ ngồi là một hoán vị của 4 phần tử. Do đó số cách xếp sẽ là P4 = 4! = 24 cách.
Nhận xét
n
Tập hợp - Giải tích tổ hợp
Hoán vị là một trường hợp đặc biệt của chỉnh hợp vì Pn = An
Hoán vị
Định nghĩa Hoán vị của n phần tử là một nhóm có thứ tự không lặp có đủ n phần tử đã cho.
Số hoán vị của n phần tử là
Pn = n!
Quy ước 0! = 1
Nhận xét
n
Tập hợp - Giải tích tổ hợp
Hoán vị là một trường hợp đặc biệt của chỉnh hợp vì Pn = An
Hoán vị
Định nghĩa Hoán vị của n phần tử là một nhóm có thứ tự không lặp có đủ n phần tử đã cho.
Số hoán vị của n phần tử là
Pn = n!
Quy ước 0! = 1
Ví dụ Mỗi cách xếp 4 học sinh ngồi vào một bàn có 4 chỗ ngồi là một hoán vị của 4 phần tử. Do đó số cách xếp sẽ là P4 = 4! = 24 cách.
Tập hợp - Giải tích tổ hợp
Hoán vị
Định nghĩa Hoán vị của n phần tử là một nhóm có thứ tự không lặp có đủ n phần tử đã cho.
Số hoán vị của n phần tử là
Pn = n!
Quy ước 0! = 1
Ví dụ Mỗi cách xếp 4 học sinh ngồi vào một bàn có 4 chỗ ngồi là một hoán vị của 4 phần tử. Do đó số cách xếp sẽ là P4 = 4! = 24 cách.
Nhận xét Hoán vị là một trường hợp đặc biệt của chỉnh hợp vì Pn = An n
Định nghĩa
Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử được chọn từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt hơn một lần trong nhóm.
n là số chỉnh hợp lặp chập k của n phần tử. Khi đó,
Gọi (cid:102)Ak
n = nk
Tập hợp - Giải tích tổ hợp
(cid:102)Ak
Chỉnh hợp lặp
Trong định nghĩa chỉnh hợp ta đòi hỏi mỗi phần tử chỉ được có mặt trong nhóm không quá một lần. Nếu bỏ đi điều kiện này, ta có chỉnh hợp lặp.
n là số chỉnh hợp lặp chập k của n phần tử. Khi đó,
Gọi (cid:102)Ak
n = nk
Tập hợp - Giải tích tổ hợp
(cid:102)Ak
Chỉnh hợp lặp
Trong định nghĩa chỉnh hợp ta đòi hỏi mỗi phần tử chỉ được có mặt trong nhóm không quá một lần. Nếu bỏ đi điều kiện này, ta có chỉnh hợp lặp.
Định nghĩa Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử được chọn từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt hơn một lần trong nhóm.
Tập hợp - Giải tích tổ hợp
Chỉnh hợp lặp
Trong định nghĩa chỉnh hợp ta đòi hỏi mỗi phần tử chỉ được có mặt trong nhóm không quá một lần. Nếu bỏ đi điều kiện này, ta có chỉnh hợp lặp.
Định nghĩa Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử được chọn từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt hơn một lần trong nhóm.
n là số chỉnh hợp lặp chập k của n phần tử. Khi đó,
n = nk (cid:102)Ak
Gọi (cid:102)Ak
Tập hợp - Giải tích tổ hợp
Nhận xét Vì mỗi phần tử có thể xuất hiện nhiều lần trong một chỉnh hợp lặp nên ở đây k có thể lớn hơn n.
Chỉnh hợp lặp
3 = 35
Ví dụ Từ các số của tập hợp A = {1, 2, 3}, ta có thể lập được (cid:102)A5 số có 5 chữ số.
Tập hợp - Giải tích tổ hợp
Chỉnh hợp lặp
3 = 35
Ví dụ Từ các số của tập hợp A = {1, 2, 3}, ta có thể lập được (cid:102)A5 số có 5 chữ số.
Nhận xét Vì mỗi phần tử có thể xuất hiện nhiều lần trong một chỉnh hợp lặp nên ở đây k có thể lớn hơn n.
n là số tổ hợp chập k của n phần tử. Khi đó,
Gọi C k
n =
n! C k k!(n − k)!
Ví dụ Mỗi đề thi gồm 3 câu hỏi lấy từ 25 câu hỏi cho trước, ta lập được
25 =
25! C 3 = 2300 3!22!
Tập hợp - Giải tích tổ hợp
đề thi. Vì mỗi đề thi là một nhóm có 3 câu hỏi có tính chất không có thứ tự và không lặp.
Tổ hợp
Định nghĩa Tổ hợp chập k của n phần tử (k ≤ n) là một nhóm không phân biệt thứ tự gồm k phần tử khác nhau chọn từ n phần tử đã cho.
Ví dụ Mỗi đề thi gồm 3 câu hỏi lấy từ 25 câu hỏi cho trước, ta lập được
25 =
25! C 3 = 2300 3!22!
Tập hợp - Giải tích tổ hợp
đề thi. Vì mỗi đề thi là một nhóm có 3 câu hỏi có tính chất không có thứ tự và không lặp.
Tổ hợp
n là số tổ hợp chập k của n phần tử. Khi đó,
Định nghĩa Tổ hợp chập k của n phần tử (k ≤ n) là một nhóm không phân biệt thứ tự gồm k phần tử khác nhau chọn từ n phần tử đã cho. Gọi C k
n =
C k n! k!(n − k)!
Tập hợp - Giải tích tổ hợp
Tổ hợp
n là số tổ hợp chập k của n phần tử. Khi đó,
Định nghĩa Tổ hợp chập k của n phần tử (k ≤ n) là một nhóm không phân biệt thứ tự gồm k phần tử khác nhau chọn từ n phần tử đã cho. Gọi C k
n =
C k n! k!(n − k)!
Ví dụ Mỗi đề thi gồm 3 câu hỏi lấy từ 25 câu hỏi cho trước, ta lập được
25 =
C 3 = 2300 25! 3!22!
đề thi. Vì mỗi đề thi là một nhóm có 3 câu hỏi có tính chất không có thứ tự và không lặp.
Tập hợp - Giải tích tổ hợp
Tổ hợp
Tổ hợp có các tính chất cơ bản sau:
• Quy ước 0! = 1. n = C n−k • C k n = C k−1 • C k
n−1
. n n−1 + C k
Tập hợp - Giải tích tổ hợp
Các hệ số trong nhị thức Newton có thể được xác định từ tam giác Pascal
Nhị thức Newton
n (cid:88)
Công thức nhị thức Newton
n an−k bk C k
k=0
(a + b)n =
Tập hợp - Giải tích tổ hợp
Nhị thức Newton
n (cid:88)
Công thức nhị thức Newton
n an−k bk C k
k=0
(a + b)n =
Các hệ số trong nhị thức Newton có thể được xác định từ tam giác Pascal
Tập hợp - Giải tích tổ hợp
Nhị thức Newton
n (cid:88)
Công thức nhị thức Newton
n an−k bk C k
k=0
(a + b)n =
Các hệ số trong nhị thức Newton có thể được xác định từ tam giác Pascal
