ĐẠI HỌC THÁI NGUN
TRƯỜNG ĐẠI HỌC KHOA HỌC
- - - - - - - - - - - - - - - - - -
Lê Quang Việt
MỘT SỐ PHƯƠNG PHÁP VÀ KỸ
THUẬT ĐẾM CƠ BẢN TRONG LÝ
THUYẾT TỔ HỢP VÀ ÁP DỤNG
LUẬN VĂN THẠC SỸ TỐN HỌC
Chun ngành: PHƯƠNG PHÁP TỐN SƠ CẤP
Mã số: 60460113
Người hướng dẫn khoa học
GS. TSKH. NGUYỄN VĂN MẬU
THÁI NGUN - NĂM 2013
Số hóa bởi trung tâm học liệu />1
.
Số hóa bởi trung tâm học liệu />2
Mục lục
Mở đầu 4
Lời cảm ơn 5
1 Các quy tắc đếm cơ bản trong tổ hợp 6
1.1 Một số kiến thức cơ bản của tổ hợp . . . . . . . . . . . . . . 6
1.1.1 Tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Cơng thức tính lực lượng của tập hợp . . . . . . . . . 7
1.1.3 Cơng thức bao hàm và loại trừ . . . . . . . . . . . . . 9
1.2 Hai quy tắc cơ bản của phép đếm . . . . . . . . . . . . . . . 10
1.2.1 Quy tắc cộng . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Quy tắc nhân . . . . . . . . . . . . . . . . . . . . . 12
1.3 Hốn vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1 Hốn vị khơng lặp . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Hốn vị có lặp . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

trọng và có ứng dụng vơ cùng đa dạng. Các phương pháp đếm số lượng phần
tử của một tập hợp đóng vai trò quan trọng trong một số mơn khoa học,
đặc biệt là Tin học và Tốn học ứng dụng. Đối với chương trình tốn phổ
thơng các phương pháp đếm ln là chun đề quan trọng và hết sức cần
thiết trong việc bồi dưỡng học sinh giỏi Tốn ở bậc học phổ thơng, đồng thời
các ứng dụng đa dạng của nó cũng ln đem lại sự hấp dẫn đối với nhiều đối
tượng học sinh và giáo viên khi nghiên cứu vấn đề này.
Mục tiêu của Luận văn " Một số phương pháp và kĩ thuật đếm cơ bản trong
lý thuyết tổ hợp và áp dụng" nhằm trình bày một số phép đếm cơ bản nhất
và những ứng dụng của nó nhằm tạo ra được một đề tài phù hợp cho việc
giảng dạy, bồi dưỡng học sinh trung học phổ thơng.
Luận văn bao gồm phần mở đầu, kết luận, tài liệu tham khảo và 3 Chương.
Chương 1 trình bày tóm tắt một số kiến thức cơ bản của tổ hợp và các quy
tắc cơ bản của phép đếm. Trong chương này cũng trình bày một số ví dụ và
các bài tốn về tính lực lượng tập hợp, bài tốn về khai triển nhị thức.
Chương 2 trình bày các phương pháp đếm bằng hàm sinh thơng thường và
phương pháp đếm bằng hàm sinh mũ cùng các ví dụ áp dụng.
Chương 3 trình bày các phương pháp đếm bằng các cơng thức nghịch đảo
các đồng nhất thức tổ hợp bao gồm cơng thức nghịch đảo nhị thức, nghịch
đảo Stirling, cơng thức sàng và các ví dụ áp dụng.
Số hóa bởi trung tâm học liệu />5
Lời cảm ơn
Trong suốt q trình làm luận văn, tơi ln nhận được sự hướng dẫn và
giúp đỡ tận tình của GS.TSKH Nguyễn Văn Mậu. Tơi xin được bày tỏ lòng
biết ơn sâu sắc nhất đến thầy.
Trong q trình học tập tơi cũng đã nhận được sự quan tâm giúp đỡ và sự
giảng dạy nhiệt tình của các Thầy, các Cơ dạy lớp cao học tốn K5B (2011
-2013), tơi xin được bày tỏ lòng biết ơn đến các Thầy, các Cơ.
Tơi xin chân thành cảm ơn các Thầy cơ trong BGH trường ĐH Khoa Học -
ĐH Thái Ngun đã tạo kiều kiện thuận lợi cho tơi trong suốt thời gian học

