Công thức tổ hợp chỉnh hợp

Công thức tổ hợp, chỉnh hợp

I. Lý thuyết

1. Tổ hợp

Cho tập hợp A có n phần tử và cho số nguyên k, (1≤k≤n). Mỗi tập hợp con của A có k phần tử được gọi là một tổ hợp chập k của n phần tử của A.

– Số các tổ hợp chập k của một tập hợp có n phần tử là: Cnk=n!(n−k)!k!=Ankk!.

– Tính chất:

Cn0=Cnn=1Cnk=Cnn−k,(0≤k≤n)Cn+1k+1=Cnk+Cnk+1,(1≤k≤n)

– Đặc điểm: Tổ hợp là chọn phần tử không quan trọng thứ tự, số phần tử được chọn là k: 0≤k≤n

Công thức tổ hợp: Cnk=n!(n−k)!k!=Ankk!

Công thức tính chất của tổ hợp:

Cn0=Cnn=1Cnk=Cnn−k,(0≤k≤n)Cn+1k+1=Cnk+Cnk+1,(1≤k≤n)

2. Chỉnh hợp

– Cho tập hợp A có n phần tử và cho số nguyên k, (1≤k≤n). Khi lấy k phần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A (gọi tắt là một chỉnh hợp n chập k của A).

– Số các chỉnh hợp chập k của một tập hợp có n phần tử là: Ank=n!(n−k)!.

– Một số quy ước: 0!=1,​  An0=1,  Ann=n!

– Đặc điểm: Đây là sắp xếp có thứ tự và số phần tử được sắp xếp là k: 0≤k≤n.

Ank=n!(n-k)!

II. Ví dụ minh họa

Ví dụ 1: Một tổ gồm 12 học sinh. Có bao nhiêu cách:

a) Chọn ra 2 bạn đại diện cho nhóm

b) Chọn ra 2 bạn, rồi phân công chứ vụ tổ trưởng và tổ phó

c) Chia tổ thành 2 nhóm, trong đó tổ trưởng và tổ phó khác nhóm

Lời giải

a) Chọn 2 bạn từ 12 bạn là tổ hợp chập 2 của 12: C122=66 cách.

b) Chọn 2 bạn rồi phân công chức vị là chỉnh hợp chập 2 của 12: A122=132 cách.

c) Chia tổ thành 2 nhóm tức mỗi nhóm có 6 bạn

Trong đó tổ trưởng và tổ phó khác nhóm

Chọn 5 bạn vào cùng nhóm với tổ trưởng trong 10 bạn còn lại: C105=252 cách.

Chọn 5 bạn vào cùng nhóm với tổ phó trong 5 bạn còn lại: C55=1 cách.

Vậy có 252.1 = 252 cách.

Ví dụ 2: Một đôi bóng có 11 cầu thủ, chuẩn bị đá penalty. Huấn luận viên muốn chọn ra 5 cầu thủ lần lượt lên đá penalty. Biết cả 11 cầu thủ đều có khả năng đá như nhau. Hỏi có bao nhiêu cách chọn cầu thủ lên đá bóng.

Lời giải

Số cách chọn và sắp xếp 5 cầu thủ lần lượt lên đá penalty là A115=55440cách.

III. Bài tập vận dụng

Bài 1: Từ các chữ số từ 0 đến 9. Có bao nhiêu cách lập một số tự nhiên sao cho:

a) Số có 6 chữ số khác nhau

b) Số có 6 chữ số khác nhau và chia hết cho 10

c) Số lẻ có 6 chữ số khác nhau

Lời giải

a) Lập số có 6 chữ số khác nhau

Chọn chữ số đầu tiên từ các số từ 1 đến 9: có 9 cách chọn

Các chữ số còn lại là chỉnh hợp chập 5 của 9 số còn lại (khác chữ số đầu tiên) có A95

Vậy có 9A95=136080 số.

b) Số có 6 chữ số khác nhau và chia hết cho 10

Chọn chữ số hàng đơn vị: có 1 cách chọn là chữ số 0

Chọn các chữ số còn lại là chỉnh hợp chập 5 của 9 số còn lại (khác chữ số 0) có A95

Vậy có A95=15120 số.

c) Gọi số abcdef¯ là số lẻ có 6 chữ số khác nhau được lập từ chữ số 0 đến 9

Vì abcdef¯ là số lẻ nên f∈1;3;5;7;9

Chọn f: có 5 cách chọn

