(LUẬN văn THẠC sĩ) phương pháp quỹ đạo và ứng dụng vào giải một số bài toán tổ hợp dành cho học sinh khá giỏi

Một số phương pháp giải bài toán đếm của toán tổ hợp trong phạm vi chương trình toán THPT

Đếm trực tiếp

Tùy theo bài toán chúng ta có thể chia trường hợp hay không chia trường hợp. Nội dung: Đếm các trường hợp thỏa mãn yêu cầu bài toán.

Cho tập A = {0,1,2,3,4,5,6,7}, ta cần xác định số lượng số tự nhiên có 5 chữ số khác nhau luôn có mặt chữ số 2 Đối với câu a), có thể lập được nhiều số tự nhiên 5 chữ số khác nhau với chữ số 2 Câu b) yêu cầu tìm số lượng số tự nhiên lẻ có 5 chữ số khác nhau cũng luôn có mặt chữ số 2.

Lời giải a) Gọi số cần tìm là n = a 1 a 2 a 3 a 4 a 5

+Trường hợp 1 a1 = 2 có 1 cách chọn. a2a3a4a5 có A 4 7 cách chọn.

Suy ra ta có A 4 7 = 840 số.

+ Trường hợp 2 a2 = 2 có 1 cách chọn. a1 6= 0 và a1 6= 2 nên có 6 cách chọn. a3a4a5 có A 3 6 số.

Suy ra ta có 6.A 3 6 = 720 số.

Vì vai trò của 2 trong các vị trí a 2 , a 3 , a 4 , a 5 là giống nhau nên

Số cần tìm là 840 + 720.4 = 3720 số. b) Gọi số cần tìm là n = a1a2a3a4a5.

+Trường hợp 1 a 5 lẻ nên có 4 cách chọn. a2 = 2 có 1 cách chọn. a2a3a4 có A 3 6 số.

+ Trường hợp 2 a5 lẻ nên có 4 cách chọn. a2 = 2 có 1 cách chọn. a 1 6= 0, a 1 6= 2, a 1 6= a 5 nên có 5 cách chọn. a 3 a 4 có A 2 5 cách chọn.

Suy ra ta có 4.5.A 2 5 = 400 số.

Vì vai trò của 2 trong các vị trí a2, a3, a4 là giống nhau nên

Số cần tìm là 480 + 400.3 = 1680 số.

Đếm theo vị trí

+ Chọn vị trí cho số thứ nhất theo yêu cầu bài toán, suy ra số vị trí cho các số tiếp theo.

+ Sắp xếp các số còn lại.

Từ tập hợp S = {1; 2; 3; 4; 5; 6; 7; 8; 9}, chúng ta cần xác định số lượng số có chín chữ số khác nhau, với điều kiện rằng chữ số 1 phải đứng trước chữ số 2, chữ số 3 phải đứng trước chữ số 4, và chữ số 5 phải đứng trước chữ số 6.

Chọn 2 vị trí để xếp 2 chữ số 1,2 (số 5 đứng trước 6): có C 5 2 cách.

3 chữ số còn lại có 3! cách.

Vậy cú 3!.C 9 2 ãC 7 2 ãC 5 2 = 45360 số.

Ví dụ 1.3.3 Cho tập A = {1,2,3,4,5,6,7,8,9} Có bao nhiêu số tự nhiên chẵn có 5 chữ số khác nhau sao cho a) Luôn có mặt chữ số 3. b) Luôn có mặt chữ số 4.

Gọi số cần tìm là n = a1a2a3a4a5. a)

+ Chữ số 3 có 3 vị trí.

+ 3 chữ số còn lại có A 3 8 cách sắp xếp.

+ Trường hợp 1: a5 = 4, khi đó A 4 8 = 1680 số.

+ Trường hợp 2: a5 6= 4, khi đó a 5 có 3 cách chọn.

Chữ số 4 có 4 vị trí.

3 chữ số còn lại có A 3 7 cách sắp xếp.

Suy ra ra có 3.4.A 3 7 = 2520 số.

Đếm loại trừ

Nội dung: Đếm loại trừ theo hai bước

+ Bước 1: Đếm số phương án xảy ra bất kỳ ta có kết quả n 1

+ Bước 2: Đếm số phương án xảy ra không thỏa mãn yêu cầu bài toán ta có kết quả n2.

+ Bước 3: Số phương án đúng là: n = n 1 −n 2

