Tài liệu B1606839_nguyenphattai

BÁO CÁO TOÁN RỜI RẠC CHƯƠNG 3 I. II. Các nguyên lý đếm a) Nguyên lý cộng: Giả sử để làm 1 công việc có 2 phương pháp: + Phương pháp 1 có n cách làm + Phương pháp 2 có m cách làm Thì số cách làm công việc đó là tổng số cách làm của các phương pháp, tức là n+m cách làm. b) Nguyên lý nhân: Giả sử để làm 1 công việc cần thực hiện 2 bước: + Bước 1 có n cách làm + Bước 2 có m cách làm Thì số cách làm công việc đó là tích các cách làm của các bước, tức là n.m cách làm. c) Nguyên lý bù trừ: Cho A và B là hai tập hữu hạn. Khi đó |A U B|= |A|+|B| - |A ∩ B| d) Nguyên lí chim bồ câu: Nguyên lý Dirichlet: Nếu có N vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất [N/k] vật. Đại số tổ hợp a) Hoán vị: Cho n phần tử phân biệt. Mỗi cách sắp xếp vị trí của n phần tử gọi là một hoán vị của n phần tử đó. + Kí hiệu: Pn=n!=n(n-1)(n-2)…1 + Quy ước: 0!=1 b) Chỉnh hợp Cho n phần tử phân biệt. Mỗi cách sắp xếp có thứ tự vị trí của k phần tử trong n phần tử là một hoán vị chập k của n phần tử Công thức: Akn= 𝒏! (𝒏−𝒌)! (k≤n) c) Tổ hợp Cho n phần tử phân biệt. Mỗi cách lấy ra k phần tử từ n phần tử gọi là một tổ hợp chập k của n phần tử. Công thức: Ckn= Tính chất: C0n = Cnn=1 d) Hoán vị lặp 𝒏! 𝒌!(𝒏−𝒌)! (k≤n) Cn-kn= Ckn Ckn+ Ck-1n= Ckn+1 Cho n phần tử trong đó có ni phần tử loại i giống hệt nhau (i =1, 2, …, k ; n1+ n2+…+ nk= n). Mỗi cách sắp xếp có thứ tự n phần tử là một hoán vị lặp của n. Công thức: Pn(n1,n2,…,nk)= e) Chỉnh hợp lặp 𝒏! 𝒏𝟏!𝒏𝟐!𝒏𝒌! BÁO CÁO TOÁN RỜI RẠC CHƯƠNG 3 Cho n phần tử phân biệt, mỗi cách lấy ra k phần tử từ n phần tử có lặp, có theo thứ tự gọi là một chỉnh hợp lặp chập k của n phần tử Công thức: Bkn=nk f) Tổ hợp lặp Mỗi cách chọn ra k vật từ n loại vật khác nhau (trong đó mỗi loại vật có thể được chọn lại nhiều lần) được gọi là tổ hợp lặp chập k của n Công thức: Ckn+k-1= III. (𝒏+𝒌−𝟏)! 𝒌!(𝒏−𝟏)! Hệ thức truy hồi a) Định nghĩa: Hệ thức truy hồi đối với dãy {an} là công thức biểu diễn an theo một hay nhiều số hạng đứng trước nó, cụ thể a0 ,a1,…, an-1 với mọi số nguyên n ≥ n0 , n0 ≥ 0. Dãy số được gọi là lời giải hay là nghiệm của hệ thức truy hồi nếu các số hạng của nó thỏa mãn hệ thức truy hồi này. b) Giải hệ thức truy hồi tuyến tính thuần nhất + Định lý 1: Cho c1, c2 là hai số thực. Giả sử r2- c1r-c2=0 có hai nghiệm phân biệt là r1, r2. Khi đó dãy {an} là nghiệm của hệ thức truy hồi an=c1an-1+c2an-2 nếu và chỉ nếu an=t1r1n+t2r2n, với n=0;1;2…trong đó t1, t2 là các hằng số + Định lý 2: Cho c1, c2 là 2 số thực (c2#0). Giả sử r2- c1r-c2=0 chỉ có một nghiệm duy nhất là r0. Khi đó dãy {an} là nghiệm hệ thức truy hồi an=c1an-1+c2an-2 nếu và chỉ nếu an= t1r0n+t2r0n với n=0;1;2…trong đó t1, t2 là các hằng số + Định lý 3: Cho c1, c2,…ck là các số thực. Giả sử rk- c1rk-1-…-ck=0 có k nghiệm phân biệt là r1, r2,..,rk. Khi đó dãy {an} là nghiệm của hệ thức truy hồi an=c1an-1+c2an-2+..+ckan-k nếu và chỉ nếu an=t1r1n+t2r2n+…+tkrkn, với n=0;1;2…trong đó t1, t2,…,tk là các hằng số