Tiêu đề Tài liệu bồi dưỡng học sinh giỏi - Chuyên đề 20 - TỔ HỢP VÀ RỜI RẠC.doc ✅

Trang 1 Chuyên đề 20: TỔ HỢP VÀ RỜI RẠC 1. KIẾN THỨC TRỌNG TÂM Tổ hợp và xác suất CX  Số hoán vị của tập A có n phần tử: !nPn  Số chỉnh hợp n chập k:  ! ! k n n A nk   Số tổ hợp n chập k:  ! !! k n n C knk   Xác suất: A B PA   Xác suất có điều kiện:  |PA PAB PAB  Nhị thức Newton:  - 0 .. n n knkk n k abCab     Cho n tập 1,...,nAA là n tập hợp hữu hạn 2n thì số phần tử: 1 111 ... nnn niikikj iiknikn AAAAAAAA    -11...1...nnAA  Cho ánh xạ f từ tập hữu hạn X có n phần tử vào tập hữu hạn Y có m phần tử. Số ánh xạ f từ X và Y là nm . Số đơn ánh f từ X vào Y là (1)(2)...(1)nnnnm với nm Số toàn ánh f từ X vào Y là  0 1. m kn k m k Cmk    khi nm Số song ánh f từ X và Y là .( 1)(2)...2.1! nnnn khi nm Nguyên tắc Dirichlê  Nếu nhốt 1k con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 2 con. Nếu nhốt 2 1k con thỏ vào k chuồng (k nguyên dương) thì tồn tại một chuồng chứa ít nhất 3 con.  Nếu nhốt   1nk con thỏ vào k chuồng (k, n nguyên dương) thì tồn tại một chuồng chứa ít nhất 1n con. Nguyên tắc cực hạn
Trang 2 Tồn tại độ đo lớn nhất và độ đo nhỏ nhất hay đại lượng lớn nhất và đại lượng nhỏ nhất của tập hữu hạn khác rỗng các độ đo hay các đại lượng. Bất biến và đơn biến Đại lượng bất biến, tính chất bất biến là những đại lượng hay tính chất không thay đổi trong quá trình thực hiện các phép biến đổi nào đó. Đại lượng đơn biến, tính chất đơn biến là những đại lượng hay tính chất thay đổi một chiều, hoặc tăng thêm hoặc giảm đi trong quá trình thực hiện các phép biến đổi nào đó. Đồ thị  Bổ đề bắt tay: Cho đồ thị  , GVE thì tổng bậc các đỉnh củạ đồ thị là số chẵn và 2 vV dVcardE     Định lý Tocran: Nếu đồ thị G có n đỉnh và số tam giác của G là  0tG thì số cạnh: 2 4 n c    2. CÁC BÀI TOÁN Bài toán 20 .1 : Tính: 123(cossin)03sincos(sincos) ... nnnACxxCCxxxx -2-2 .sincos(sincos )nnn nCnxxxx Hướng dẫn giải Xét hàm số (1 cos) (1 sin) nnyxx thì: 012201 (cos cos ...cos )sin ...sin nnnnnnnnnnnyCCxCxCxCCxCx 012222sin cos sin cos ...sin cos nnnnnnnCCxxCxxCxx 123 ' (cos sin ) 0. 3sin cos (sin cos ) nnnyCxxCCxxxx -2-2            ... sin cos sincosnnnnCnxxxx Do đó: -1-1 '[(1cos)(1sin)] (1cos).(sin)(1sin)cosnnnnAyxxnxxnxx -1-1 [cos(1 sin) sin(1 cos)]nnnxxxx Bài toán 20. 2: Tìm tất cả các cặp số tự nhiên dương n và k thoả: 3 (3)nk nCn Hướng dẫn giải