Chú ý: Khi phương pháp đếm trực tiếp có nhiều trường hợp quá chúng ta sử dụng phương pháp đếm loại trừ.

Ví dụ 1.3.4 Cho tập A = {1,2,3,4,5,6,7} Có bao nhiêu số lẻ có 4 chữ số khác nhau sao cho chữ số 4 luôn có mặt một lần.

Gọi số cần tìm là n = a1a2a3a4.

+ Đếm các số lẻ có 4 chữ số khác nhau là: a 4 có 4 cách chọn (a 4 ∈ {1,3,5,7}); 3 chữ số còn lại có A 3 6 cách chọn, suy ra có 4.A 3 6 số.

Để đếm các số lẻ có 4 chữ số khác nhau mà không chứa chữ số 4, ta có 4 cách chọn cho chữ số đầu tiên (a4 ∈ {1,3,5,7}) Sau đó, 3 chữ số còn lại có 5 cách chọn (không bao gồm số 4), từ đó suy ra tổng số có được là 4.A3.5.

Các số cần tìm là 4.A 3 6 −4.A 3 5 = 240 số.

Chọn tập con trước, sắp xếp sau

Để giải bài toán, bước đầu tiên là chọn ra số lượng phần tử cần thiết, đảm bảo thỏa mãn các yêu cầu của đề bài (ví dụ, chọn tập con có k phần tử từ n phần tử sẽ có C(n, k) cách) Sau khi lựa chọn xong, bước tiếp theo là tiến hành sắp xếp các phần tử đã chọn.

• Chú ý: Những bài toán có sự sắp xếp, cạnh nhau, có mặt.

Ví dụ 1.3.5 Cho tập A = {1,2,3,4,5,6,7,8,9} Có bao nhiêu số tự nhiên có

5 chữ số khác nhau sao cho: a) Luôn có mặt hai chữ số 2, 3. b) Luôn có mặt hai chữ số 2, 3 và hai chữ số này luôn đứng kề nhau.

+ Lấy ra 5 số từ tập A:

Số 2, 3 có 1 cách chọn, 3 số còn lại được lấy từ tập A\{2,3} nên có C 7 3 cách, suy ra có C 7 3 cách lấy ra 5 số mà 2, 3 luôn có mặt.

Sắp xếp 5 số vào 5 vị trí ta có 5! cách.

+ Lấy ra 5 số từ tập A:

Số 2, 3 có 1 cách chọn, 3 số còn lại được lấy từ tập A\{2,3} nên có C 7 3 cách, suy ra có C 7 3 cách lấy ra 5 số mà 2, 3 luôn có mặt.

Khi sắp xếp số 2 và 3 kề nhau, ta coi chúng là một số a với 2! cách sắp xếp Kết hợp với 3 số còn lại, ta có 4! cách sắp xếp Do đó, tổng số cách sắp xếp 5 chữ số đã chọn là 2! x 4! Từ đó, ta tính được C(7, 3) x 2! x 4! = 1680 số.

Đếm theo “vách ngăn”

+ Bước 1: Sắp xếp m đối tượng vào m vị trí sẽ tạo ra m+ 1 vách ngăn.

+ Bước 2: Sắp xếp đối tượng khác theo yêu cầu bài toán từ m+ 1 vách ngăn nói trên.

1 Hầu hết các bài toán tổ hợp đều sử dụng một trong các phương pháp trên để giải quyết, tuy nhiên sự linh hoạt của phương pháp tùy thuộc vào khả năng của từng học sinh.

2 Đối với bài toán mà tập ban đầu có số 0 ta xét các trường hợp xem số 0 là một số có nghĩa ta được kết quả n1, xét trường hợp số 0 đứng đầu ta có kết quả n2, kết quả cần tìm là n1−n2.

Ví dụ 1.3.6 Cần sắp xếp 2 thầy giáo và 6 học sinh vào một dãy ghế dài sao cho 2 thầy giáo không ngồi cạnh nhau.

+ Xếp 6 học sinh vào 6 vị trí ta có 6! cách xếp.

+ 6 học sinh sẽ tạo ra 7 vách ngăn, ta đặt 2 thầy giáo vào 7 vách ngăn ta có

Khi đó số cách sắp xếp là 6!A 2 7 = 30240.

Sử dụng nguyên lý bù trừ

