Chương 2 - các phương pháp đếm và nguyên lý Dirichlet

CHƯƠNG 2

CÁC PHƯƠNG PHÁP ĐẾM

VÀ NGUYÊN LÝ DIRICHLET

Các phần học trong chương 2

 Các nguyên lý đếm cơ bản.

 Khái niệm về hoán vị, chỉnh hợp, tổ

hợp.

 Nhị thức Newton.

 Nguyên lý Dirichlet.

 Hệ thức truy hồi.

 Quan hệ chia để trị

 Nguyên lý bù trừ.

1.Các nguyên lý đếm cơ bản

1.1 Nguyên lý cộng

 Cho A là một tập hữu hạn các phần tử, ta

ký hiệu N(A) là số lượng các phần tử của

A.

 Nguyên lý cộng: Cho A1

, A2

, ..., An

là các

tập hữu hạn, không giao nhau từng đôi

một. Khi đó:

∑ ( )

= =

=















n

i

i

n

i

N Ai N A

1 1