− 3x + 2 ≥ 0

Tập con.
- Tất cả các phần tử của tập B đều thuộc tập A thì ta nói tập B là tập con
của tập A và viết B ⊆ A
- Trường hợp B ⊆ A và B = A thì B được gọi là tập con khơng tầm thường
Số hóa bởi trung tâm học liệu />7
(hay tập con thực sự) của tập A và viết B ⊂ A
Tập rỗng
-Tập hợp rỗng (hay tập hợp trống) là tập hợp khơng chứa một phần tử nào
và thường được ký hiệu là ∅
- Quy ước tập rỗng là con của bất kỳ tập nào
Hợp, giao, hiệu và phần bù của hai tập hợp.
Giả sử có các tập A, B.
- Tập hợp gồm các phần tử hoặc thuộc tập A hoặc thuộc tập B được gọi là
hợp của tập A và tập B và ký hiệu là A ∪ B hoặc A ∨ B.
- Tập hợp gồm các phần tử thuộc đồng thời cả tập A và tập B được gọi là
giao của tập A và tập B ký hiệu là A ∩ B hoặc A ∧ B.
- Tập hợp gồm các phần tử thuộc tập A mà khơng thuộc tập B được gọi là
hiệu của tập A và tập B. Kí hiệu A\B
- Trường hợp tập B là tập con của tập A. Hiệu của tập A và tập B được
gọi là tập phần bù (hay phần bù) của tập B (đối với tập A) và ký hiệu hoặc
bằng hoặc bằng C
A
(B) hoặc bằng C (B).
Lực lượng của tập hợp.
Giả sử có tập A. Số phần tử trong tập A được gọi là lực lượng của tập A,
ký hiệu là |A|.
1.1.2 Cơng thức tính lực lượng của tập hợp
Với hai tập hợp V

| = |V
1
| + |V
2
| + |V
3
| − |V
1
∩ V
2
| − |V
2
∩ V
3
| − |V
1
∩ V
3
| +
|V
1
∩ V
2
∩ V
3
|. (1.2)
Tổng qt với các tập tùy ý V
1
, V
2

|
V
i
∩
V
j
| + |
V
1
∩
V
2
∩
V
3
| + |
V
1
∩
V
2
∩
V
4
|
+ ··· + |
V
n−2
∩
V

V
3
số học sinh chơi thể thao.
Khi đó
|V
1
∪ V
2
∪ V
3
| = |V
1
|+|V
2
|+|V
3
|−|V
1
∩ V
2
|−|V
2
∩ V
3
|−|V
1
∩ V
3
|+|V
1

Vật Lý, Ngữ Văn, Lịch Sử. Đặt T
l
= T ∩L, L
v
= L ∩V, V
s
= S ∩ V . Từ giả
thiết suy ra: |T
l
| >
2
3
|T |, |L
v
| >
2
3
|L|, |V
s
| >
2
3
|V |
Ta cần chứng minh : |T ∩L ∩V ∩S| > 0.
Vì T ∩ L ∩ V ∩ S = (T ∩ L) ∩ (L ∩V ) ∩ (V ∩ S) nên ta cần chứng minh
|(T ∩L) ∩(L ∩V ) ∩(V ∩ S)| > 0.
Thật vậy, khơng mất tính tổng qt, giả sử |T | ≥ |L| ≥ |V | ≥ |S|. Ta có
|T
l
∩ L

∪ L
v
| − |(T
l
∩ L
v
) ∪ V
s
|
>
2
3
|T |+
2
3
|L| +
2
3
|V | − |L| − |V | =
2
3
|T |−
1
3
|L| −
1
3
|V |
≥
2

⊂ V . Khi đó


V
1
∩ V
2


= |V | − |V
1
∪ V
1
| = |V | − |V
1
| − |V
1
| + |V
1
∩ V
1
|. (1.5)
Cho tập hợp V và V
1
, V
2
, V
3
⊂ V . Khi đó.


|+ |V
1
∩ V
3
|−|V
1
∩ V
2
∩ V
3
|.
(1.6)
Tổng qt với các tập tùy ý V
1
, V
2
, . . . , V
n
⊂ V bằng phương pháp quy nạp
theo n (n ≥ 2) ta có cơng thức