Khi hai công việc có thể thực hiện đồng thời, không thể áp dụng quy tắc cộng để tính số cách thực hiện nhiệm vụ Để có được số cách chính xác, ta cần cộng số cách thực hiện từng công việc riêng lẻ và sau đó trừ đi số cách thực hiện cả hai công việc cùng một lúc.

Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp.

Cho A1,A2 là hai tập hữu hạn, khi đó

Từ đó với ba tập hợp hữu hạn A 1 ,A 2 ,A 3 , ta có:

Và bằng quy nạp, với k tập hữu hạn A1,A2, ,Ak ta có:

|A1 ∪A2∪ .∪Ak| = N1 −N2 + N3− .+ (−1) k−1 Nk, trong đóN m (1 ≤ m ≤ k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho, nghĩa là

Chúng ta sẽ đồng nhất tập A m (1 ≤ m ≤ k) với tính chất A m trong một tập vũ trụ hữu hạn U và tiến hành đếm số phần tử của U không thỏa mãn bất kỳ tính chất A m nào Gọi N¯ là số phần tử cần đếm trong tập hợp này.

N¯ = N − |A 1 ∪A 2 ∪ .∪A k | =N −N 1 + N 2 − .+ (−1) k N k , trong đó N m là tổng các phần tử của U thỏa mãn m tính chất lấy từ k tính chất đã cho.

Công thức này được gọi là nguyên lý bù trừ Nó cho phép tính N¯ qua các Nm trong trường hợp các số này dễ tính toán hơn.

Một chuyến bay có tổng cộng 67 hành khách, trong đó 47 người thành thạo tiếng Anh, 35 người thành thạo tiếng Đức và 20 người thành thạo tiếng Pháp Đáng chú ý, có 23 hành khách sử dụng thành thạo cả tiếng Anh và tiếng Đức, 12 người sử dụng thành thạo cả tiếng Anh và tiếng Pháp, và 11 người sử dụng thành thạo cả tiếng Đức và tiếng Pháp.

5 người sử dụng tốt cả ba thứ tiếng Tìm số hành khách không sử dụng được bất kì ngoại ngữ nào?

Gọi A, B, C lần lượt là các hành khách sử dụng tốt ngoại ngữ là tiếng Anh, tiếng Đức, tiếng Pháp.

Số các hành khách biết ít nhất một ngoại ngữ là:

= 47 + 35 + 20−23 −12 −1 + 5 = 61 Vậy số hành khách không sử dụng được bất kì ngoại ngữ nào là 67 −61 = 6.

Ví dụ 1.3.8 Rút ngẫu nhiên 13 quân bài từ bộ bài 52 quân Tính xác suất để trong 13 quân đó có “tứ quý”.

Có C 52 13 cách rút 13 quân bài từ bộ bài 52 quân Ta cần tìm số cách rút trong đó có 4 quân bài giống nhau (về số).

Để tính số cách rút bài có "tứ quý" A, ta có thể sử dụng công thức C(48, 9), tức là có 48 quân bài còn lại và ta chọn 9 quân bất kỳ Số cách rút này tương tự cho các quân bài khác.

Vì có 13 quân bài khác nên số cách rút là có tứ quý là 13.C 48 9

Trong lời giải, chúng ta đã phát hiện việc đếm lặp trong cách rút bài có hai tứ quý, ví dụ như tứ quý K và tứ quý A Điều này dẫn đến việc mỗi tứ quý được tính hai lần trong quá trình đếm.

Số lần gặp tứ quý K và A cần được tính toán chính xác, vì chúng ta không chỉ đếm số tứ quý mà còn phải trừ đi những lần lặp Số cách rút có tứ quý K và A được xác định là C(44, 5) Tiếp tục lý luận, ta có thể tính ra số cách rút chính xác có tứ quý.

13.C 48 9 −C 13 2 C 44 5 +C 13 3 C 40 1 và xác suất cần tìm bằng

Xác suất để một người chơi bài ngẫu nhiên có được tứ quý là 0.0342, tức là trung bình cứ 29 lần chơi sẽ có 1 lần đạt được tứ quý Trong một ván chơi, khả năng xuất hiện ít nhất một tứ quý cao hơn và có thể được tính toán bằng phương pháp thêm bớt.

P ∼ 4p 6 p 2 + 4p 3 p 4 = 0.1299. tức là cứ khoảng 8 ván sẽ có xuất hiện một tứ quý.

Có bao nhiêu cách sắp xếp 8 con xe trên bàn cờ quốc tế khi đã gạch đi một đường chéo chính, đảm bảo rằng không có con nào có thể ăn con nào?

Có 8! cách sắp xếp 8 con xe trên bàn cờ quốc tế mà không có con nào ăn nhau Tuy nhiên, để tìm số cách sắp xếp không hợp lệ, tức là những cách có ít nhất một con xe nằm trên đường chéo, chúng ta cần phải tính toán kỹ lưỡng Việc này giúp xác định số cách sắp xếp hợp lệ cho bài toán.

Gọi A i là tập hợp các cách xếp có quân xe nằm ở ô (i, i).

Nhưng dễ dàng thấy rằng |Ai| = 7!, |Ai∩Aj|= 6! .|A1∩ .∩A8| = 1 nên từ định lý trên ta suy ra

Có 8 cách để xếp 8 con xe trên bàn cờ quốc tế sao cho không có con nào ăn con nào, với điều kiện là có một đường chéo chính bị gạch đi.

Sử dụng tính chất của song ánh

Ánh xạ f : X → Y được định nghĩa là một đơn ánh nếu với mọi x, x' ∈ X, điều kiện f(x) = f(x') kéo theo x = x', hoặc x ≠ x' kéo theo f(x) ≠ f(x'), tức là với mọi y ∈ Y, có tối đa một x ∈ X sao cho y = f(x) Một ánh xạ f được gọi là toàn ánh nếu f(X) = Y, nghĩa là với mọi y ∈ Y, có ít nhất một x ∈ X sao cho y = f(x) Cuối cùng, ánh xạ f được gọi là song ánh nếu nó vừa là đơn ánh vừa là toàn ánh, tức là với mọi y ∈ Y, có một và chỉ một x ∈ X sao cho y = f(x).

Phương pháp song ánh dựa trên nguyên tắc cơ bản rằng nếu tồn tại một song ánh từ tập hợp A đến tập hợp B, thì số lượng phần tử của A và B là bằng nhau, tức là |A| = |B| Để chứng minh hai tập hợp có cùng số phần tử, chỉ cần thiết lập một song ánh giữa chúng Ngoài ra, phương pháp này còn cho phép chúng ta đếm số phần tử của một tập hợp A thông qua việc xây dựng một song ánh từ A đến một tập hợp khác.

Tập hợp B có số phần tử giống như tập hợp A, nhưng cấu trúc của B được mô tả khác biệt, giúp cho việc đếm số phần tử của B trở nên dễ dàng hơn so với việc đếm số phần tử của A.

Trong một nhóm người, nếu mỗi cặp không quen nhau có đúng hai người quen chung, trong khi mỗi cặp quen nhau lại không có người quen chung, thì số người quen của mỗi cá nhân trong nhóm này là như nhau Điều này chứng minh rằng sự phân bố mối quan hệ quen biết giữa các thành viên trong nhóm là đồng đều.

Nếu a quen b và có các người quen là A và B (không tính a, b), thì mỗi người trong A sẽ quen với một người duy nhất trong B Điều này xảy ra vì không ai trong A quen với b và họ đã có một người quen chung là a Tương tự, mỗi người trong B cũng chỉ quen với một người trong A Do đó, tồn tại một sự tương ứng một-một giữa A và B, cho thấy a và b có số người quen bằng nhau.

Nếu a không quen b thì tồn tại c quen cả a và b Do đó số người quen của a và b bằng nhau do cùng bằng số người quen của c (suy ra từ trên).

Ví dụ 1.3.11 Xét tập A = {1,2, , n} Đối với mỗi tập con không trống của

A chúng ta xác định duy nhất một tổng đan dấu theo quy tắc sau:

Xếp các số trong tập con theo thứ tự tăng dần và gán luân phiên dấu cộng và trừ cho các số liên tiếp Đảm bảo rằng số lớn nhất sẽ có dấu cộng Mục tiêu là tìm tổng của tất cả các tổng đan dấu này.

Quy ước tổng đan dấu của tập trống có giá trị 0 Mỗi tập con của A được chia làm hai loại:

Các tập con loại 1 và loại 2 có số phần tử bằng nhau vì tồn tại một song ánh giữa chúng như sau:

Khi đó tổng đan dấu của một tập con trên bằng

Có 2 n tập con của A suy ra có 2 n−1 cặp tập hợp con loại 1 và loại 2 theo định nghĩa trên.

Vậy tổng của tất cả cỏc tổng đan dấu bằng S = 2 n−1 ãn.

Vận dụng phương pháp “quỹ đạo” vào giải một số bài toán tổ hợp 15

Một số vận dụng

2.3 Ý nghĩa của khái niệm “quỹ đạo” và phương pháp “quỹ đạo”.

Luận văn này được hoàn thành nhờ sự hướng dẫn tận tình của PGS TS Trịnh Thanh Hải và sự hỗ trợ từ các thầy cô trong khoa Toán - Tin, trường Đại học Khoa học cùng các bạn trong lớp Cao học K11 Tôi xin chân thành cảm ơn những đóng góp quý báu từ thầy cô và bạn bè, đặc biệt là thầy PGS TS Trịnh Thanh Hải Mặc dù đã nỗ lực trong quá trình thực hiện, luận văn vẫn không tránh khỏi những thiếu sót do thời gian và kiến thức còn hạn chế Rất mong nhận được sự góp ý từ quý thầy cô và các bạn.

Em xin chân thành cảm ơn!

Thái Nguyên, ngày 28 tháng 12 năm 2019

Một số kiến thức chuẩn bị

1.1 Bài toán đếm trong toán tổ hợp

Trong toán tổ hợp, bài toán đếm là bài toán nhằm trả lời câu hỏi: “Có bao nhiêu cấu hình tổ hợp thuộc dạng đã cho?”.

Phương pháp đếm thường dựa vào một số quy tắc, nguyên lý đếm và một số kết quả đếm cho các cấu hình tổ hợp đơn giản.

Hai quy tắc đếm cơ bản là quy tắc cộng và quy tắc nhân.

Quy tắc cộng trong đếm cơ bản xác định rằng nếu một công việc có thể được hoàn thành bằng một trong hai hành động khác nhau, với hành động đầu tiên có m cách thực hiện và hành động thứ hai có n cách thực hiện không trùng lặp, thì tổng số cách thực hiện công việc này là m + n.

Quy tắc nhân cho biết rằng khi một công việc được hoàn thành bằng hai hành động liên tiếp, nếu có m cách thực hiện hành động đầu tiên và n cách cho hành động thứ hai, thì tổng số cách hoàn thành công việc là m.n Định nghĩa hoán vị cho tập hợp A với n phần tử (n ≥ 1) chỉ ra rằng mỗi cách sắp xếp thứ tự của n phần tử trong tập hợp A được gọi là một hoán vị của chúng.

• Kí hiệu: Pn là số các hoán vị của n phần tử.

• Số cỏc hoỏn vị: Pn = n! = 1ã2ã ã ã(n−1)ãn.

Chỉnh hợp là khái niệm liên quan đến việc chọn và sắp xếp k phần tử khác nhau từ một tập hợp A có n phần tử (n ≥ 1) Kết quả của quá trình này được gọi là một chỉnh hợp chập k của n phần tử đã cho.

• Kí hiệu: A k n là số các chỉnh hợp chập k của n phần tử, 1 ≤ k ≤ n.

(n−k)! = n.(n−1)ã ã ã(n−k+ 1) (với 1 ≤ k ≤ n). Nhận xét: Mỗi hoán vị của n phần tử cũng là một chỉnh hợp chập n của n phần tử đó nên Pn =A n n

Tổ hợp Định nghĩa 1.1.4 Giả sử tập A gồm n phần tử (n ≥ 1) Mỗi tập con gồm k phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho.

• Kí hiệu: C n k là số các tổ hợp chập k của n phần tử (0 ≤ k ≤ n).

• Số các tổ hợp: C n k = n! k! (n−k)! (với 1 ≤ k ≤ n).

Chỉnh hợp lặp là một khái niệm trong toán học, được định nghĩa như sau: cho tập A có m phần tử, chúng ta có thể rút ra một phần tử bất kỳ từ A, ký hiệu là a1, và sau đó trả lại nó vào tập hợp A Tiếp theo, chúng ta tiếp tục rút ra một phần tử khác, ký hiệu là a2, mà có thể chính là a1, và cũng trả lại vào A Quá trình này được lặp lại k lần (k không nhất thiết phải nhỏ hơn hoặc bằng m), từ đó ta thu được một dãy (a1, a2, , ak) gồm k phần tử, trong đó các phần tử có thể trùng nhau.

A Một dãy như thế gọi là một chỉnh hợp có lặp chập k của m phần tử đã cho. Tập hợp tất cả các chỉnh hợp có lặp chập k lập nên từ các phần tử của một tập hợp A cú m phần tử chớnh là tập hợp cỏc bộ (a 1 , a 2 ,ã ã ã , a k ) với a i ∈ A Vậy đú là tớch Đề-cỏc AìA ì ã ã ã ìA

=A k Định lý 1.1.1 Số chỉnh hợp có lặp chập k của m phần tử, kí hiệu là A k m , được tính theo công thức A k m = A k = m k

Có thể chọn một phần tử từ tập m phần tử cho mỗi vị trí trong k vị trí của chỉnh hợp khi cho phép lặp Do đó, theo quy tắc nhân, số lượng chỉnh hợp lặp chập k từ tập m phần tử là m^k.

Trong bài toán đếm, cần lưu ý rằng một số phần tử có thể giống nhau, do đó cần tránh việc đếm chúng nhiều lần Theo định lý 1.1.2, số hoán vị của n phần tử, trong đó có n1 phần tử giống nhau thuộc loại 1, n2 phần tử giống nhau thuộc loại 2, và tiếp tục cho đến nk phần tử giống nhau thuộc loại k, được tính bằng công thức n! / (n1! * n2! * * nk!).

Chứng minh Để xác định số hoán vị trước tiên chúng ta nhận thấy cóC n n 1 cách giữ n1 số cho n1 phần tử loại 1, còn lại n−n1 chỗ trống.

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 thêm các phần tử từ loại 3 đến loại k−1 vào các vị trí trống trong hoán vị Cuối cùng, số cách sắp xếp n phần tử loại k trong hoán vị là C(n−n1−n2−…−nk−1) Theo quy tắc nhân, tổng số hoán vị có thể được tính toán.

Tổ hợp lặp chập k của một tập hợp là cách chọn không có thứ tự k phần tử có thể lặp lại từ tập n phần tử, cho phép k lớn hơn n Theo định lý 1.1.3, số lượng tổ hợp lặp chập k từ tập n phần tử được tính bằng công thức C(n+k−1, k).

Mỗi tổ hợp lặp chập k từ tập n phần tử có thể được biểu diễn bằng một dãy n−1 thanh đứng, phân cách các ngăn Trong đó, ngăn thứ i sẽ chứa thêm một ngôi sao mỗi khi phần tử thứ i xuất hiện trong tổ hợp Do đó, mỗi dãy n−1 thanh và k ngôi sao tương ứng với một tổ hợp lặp chập k của n 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.

Số tổ hợp có lặp chập p của n được tính bằng công thức Cn p = C n+p−1 p = C n+p−1 n−1 Tổ hợp có lặp lại cho phép một phần tử xuất hiện nhiều lần mà không cần quan tâm đến thứ tự của các phần tử.

1.2 Một số nguyên lý, tính chất của toán tổ hợp thường được vận dụng vào giải bài toán đếm của toán tổ hợp

• Nguyên lý cộng: Nếu A, B là các tập hợp không giao nhau thì

• Nguyên lý cộng mở rộng: Nếu tập hợp hữu hạn C là hợp của n tập đôi một rời nhau C 1 , C 2 , ã ã ã , C n thỡ

|C| = |C1|+|C2|+ã ã ã+|Cn| Định nghĩa 1.2.1 Tích Descartes của hai tập hợp A, B kí hiệu bởi A×B là tập hợp tất cả các cặp thứ tự (a, b) với a ∈A, b ∈ B.

Nguyên lý nhân cho biết rằng nếu A và B là hai tập hợp hữu hạn, thì tích Descartes A×B cũng sẽ hữu hạn, với số lượng phần tử được tính bằng |A × B| = |A|.|B| Định nghĩa này có thể áp dụng cho nhiều tập hợp khác nhau, và nguyên lý nhân có thể được diễn đạt theo một cách khác.

Khi một quá trình diễn ra qua hai công đoạn, trong đó công đoạn I có n1 cách thực hiện và công đoạn II có n2 cách thực hiện sau khi hoàn thành công đoạn I, tổng số cách thực hiện toàn bộ quá trình sẽ là n1 nhân n2.

• Nguyên lý thêm bớt: Với hai tập hữu hạn A, B bất kỳ ta có

1.3 Một số phương pháp giải bài toán đếm của toán tổ hợp trong phạm vi chương trình toán THPT