Chọn a từ các chữ số {1; 2; 3; 4; 5; 6; 7; 8; 9}{f}: có 8 cách chọn

Chọn b, c, d, e là chỉnh hợp chập 4 của 8 chữ số còn lại (khác f và a): có A84

Vậy có 5.8A84=67200 số.

Bài 2: Một hộp có 15 viên bi đỏ và 5 viên bi xanh, 10 viên bi vàng. Có bao nhiêu cách chọn ra 5 viên sao cho

a) Các viên bi cùng màu

b) Số bi xanh bằng số bi đỏ, biết luôn có bi xanh và đỏ

c) Có ít nhất 1 viên bi xanh

Lời giải

a) Chọn 5 viên bi cùng màu

+ Trường hợp 1: Chọn được 5 viên bi màu đỏ: C155=3003 cách.

+ Trường hợp 2: Chọn được 5 viên bi màu xanh: có C55=1 cách.

+ Trường hợp 3: Chọn được 5 viên bi màu xanh: có C105=252 cách.

Vậy có 3003 + 1 + 252 = 3256 cách chọn.

b) Chọn được 5 viên bi trong đó số bi xanh bằng số bi đỏ

+ Trường hợp 1: có 1 viên bi xanh, 1 viên bi đỏ, 3 viên bi vàng: C51.C151.C103=9000 cách.

+ Trường hợp 2: có 2 viên bi xanh, 2 viên bi đỏ, 1 viên bi vàng: C52.C152.C101=10500 cách.

Vậy có 9000 + 10500 = 19500 cách chọn.

c) Chọn được ít nhất 1 viên bi xanh

Số cách chọn 5 viên bi bất kì là: C305=142506 cách.

Số cách chọn 5 viên trong đó không có bi xanh là: C255=53130 cách.

Vậy số cách chọn được ít nhất 1 viên bi xanh là: 142506 – 53130 = 89376 cách chọn.

Bài 3: Từ các chữ số 0; 1; 2; 3; 4; 5; 6; 7. Có thể lập được bao nhiêu số tự nhiên thỏa mãn

a) Số có 10 chữ số, trong đó chữ số 3 có mặt đúng 3 lần, các chữ số khác có mặt đúng một lần.

b) Số chẵn có 5 chữ số khác nhau.

c) Số có 6 chữ số khác nhau, trong đó chữ số 1 là hàng đơn vị.

d) Số có 6 chữ số khác nhau, trong đó chữ số 2 và 3 đứng cạnh nhau.

Lời giải

a) Giả sử số có 10 chữ số cần lập ở 10 vị trí như hình dưới

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

+ Số các số có 10 chữ số, chữ số 3 có mặt 3 lần, các chữ số khác có mặt đúng 1 lần (Kể cả chữ số 0 đứng đầu)

Chữ số 3 có mặt đúng 3 lần, ta chọn 3 vị trí để đặt số 3: có C103 cách chọn

Các chữ số khác có mặt đúng 1 lần là hoán vị của 7: có 7! cách chọn

Do đó có C103.7! số (kể cả số 0 đứng đầu).

+ Số các số có 10 chữ số, chữ số 3 có mặt 3 lần, các chữ số khác có mặt đúng 1 lần và chữ số 0 đứng đầu

Vị trí đầu tiên có 1 cách chọn (là chữ số 0)

Chữ số 3 có mặt đúng 3 lần, ta chọn 3 vị trí trong 9 vị trí còn lại để đặt số 3: có C93 cách chọn

Các chữ số khác có mặt đúng 1 lần là hoán vị của 6: có 6! cách chọn.

Do đó có C93.6!

Vậy có C103.7!−C93.6!=544320 số có 10 chữ số, trong đó chữ số 3 có mặt đúng 3 lần, các chữ số khác có mặt đúng một lần.

b) Gọi số abcde¯ là số chẵn có 5 chữ số trong các số trên

Vì abcde¯ là số chẵn nên e∈0;2;4;6

+ Trường hợp 1: e = 0

Số cách chọn a, b, c, d trong 7 số còn lại là A74

Do đó có A74.

+ Trường hợp 2: e∈2;4;6

Chọn e: có 3 cách chọn

Chọn a từ các số {1; 2; 3; 4; 5; 6; 7}{e}: có 6 cách chọn

Chọn b, c, d từ các số {0; 1; 2; 3; 4; 5; 6; 7}{a, e}: có A63

Do đó có 3.6.A63 số