n

i=1
V
i

| − |
V
1
∩
V
2
∩
V
4
|
−··· − |
V
n−2
∩
V
n−1
∩
V
n
| + ··· + (−1)
n
|
V
1
∩
V
2
∩··· ∩
V
n

Khi đó số vận động viên khơng tham gia mơn nào của Hội thao chính bằng
lực lượng của tập V
1
∩ V
2
∩ V
3
∩ V
4
:


V
1
∩ V
2
∩ V
3
∩ V
4


= 100 − (18 + 26 + 19 + 24)+
+(5 + 2 + 3 + 5 + 4 + 3) − (2 + 3 + 2 + 4) + 1 = 25
Vậy có 25 người khơng tham gia thi đấu mơn nào của Hội thao.
1.2 Hai quy tắc cơ bản của phép đếm
1.2.1 Quy tắc cộng
Nội dung quy tắc: Giả sử có n hành động H
1
, H

n
với |V
k
| = m
k
(1 ≤ k ≤ n) và ∀i, j(1 ≤ i, j ≤ n)V
i
∩ V
j
= ∅
khi i = j. Khi đó số cách thực hiện hành động H
1
, hoặc H
2
, . . ., hoặc H
n
sẽ
bằng số cách chọn phần tử v thuộc

n
k=1
V
k
và bằng |

n
i=1
A
k
| =

= 0
4 cách chọn a
1
= 0
3 cách chọn a
2
= 0
2 cách chọn a
3
= 0
1 cách chọn a
4
= 0
Vậy ta có 1 × 4 × 3 × 2 × 1 = 24 số n.
Trường hợp 2 a
5
= 0 thì ta có
2 cách chọn a
5
( vì a
5
= 2 hoặc a
5
= 6)
3 cách chọn a
1
3 cách chọn a
2
2 cách chọn a
3

Tính các số n có bốn chữ số và có chữ số lập lại đúng ba lần.
+) Trường hợp 1 : Ta có 9 cách chọn a
1
(a
1
= 0, a
1
lặp lại ba lần)
Chọn a
2
= a
3
= a
1
, có 1 cách chọn.
Chọn a
4
= a
1
, 9 cách chọn.
Vậy ta có 9 × 9 = 81 cách.
+) Trường hợp 2 : Chọn a
1
= 0 có 9 cách.
Chọn a
2
= a
3
= a
4

Vậy ta có 9 × 9 = 81 cách.
+) Trường hợp 4 : Chọn a
1
= 0 có 9 cách.
Chọn a
2
= a
3
= a
4
, có 1 cách (a
4
lặp lại 3 lần)
Vậy ta có 9 × 9 = 81 cách.
Từ 4 trường hợp ta có 81 + 81 + 81 + 81 = 324 số n có một chữ số lặp lại
đúng ba lần.
Do đó các số n thỏa mãn u cầu bài tốn là 9000 − 324 = 8676 số.
1.2.2 Quy tắc nhân
Nội dung quy tắc : Giả sử một hành động H bao gồm n giai đoạn kế tiếp
và độc lập với nhau, trong đó giai đoạn thứ i là hành động H
i
, (1 ≤ i ≤ n).
Ta cũng giả sử rằng hành động H
i
có m
i
, (1 ≤ i ≤ n) cách thực hiện. Khi
Số hóa bởi trung tâm học liệu />13
đó hành động H sẽ có m
1

n
| = m
1
m
2
. . . m
n
Ví dụ 1.6. Từ thành phố A đến thành phố B có 3 con đường, từ thành phố
B đến thành phố C có 4 con đường. Một ơ tơ trở hàng từ thành phố A đến
C rồi quay lại thành phố A ( cả hai lượt đi và về ơ tơ đều đi qua B) . Hỏi
có tất cả bao nhiêu cách đi sao cho đoạn đường lúc đi khơng trùng với đoạn
đường về.
Giải.
Tìm đường đi từ A đến B có 3 còn đường, đi từ B đến C có 4 con đường.
Vậy ta có 3 × 4 = 12 con đường đi từ A đến C qua B.
Tìm đường đi từ C về B có 3 con đường, đi từ B về A có 2 ( vì đoạn đường
lúc đi khơng trùng với đoạn đường về)
Vậy ta có 3 × 2 = 6 con đường đi từ C về A qua B.
Do đó ta sẽ có 12 ×6 = 72 cách đi từ thành phố A đến thành phố C rồi quay
lại thành phố A sao cho đoạn đường lúc đi khơng trùng với đoạn đường về.
Ví dụ 1.7. Từ các số 0,1,2,3,4,5,6 có thể lập được bao nhiêu số tự nhiên có
5 chữ số khác nhau đơi một mà bắt buộc phải có chữ số 5.
Giải.
Gọi n = a
1
a
2
a
3
a

