TAILIEUCHUNG - Bài giảng Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 2) - GVC ThS. Võ Minh Đức
Bài giảng "Chương II: Các phương pháp đếm và nguyên lý Dirichlet (Phần 2)" cung cấp cho các bạn những kiến thức về: sinh các hoán vị và tổ hợp, hệ thức truy hồi, nguyên lý Dirichlet. Tài liệu hữu ích với các bạn chuyên ngành Toán họ | 10/3/2014 1 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk CÁC PHƯƠNG PHÁP ĐẾM VÀ NGUYÊN LÝ DIRICHLET Chương II 1 III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP 10/3/2014 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk 2 1. Sinh các hoán vị (Tổ 1) Sinh các tổ hợp (tổ 2) Nhị thức Newton (tổ 3) Đọc sách TL1 (tr ): Chuẩn bị nội dung, tuần sau mỗi tổ trình bày trong 5 phút. 10/3/2014 3 ThS. Võ Minh Đức, CĐSP Đăklăk III. SINH CÁC HOÁN VỊ VÀ TỔ HỢP. 1. Sinh các hoán vị Cho tập gồm n phần tử {1, 2, 3,. . .n} Hóan vị đi trứớc: Hoán vị được gọi là đi trước hoán vị nếu tồn tại k (1 k n), a1 = b1, a2 = b2,., ak-1 = bk-1 và ak aj+2 > . > an để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2, ., an, rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj, aj+1, aj+2, ., an vào các vị trí j+1, ., n. Dễ thấy không có hoán vị nào đi sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra 10/3/2014 5 GVC, ThS. Võ Minh Đức, CĐSP Đắk Lắk IV. NGUYÊN LÝ DIRICHLET nhà toán học người Đức, Peter Gustav Dirichlet (1805-1859) 1. Nguyên lý: Nếu có k+1 đồ vật (hoặc nhiều hơn) được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật. 2. Nguyên lý Dirichlet tổng quát: Nếu có n đồ vật được đặt trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ]n/k[ đồ vật. ] x [: Số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. 5 ] x [: giá trị của hàm trần tại số thực x, đó là số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. (đối ngẫu với khái niệm [x]: hàm sàn, đó là số nguyên lớn nhất có giá trị lớn hơn hoặc bằng x) 10/3/2014 6 GVC, ThS. Võ Minh Đức, CĐSP Đăklăk IV. NGUYÊN LÝ DIRICHLET 3. Ví dụ: Chứng minh rằng trong 100 người có ít
đang nạp các trang xem trước
