ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC KHOA HOC TỰ NHIÊN
——————–
NGUYỄN THỊ HỒNG
PHƯƠNG PHÁP XÁC SUẤT TRONG TOÁN
TRUNG HỌC PHỔ THÔNG
LUẬN VĂN THẠC SĨ KHOA HỌC
HÀ NỘI - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
ĐẠI HỌC KHOA HOC TỰ NHIÊN
——————–
NGUYỄN THỊ HỒNG
PHƯƠNG PHÁP XÁC SUẤT TRONG TOÁN
TRUNG HỌC PHỔ THÔNG
Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 60 46 01 13
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS. TS. LÊ ANH VINH
HÀ NỘI - 2014
Mục lục
Danh mục ký hiệu 1
Lời nói đầu 2
1 Phương pháp đếm 4
1.1 Hoán vị, chỉnh hợp, tổ hợp . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.3 Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Sự phân hoạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Sự phân hoạch một số nguyên dương thành tổng các số
nguyên không âm . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Phân hoạch tập hợp . . . . . . . . . . . . . . . . . . . . . . 12
1.2.3 Phân hoạch số nguyên . . . . . . . . . . . . . . . . . . . . . 14
1.3 Công thức Sieve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Lý thuyết đồ thị cơ bản 26
2.1 Khái niệm cơ bản về đồ thị . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Định nghĩa đồ thị và phân loại đồ thị . . . . . . . . . . . . 26
2.1.2 Đồ thị đẳng cấu . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.3 Biểu diễn đồ thị bằng ma trận . . . . . . . . . . . . . . . . 28
2.1.4 Đồ thị con, đồ thị thành phần và đồ thị sinh . . . . . . . . 29
2.2 Các yếu tố trong đồ thị vô hướng . . . . . . . . . . . . . . . . . . . 30
2.2.1 Bậc của đỉnh trong đồ thị . . . . . . . . . . . . . . . . . . . 30
2.2.2 Đường đi và chu trình . . . . . . . . . . . . . . . . . . . . . 30
2.2.3 Tính liên thông . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.4 Một số loại đơn đồ thị vô hướng . . . . . . . . . . . . . . . 31
2.3 Bài toán tô màu và các số Ramsey . . . . . . . . . . . . . . . . . . 39
i
MỤC LỤC
2.3.1 Lý thuyết Ramsey cho đồ thị hữu hạn . . . . . . . . . . . . 39
2.3.2 Lý thuyết Ramsey trong trường hợp tổng quát . . . . . . . 42
3 Xác suất và một số ứng dụng 44
3.1 Phép thử và biến cố . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Xác suất của biến cố . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 Định nghĩa cổ điển của xác suất . . . . . . . . . . . . . . . 45
3.2.2 Định nghĩa thống kê về xác suất . . . . . . . . . . . . . . . 48
3.2.3 Định nghĩa hình học về xác suất . . . . . . . . . . . . . . . 48
3.3 Định lý cộng xác suất . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Định lý nhân xác suất . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5 Một số mở rộng của định lý cộng và định lý nhân xác suất . . . . 57
3.6 Biến ngẫu nhiên và kì vọng . . . . . . . . . . . . . . . . . . . . . . 64
3.6.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.6.2 Tính tuyến tính của kì vọng . . . . . . . . . . . . . . . . . . 66
3.7 Sử dụng xác suất chứng minh một số tính chất của các số Ramsey 68
3.8 Áp dụng xác suất và kì vọng vào một số bài toán thi học sinh giỏi 70
Kết luận 78
Tài liệu tham khảo 79
ii
Danh mục ký hiệu
|A|Số phần tử của A
p(n)Số hoán vị của nphần tử phân biệt
Ck
nSố tổ hợp chập kcủa nphần tử
Ak
nSố chỉnh hợp chập kcủa nphần tử
S(n, k)Số cách phân hoạch tập nphần tử thành kphần
B(n)Số cách phân hoạch tập nphần tử thành một số phần
P(n)Số cách phân hoạch số nthành kphần
D(n)Số xáo trộn của tập nphần tử
P(A)Xác suất của biến cố A
E(X)Kì vọng của biến ngẫu nhiên X
1