5 cách chọn a
1
( vì a
1
= 0, a
1
= 5)
1 cách chọn a
2
5 cách chọn a
3
4 cách chọn a
4
3 cách chọn a
5
Trong trường hợp này ta có 4 × 5 × 1 × 5 × 4 × 3 = 1200 số n.
Vậy tổng hai trường hợp ta có 1200 + 360 = 1560 số n.
1.3 Hốn vị
Hốn vị thực chất là một cách sắp xếp nào đó các phần tử của một tập
hợp.
1.3.1 Hốn vị khơng lặp
Định nghĩa 1.1 ([1]-[4]). Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi
cách sắp xếp n phần tử này theo một tứ tự nào đó (mỗi phần tử có mặt đúng
một lần) được gọi là một hốn vị của n phần tử đã cho. Kí hiệu số hốn vị
của n phần tử bằng P
n
.
Ta có cơng thức: P
n
= n!

n
(k) là số
hốn vị của tập S có đúng k điểm cố định. Hãy chứng minh rằng
n

k=0
kP
n
(k) = n! (1.8)
Giải.
1) Vì tổng tất cả các hốn vị của n phần tử có 0,1,2,. . . ,n điểm cố định bằng
tất cả các hốn vị có thể của n phần tử, tức bằng n!, nên có đẳng thức
n

k=0
P
n
(k) = n! (1.9)
2) Ta chứng minh rằng: ∀k (1 ≤ k ≤ n)đều có kP
n
(k) = n.P
n−1
(k −1) Dùng
(f, i) để kí hiệu cặp gồm hốn vị f tùy ý của n phần tử với k điểm cố định
và i là điểm tùy ý trong k điểm cố định đó ( tức f(i) = i ).
Thừa nhận P
0
(0) = 1
Để lý giải quan hệ (1.11), ta hãy tính số N cáp cặp (f,i) bằng hai cách. Một
mặt, i chạy qua k điểm cố định đã xác định, nên mỗi hốn vị trong P

k=1
P
n−1
(k −1) = n (n −1)! = n!.
1.3.2 Hốn vị có lặp
Định nghĩa 1.2. Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp
xếp n phần tử này theo một tứ tự nào đó (mỗi phần tử có mặt ít nhất một
lần) được gọi là là hốn vị lặp.
Số hốn vị lặp của n phần tử thuộc k loại, mà các phần tử loại i(1 ≤ i ≤ k)
xuất hiên n
i
luần được kí hiệu là P (n
1
, n
2
, . . . , n
k
) và được tính bằng cơng
thức
P (n
1
, n
2
, . . . , n
k
) =
n!
n
1
!n

2
a
3
a
7
là
6!
3!
.
Vậy số các số n đúng u cầu bài tốn là :
7!
3!
−
6!
3!
= 720 số.
Ví dụ 1.12. Với sáu chữ số 0,1,2,3,4,5 có thể lập được bao nhiêu số chia hết
cho 5 gồm 11 chữ số, trong đó chữ số 1 có mặt 4 lần, chữ số 2 có mặt 3 lần,
chữ số 3 có mặt 2 lần, chữ số 4 có mặt 1 lần và tổng số lần xuất hiện của
chữ số 0 và chữ số 5 là 1.
Giải.
Gọi số cần lập là n = a
1
a
2
a
3
a
11
. Do n chia hết cho 5 nên n phải tận cùng