Vậy có A74+3.6.A63=3000 số chẵn có 5 chữ số khác nhau được lập từ các chữ số trên.

c) Giả sử số có 6 chữ số cần lập ở 6 vị trí như hình dưới

(1)

(2)

(3)

(4)

(5)

(6)

Lập số có 6 chữ số khác nhau, chữ số 1 ở hàng đơn vị

Vị trí (6) có 1 cách chọn (là chữ số 1)

Vị trí (1) có 6 cách chọn (là các chữ số 2; 3; 4; 5; 6; 7)

Bốn vị trí còn lại là chỉnh hợp chập 4 của 6 số còn lại: có A64 số

Vậy có 1.6.A64=2160 số có 6 chữ số, trong đó chữ số 1 là hàng đơn vị.

d) Để lập số có số 2 và 3 đứng cạnh nhau ta ghép số 2 và 3 với nhau, đặt vào 1 vị trí.

Giả sử số có 6 chữ số cần lập ở 5 vị trí như hình dưới

(1)

(2)

(3)

(4)

(5)

Vị trí (1) có 6 cách chọn (là 1; 2 và 3; 4; 5; 6; 7)

Các vị trí còn lại có là chỉnh hợp chập 4 của 6 số còn lại: có A64

Ở vị chí chứa số 2 và 3: có 2! cách sắp xếp chữ số 2 và 3.

Vậy có 6.A64.2!=4230 số có 6 chữ số khác nhau, trong đó chữ số 2 và 3 đứng cạnh nhau.

Bài 4: Có 7 học sinh nữ và 3 học sinh nam. Ta muốn sắp xếp vào một bàn dài có 5 ghế ngồi. Hỏi có bao nhiêu cách sắp xếp để:

a) Sắp xếp tùy ý.

b) Các bạn nam ngồi cạnh nhau và các bạn nữ ngồi cạnh nhau.

c) 3 học sinh nam ngồi kề nhau.

d) Không có 2 bạn nam nào ngồi cạnh nhau.

Lời giải

a) Sắp xếp 10 bạn tùy ý là hoán vị của 10: có 10! cách xếp.

b) Xếp các 7 bạn nữ ngồi cạnh nhau và 3 bạn nam ngồi cạnh nhau. Ta ghép tất cả 7 bạn nữ vào 1 “bó”, 3 bạn nam vào 1 “bó”

Rồi mang sắp xếp 2 “bó” ta được 2! cách xếp.

Trong 7 bạn nữ: ta có 7! cách xếp

Trong 3 bạn nam: ta có 3! cách xếp

Vậy có 2! . 7! . 3! = 60480 cách xếp.

c) Xếp 3 bạn nam ngồi cạnh nhau. Ta ghép 3 bạn nam vào 1 “bó”

Rồi mang sắp xếp 7 bạn nữ và 1 “bó” ta được 8! cách xếp

Trong 3 bạn nam: ta có 3! cách xếp

Vậy có 8! . 3! = 241920 cách xếp.

d) Để xếp không có bạn nam nào ngồi cạnh nhau, ta sắp xếp 7 bạn nữ vào bàn dài trước: ta được 7! cách xếp

Khi đó tạo ra 8 khoảng trống (là 6 khoảng trống giữa 2 bạn nữ và 2 khoảng trống ngoài cùng)

Ta xếp 3 bạn nam vào 3 khoảng trống bất kì (mỗi bạn ở 1 khoảng trống): ta được A83.

Vậy có 7!.A83=1693440 cách xếp.

Bài 5: Xếp 6 người A, B, C, D, E, F vào một ghế dài. Hỏi có bao nhiêu cách sắp xếp sao cho:

a) A và F ngồi ở hai đầu ghế.

b) A và F ngồi cạnh nhau.

c) A và F không ngồi cạnh nhau.

Lời giải

a) Xếp A và F ở hai đầu ghế: có 2! cách xếp A và F

Các vị trí ở giữa: có 4! cách xếp

Vậy có 2! . 4! = 48 cách xếp sao cho A và F ở hai đầu ghế.

b) Xếp A và F ngồi cạnh nhau ta ghép A và F thành 1 “bó”: có 2 ! cách sắp xếp vị trí bên trong “bó”

Rồi mang sắp xếp 4 người còn lại và 1 “bó” trên ghế dài: ta được 5! cách xếp

Vậy có 2! . 5! = 240 cách xếp sao cho A và F ngồi cạnh nhau.

