Định nghĩa 0.0.1. Khi hai công việc có thể được làm đồng thời, ta không thể dùng
quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách
thực hiện nhiệm vụ này, ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách
làm đồng thời cả hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập
hợp. Cho A
1
, A
2
là hai tập hữu hạn, khi đó
| A
1
∪ A
2
|=| A
1
| + | A
2
| − | A
1
∩ A
2
| .
Từ đó, với ba tập hữu hạn A
1
, A
2
, A
3
, ta có:
| A
1

và bằng quy nạp, với k tập hữu hạn A
1
, A
2
, ..., A
k
, ta có:
| A
1
∪ A
2
∪ ... ∪ A
k
|= N
1
− N
2
+ N
3
− · · · + (−1)
k−1
N
k
,
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à
N
m

∪ A
2
∪ ... ∪ A
k
|= N − N
1
+ N
2
− N
3
+ · · · + (−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ừ.
Ví dụ 0.0.1.
1) Có bao nhiêu số nguyên dương từ 1 đến 1000 mà không chia hết cho 2, không
chia hết cho 3 và cũng không chia hết cho 7?
Ký hiệu A = {1, 2, ..., 1000}, A
2
= {a ∈ A | a chia hết cho 2}, A
3
= {a ∈ A |
a chia hết cho 3}, A
7
= {a ∈ A | a chia hết cho 7}. Theo nguyên lý bù trừ, số các số

3
∩ A
7
|,
trong đó, |A
2
| = [1000/2] = 500, |A
3
| = [1000/3] = 333, |A
7
| = [1000/7] = 142,
|A
2
∩ A
3
| = [1000/6] = 166, |A
2
∩ A
7
| = [1000/14] = 71, |A
3
∩ A
7
| = [1000/21] =
47, |A
2
∩ A
3
∩ A
7

N
m
= C
m
n
(n − m)! =
n!
m!(n − m)!
(n − m)! =
n!
m!
.
N = n!

1 −
1
1!
+
1
2!
− · · · + (−1)
n
1
n!

,
trong đó C
m
n
là tổ hợp chập m của tập n phần tử (xem Mục 1.4). Xác suất cần tìm là:

m
), mà là các phần tử của một vành giao hoán K nào đó.
Mỗi vật a
i
đã cho có thể có hay không có các tính chất P
1
, P
2
, ..., P
n
. Ký hiệu
S
0
=
m

i=1
ω(a
i
), S
k
=

1≤i
1
<i
2
<···<i
k
≤n

M
r
là tổng trọng số của tất cả các vật có không ít hơn r tính chất.
Định lý 0.1.1 (Nguyên lý bù trừ suy rộng).
M(r) =
n

k=r
(−1)
k−r
C
r
k
S
k
, M
r
=
n

k=r
(−1)
k−r
C
r−1
k−1
S
k
,
với mọi r = 0, 1, . . . , n.

k
với k ≥ r. Vì
vậy trọng số của các vật đó tham gia trong tổng
n

k=r
(−1)
k−r
C
r
k
S
k
với hệ số bằng
n

k=r
(−1)
k−r
C
r
k
C
k
t
=
n

k=r
(−1)

r
t
t−r

j=0
(−1)
j
C
j
t−r
= 0.
Trọng số của các vật có t < r tính chất không tham gia vào việc tính tổng S
r
, ..., S
n
.
Vì vậy trọng số của các vật đó cũng tham gia trong tổng
n

k=r
(−1)
k−r
C
r
k
S
k
với hệ số
bằng 0. Vậy
n

j
k
S
k

=
n

k=r
(−1)
k−r
C
r
k
S
k
+
n

k=r+1
(−1)
k−(r+1)
C
r+1
k
S
k
+ · · · +
n


t=0
(−1)
t
C
k−t
k
=
n

k=r
S
k
k−r

t=0
(−1)
t
C
t
k
=
n

k=r
S
k
k−r

j=0
(−1)

k
x
k

(1 + x + x
2
+ x
3
+ · · · ).
Hệ số của x
k−r
trong chuỗi biểu diễn (1 − x)
k
(1 − x)
−1
ở trên bằng
k−r

j=0
(−1)
j
C
j
k
.
Mặt khác,
(1 − x)
k
(1 − x)
−1

k−r
C
k−r
k−1
. Vì vậy
k−r

j=0
(−1)
j
C
j
k
= (−1)
k−r
C
k−r
k−1
⇒ M
r
=
n

k=r
(−1)
k−r
C
k−r
k−1
S

M(P
i
1
, P
i
2
, . . . , P
i
k
) = |A
i
1
∩ A
i
2
∩ . . . ∩ A
i
k
|,
M
1
= |A
1
∪ A
2
∪ . . . ∪ A
n
|,
S
k

k−1
C
0
k−1
S
k
=
n

k=1
(−1)
k−1
S
k
=
n

k=1
(−1)
k−1

1≤i
1
<i
2
<···<i
k
≤n
|A
i

, . . . , b
i−1
, b
i
, b
i+1
, . . . , b
n
) và (b
1
, . . . , b
i−1
, b

i
, b
i+1
, . . . , b
n
) với b
i
= b

i
sao cho f(b
1
, . . . , b
i−1
, b
i

, x
2
, . . . , x
n
) mà phụ thuộc không thật
sự vào đúng r biến.
Giả sử P
i
là tính chất “phụ thuộc không thật sự vào biến x
i
”. Khi đó với ω(f) = 1
cho mọi hàm f(x
1
, x
2
, ..., x
n
) ta có M(P
i
1
, P
i
2
, ..., P
i
k
) bằng số các hàm Boole n biến
có các tính chất P
i
1

M
n
(r) =
n

k=r
(−1)
k−r
C
r
k
S
k
=
n

k=r
(−1)
k−r
C
r
k
C
k
n
2
2
n−k
=
n