của n phần tử thuộc A.
Kí hiệu số chỉnh hợp chập k của n phần tử bằng A
k
n
. Số chỉnh hợp chập k
của n phần tử được tính bởi cơng thức
A
k
n
= n(n − 1) (n − k + 1) =
n!
(n − k)!
Ví dụ 1.13. Một lớp học có 25 học sinh. Muốn chọn ra một lớp trưởng, một
lớp phó và một thủ quỹ mà khơng cho kiêm nhiệm. Hỏi có bao nhiêu cách
chọn ?
Giải.
Mỗi cách chọn tra một lớp trưởng, một lớp phó và một thủ quỹ là một chỉnh
hợp chập ba 3 của tập 25 phần tử.
Số các chỉnh hợp là :
A
3
25
=
25!
(25 − 3)!
= 13800
Vậy có 13800 cách chọn ra một lớp trưởng, một lớp phó và một thủ quỹ trong
lớp học có 25 học sinh.
Số hóa bởi trung tâm học liệu />18
Ví dụ 1.14. Từ các số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên

để kí hiệu tập số dạng a
1
a
2
a
3
a
4
Dùng S
5
để kí hiệu tập số dạng a
1
a
2
a
3
a
4
a
5
Dùng S
6
để kí hiệu tập số dạng a
1
a
2
a
3
a
4

= 0. Ngược lại,
nếu C
i1
= 0, thì nó khơng tương ứng với số tự nhiên gồm k chữ số. Nhưng
tương ứng với một chỉnh hợp chập k – 1 (C
i2
, C
i3
. . . , C
ik
) của năm phần tử
1, 2, 3, 4, 5. Từ đó có
|S
6
| = A
6
6
− A
5
5
=
6!
0!
−
5!
0!
= 720 − 120 = 600;
|S
5
| = A