c) Số cách xếp 6 người bất kì là 6! cách

Số cách xếp sao cho A và F ngồi cạnh nhau là 240 cách (câu c)

Vậy có 6! – 240 = 480 cách xếp sao cho A và F không ngồi cạnh nhau.

Bài 6: Một hộp chứ 6 viên bi trắng và 5 viên bi xanh, 9 viên bi đỏ. Lấy 4 viên bi từ hộp, có bao nhiêu cách lấy được:

a) 4 viên cùng màu.

b) 2 viên bi trắng và 2 viên bi xanh.

c) Có ít nhất 1 viên màu đỏ.

d) Có đủ ba màu.

Lời giải

a) Trường hợp 1: Lấy được 4 viên bi cùng màu trắng: C64 cách

Trường hợp 2: Lấy được 4 viên bi cùng màu xanh: C54 cách

Trường hợp 3: Lấy được 4 viên bi cùng màu đỏ: C94 cách

Vậy có C64+C54+C94=146 cách bi chọn 4 viên bi cùng màu.

b) Chọn được 2 viên bi trắng: có C62 cách

Chọn được 2 viên bi xanh: có C52 cách

Vậy có C62.C52=150 cách chọn 2 viên bi trắng và 2 viên bi xanh.

c) Số cách chọn 4 viên bi bất kì (có tất cả 20 viên): có C204 cách

Số cách chọn 4 viên bi không có màu đỏ (Còn lại 6 + 5 = 11 viên bi không phải màu đỏ): có C114 cách

Vậy có C204−C114=4515 cách chọn được ít nhất 1 viên màu đỏ.

d) Trường hợp 1: Chọn được 2 viên bi trắng, 1 viên bi xanh, 1 viên bi đỏ: có C62.C51.C91 cách

Trường hợp 2: Chọn được 1 viên bi trắng, 2 viên bi xanh, 1 viên bi đỏ: có C61.C52.C91 cách

Trường hợp 3: Chọn được 1 viên bi trắng, 1 viên bi xanh, 2 viên bi đỏ: có C61.C51.C92 cách

Vậy có C62.C51.C91+C61.C52.C91+C61.C51.C92=2295 cách chọn 4 viên bi có đủ ba màu.

Bài 7: Một lớp học có 40 học sinh. Có bao nhiêu cách chọn ra 5 bạn

a) Chọn bất kì

b) Chọn 5 bạn rồi phân công chức vụ, trong đó có 1 lớp trưởng, 1 bí thứ, 1 thư kí và 2 lớp phó.

Lời giải

a) Chọn bất kì 5 bạn trong 40 học sinh: có C405 cách chọn.

b) Chọn 3 bạn, trong đó có 1 lớp trưởng, 1 bí thư, 1 thư kí: có A403 cách

Chọn 2 bạn trong 37 bạn còn lại làm lớp phó: có C372 cách.

Vậy có A403.C372 cách chọn.

Bài 8: Cho đa giác lồi n cạnh.

a) Có bao nhiêu vectơ khác vectơ không, có điểm đầu và điểm cuối là 2 đỉnh của đa giác.

b) Có bao nhiêu đường chéo của đa giác.

c) Có bao nhiêu tam giác có 3 đỉnh là 3 đỉnh của đa giác trên.

Lời giải

a) Có An2 vectơ khác vectơ không, có điểm đầu và điểm cuối là 2 đỉnh của đa giác.

b) Số đoạn thẳng được tạo ra từ n đỉnh của đa giác là: Cn2 đoạn thẳng

Trong đó có n đoạn thẳng là cạnh của đa giác

Vậy có Cn2−n đường chéo trong đa giác n cạnh.

c) Có Cn3 tam giác có 3 đỉnh là 3 đỉnh của đa giác trên.

Bài 9: Trong mặt phẳng có 2020 đường thẳng song song với nhau và 2021 đường thẳng song song khác cùng cắt nhóm 2020 đường thẳng đó. Có bao nhiêu hình bình hành được tạo ra từ các đường thẳng song song đó.

Lời giải

Hình bình hành được tạo ra bởi hai cặp đường thẳng đối nhau song song với nhau.

Từ 2020 đường thẳng song song, chọn 2 đường thẳng: có C20202 cách

Từ 2021 đường thẳng song song khác, chọn 2 đường thẳng: có C20212 cách

Vậy có C20202.C20212 hình bình hành được tạo ra.