2
5
= 25;
|S
1
| = 6
Vậy các số tự nhiên có thể lập là:
S = |S
1
|+|S
2
|+|S
3
|+|S
4
|+|S
5
|+|S
6
| = 6+25 +100 +300+600+600 = 1631.
Số hóa bởi trung tâm học liệu />19
Ví dụ 1.15. ( Bài tốn đếm số tất cả các hàm đơn ánh từ một tập hữu hạn
vào một tập hữu hạn) Giả sử N và M là hai tập hữu hạn với |N| = n và
|M| = m . Hãy xác định số các hàm đơn ánh f : N → M.
Giải.
Giả sử N = {a
1
, a
2
, , a

các phần tử của tập X, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp
xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n
phần tử thuộc tập X.
Số chỉnh hợp lặp chập k của n phần tử, ký hiệu là A
k
n
, bằng số ánh xạ từ tập
k phần tử đến tập n phần tử và bằng n
k
, tức A
k
n
= n
k
.
Ví dụ 1.16. Từ bốn chữ số 1, 2, 3, 5 có thể thành lập được bao nhiêu số
chẵn gồm 4 chữ số?
Giải.
Vì tập 1, 2, 3, 5 chỉ có duy nhất một chữ số chẵn là 2, nên x = abcd với a, b,
c, d thuộc tập 1, 2, 3, 5 là số chẵn khi và chỉ khi d bằng 2.
Mặt khác a, b, c có thể bằng nhau, nên y = abc là một chỉnh hợp lặp chập
3 của bốn phần tử 1, 2, 3, 5.
Để thành lập số x ta chỉ cần lấy một số y nào đó rồi thêm 2 vào cuối. Bởi
vậy, số các số x = abc2 bằng các số y = abc và bằng A
3
4
= 4
3
= 64.
Chẳng hạn 1112, 1122, 1132, 1152, . . . , 5542, 5552.

= m
n
Vậy ta có số tất cả các hàm f : N → M với |N| = n và |M| = m bằng
A
n
m
= m
n
1.5 Tổ hợp
1.5.1 Tổ hợp khơng lặp
Định nghĩa 1.5. Cho tập A gồm n phần tử. Mỗi tập con gồm k (0 ≤ k ≤ n)
phần tử thuộc A được gọi là tổ hợp chập k của n phần tử đã cho.
Nhận xét 1.1. Hai tổ hợp được coi là khác nhau khi và chỉ khi có ít nhất
một phần tử khác nhau.
Số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử, được kí hiệu là

n
k

và được
tính theo cơng thức

n
k

=
n!
k!(n−k )!
Ví dụ 1.18. Có bao nhiêu cách chia một lớp 40 học sinh thành bốn tổ, sao
cho mỗi tổ có đúng 10 học sinh.

Vậy số cách chia lớp sẽ là:

40
10

×

30
10

×

20
10

×

10
10

=
40!30!20!
10!30!20!10!10!10!
=
40!
(10!)
4
1.5.2 Tổ hợp có lặp
Định nghĩa 1.6. Cho tập hợp A = a
1

Giả sử a
1
là một máy vi tính thuộc loại máy 1; a
2
là một máy vi tính thuộc loại
máy 2; , a
10
là một máy vi tính thuộc loại máy 10, và A = {a
1
, a
2
, . . . , a
10
}.
Mỗi cách chọn 5 máy vi tính có thể coi là một tổ hợp chập 10 của 5 và tổng
số các tổ hợp được tính theo cơng thức.

5
10

∗
=

10 + 5 − 1
5

=

14
5

9!
6!3!
= 84
1.5.3 Khai triển lũy thừa của nhị thức
Đồng nhất thức Pascal
Cơng thức

m + 1
k

=

m
k

+

m
k −1

Tam giác Pascal, trong đó số bắt đầu và kết thúc của mỗi dòng trong tam
giác Pascal là số 1, và mỗi số khác của mỗi dòng bằng tổng của hai số của
dòng trên nó.

0
0

= 1

1

1

= 3

3
2

= 3

3
2

= 1

4
0

= 1

4
1

= 4

4
2

= 6

4

Giả sử (1.12) đã được chứng minh và đúng với n = k. Khi đó :
(x + y)
k+1
= (x + y)
k
(x + y)
=

k

i=0

k
i

x
i
y
k−i

(x + y)
=
k

i=0

k
i

x

x
i+1
y
k−i
+
k

i=1

k
i

x
i
y
k−i+1
+

k
0

y
k+1
=

k + 1
k + 1

x
k+1

+

k
i + 1

=

k + 1
i + 1

Vì vậy từ đẳng thức (1.11) ta có
(x + y)
k+1
=

k + 1
k + 1

x
k+1
+
k−1

i=0

k + 1
i + 1

x
i+1

x
5
+

5
1

x
4
y+

5
2

x
3
y
2
+

5
3

x
2
y
3
+

5

5
+ 240x
4
+ 720x
3
+ 1080x
2
+ 810x + 243
1.5.4 Tính số phần tử của một tập hợp các tập hợp
Ví dụ 1.22 (Ví dụ dẫn dắt). Lớp 12A phải làm một bài kiểm tra Tốn gồm
có ba bài tốn. Biết rằng mỗi em trong lớp đều giải được ít nhất một bài,
trong lớp có 20 em giải được bài tốn thứ nhất, 14 em giải được bài tốn
Số hóa bởi trung tâm học liệu />24
thứ hai, 10 em giải được bài tốn thứ ba, 6 em giải được cả hai bài tốn thứ
nhất và thứ ba, 5 em giải được cả hai bài thứ hai và thứ ba, 2 em giải được
cả hai bài thứ nhất và thứ hai, và có một em được 10 điểm vì đã giải được
cả ba bài tốn. Hỏi rằng lớp học có bao nhiều em tất cả ?
Giải.
Gọi A là tập hợp các em học sinh giải được bài tốn thứ nhất.
B là tập hợp các em học sinh giải được bài tốn thứ 2
C là tập hợp các em học sinh giải được bài tốn thứ 3
Ta phải tính số phần tử của tập hợp A ∪ B ∪ C
Khơng khó khăn ta có thể thấy được cơng thức sau là đúng:
|A ∪ B ∪ C| = |A|+|B|+|C|−|A ∩ B|−|B ∩ C|−|C ∩ A|+|A ∩ B ∩ C|.
Theo cơng thức trên, số học sinh trong lớp sẽ là:
20 + 14 + 10 − 6 − 5 − 2 + 1 = 32.
Nhưng ta có thể bắt gặp những bài tốn có sự tham gia của nhiều hơn ba
tập hợp con.
Ví dụ 1.23. Tính số cách treo 5 đơi tất trên một dây phơi sao cho khơng
có hai chiếc tất nào cùng đơi được phơi cạnh nhau.

n−1
|V
1
∩ V
2
∩ ∩ V
n
| (1.12)
Chứng minh.
Định lý này có thể được chứng minh bằng hai cách:
Số hóa bởi trung tâm học liệu />