ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP LUẬN VĂN THẠC SỸ TOÁN HỌC HÀ NỘI- 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN NGỌC MAI MỘT VÀI NGUYÊN LÝ VÀ BÀI TOÁN TỔ HỢP Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số: 60460113 LUẬN VĂN THẠC SỸ TOÁN HỌC Người hướng dẫn khoa học PGS TS ĐÀM VĂN NHỈ HÀ NỘI- 2014 Mục lục Mở đầu Kiến thức chuẩn bị 1.1 Nguyên lý quy nạp 1.2 Hai quy tắc đếm 1.3 Hoán vị 1.4 Chỉnh hợp 1.5 Tổ hợp 1.5.1 Tổ hợp 1.5.2 Ứng dụng số 1.6 Nhị thức Newton 1.7 Đồ thị học Một vài nguyên lý tổ hợp 2.1 Nguyên lý Dirichlet 2.1.1 Nguyên lý Dirichlet 2.1.2 Nguyên lý Dirichlet áp dụng hình học 2.2 Nguyên lý bù trừ 2.3 Nguyên lý cực hạn 2.4 Nguyên lý bất biến Một vài đồng thức tổ hợp 3.1 Xây dựng đồng thức qua hệ phương trình 3.2 Xây dựng đồng thức qua số phức 3.3 Xây dựng đồng thức qua hàm sinh 3.3.1 Khái niệm hàm sinh 3.3.2 Một số đồng thức liên quan đến hàm 3.3.3 Ứng dụng hàm sinh Kết luận Tài liệu tham khảo 5 11 14 14 16 18 20 26 26 26 tổ hợp 31 34 42 51 sinh 60 60 66 69 70 70 71 77 78 Lời cảm ơn Tơi xin bày tỏ lòng kính trọng biết ơn sâu sắc đến PGS.TS Đàm Văn Nhỉ Thầy dành nhiều thời gian hướng dẫn giải đáp thắc mắc suốt q trình tơi thực đề tài Tơi xin gửi lời cảm ơn chân thành tới thầy cô Khoa Tốn - Cơ - Tin học, Phòng Sau đại học - Trường Đại học Khoa học Tự nhiên- Đại học Quốc gia Hà Nội; thầy cô tham gia giảng dạy khóa cao học 2011-2013 Cuối cùng, tơi xin chân thành cảm ơn gia đình bạn bè ln động viên tơi suốt q trình học tập thực luận văn Mở đầu Tư tổ hợp xuất từ sớm lịch sử phát triển nhân loại Tuy nhiên, lý thuyết tổ hợp xem hình thành ngành toán học vào khoảng kỷ 17 loạt cơng trình tiếng nhà tốn học Passcal, Fermat, Leibniz, Euler, Kể từ sau tin học đời, lý thuyết tổ hợp phát triển ngày mạnh mẽ Các vấn đề liên quan đến lý thuyết tổ hợp phận quan trọng, hấp dẫn lí thú tốn học nói chung tốn rời rạc nói riêng Nó khơng có nội dung phong phú, đa dạng, mà có nhiều ứng dụng thực tế đời sống Trong toán sơ cấp, tổ hợp xuất với nhiều tốn hay với độ khó cao Khi giải toán tổ hợp, ta phải liệt kê, đếm đối tượng theo tính chất Để làm việc này, việc sử dụng hai quy tắc đếm bản, kiến thức hoán vị, chỉnh hợp, tổ hợp, nhiều toán ta phải sử dụng số nguyên lý khác tổ hợp Vì vậy, để hiểu rõ nắm bắt sâu vể vấn đề này, chọn đề tài Một vài nguyên lý toán tổ hợp Luận văn trình bày số nguyên lý tổ hợp xây dựng số toán áp dụng Luận văn gồm phần mở đầu, ba chương, kết luận danh mục tài liệu tham khảo Chương : Kiến thức chuẩn bị Trong chương này, tác giả trình bày số lý thuyết nguyên lý quy nạp, hai quy tắc đếm bản, hoán vị, chỉnh hợp, tổ hợp, nhị thức Newton đồ thị Chương : Một vài nguyên lý tổ hợp Chương gồm nội dung chính, trình bày bốn nguyên lý tổ hợp ví dụ áp dụng ngun lý Cụ thể là: Mục 2.1 trình bày nguyên lý thứ nhất: Nguyên lý Dirichlet Nguyên lý gọi nguyên lý lồng chim bồ câu Giả sử có đàn chim bồ câu bay vào chuồng Nếu số chim nhiều số ngăn chuồng có ngăn có nhiều chim Phát triển dạng toán này, Piter Gustave Dirichlet đưa nguyên lý chứng minh toán học đơn giản, phát biểu sau: "Nếu có N đồ vật đặt vào k hộp tồn hộp chứa N + đồ vật." k Mục 2.2 trình bày Ngun lý bù trừ Khi hai cơng việc làm đồng thời, dùng quy tắc cộng để tính số cách thực nhiệm vụ gồm hai việc Cộng số cách thực việc dẫn đến trùng lặp, cách làm hai cơng việc tính hai lần Để tính số cách thực nhiệm vụ ta cộng số cách làm hai việc trừ số cách làm đồng thời hai công việc Nguyên lý mở rộng cho trường hợp đếm số phần tử hợp tập hợp Đó Ngun lý bù trừ Ngun lý thứ Nguyên lý cực hạn, trình bày mục Nguyên lý tồn phần tử lớn phần tử nhỏ tập hợp hữu hạn Nguyên lý có nhiều ứng dụng việc giải toán tổ hợp, giải số phương trình nghiệm nguyên, chứng minh bất đẳng thức, Cuối cùng, mục trình bày nguyên lý thứ Nguyên lý bất biến Trong mục này, tác giả trình bày hai mẫu tốn tổng qt thường giải nguyên lý bất biến đưa ví dụ sử dụng nguyên lý bất biến Chương Một vài đồng thức tổ hợp Chương trình bày số ví dụ xây dựng đồng thức tổ hợp qua hệ phương trình, số phức hàm sinh, Chương Kiến thức chuẩn bị 1.1 Nguyên lý quy nạp Mệnh đề 1.1 [Nguyên lý thứ nhất] Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) với α ∈ N (ii) P (n + 1) P (n) đúng, n ≥ α, n ∈ N P (n) với số tự nhiên n ≥ α Mệnh đề 1.2 [Nguyên lý thứ hai] Nếu mệnh đề P (n), phụ thuộc vào số tự nhiên n thỏa mãn: (i) P (α) với α ∈ N (ii) P (n + 1) P (α), P (α + 1), , P (n) đúng, n ≥ α, n ∈ N, P (n) với số tự nhiên n ≥ α Cách chứng minh định lý hay tốn có sử dụng nguyên lý quy nạp gọi phép quy nạp hay phương pháp quy nạp toán học Sau đây, ta xét số ví dụ áp dụng hai nguyên lý Ví dụ 1.1 Chứng minh rằng, với số nguyên n ≥ số thực a > ta ln có đồng thức n k=1 (−1)k Cnk = ak + n!an n k=1 (1 + ka) Lời giải Trước tiên, ta chứng minh quy nạp theo n (1 − xa )n dx = n!an n k=1 (1 + ka) Thật Với n = ta có (1 − xa )dx = x − Suy khẳng định với n = Đặt xa+1 a+1 = a 1!a1 = a+1 + 1.a (1 − xa )n dx In = Giả sử n!an n k=1 (1 + ka) In = Ta phải chứng minh In+1 = (n + 1)!an+1 n+1 k=1 (1 + ka) Ta có 1 (1 − xa )n+1 dx = (n + 1)a In+1 = xa (1 − xa )n dx = (n + 1)a(In − In+! ) Hay In+1 = (n + 1)a In + (n + 1)a Theo giả thiết quy nạp ta có In+1 = (n + 1)!an+1 n+1 k=1 (1 + ka) Suy khẳng định với n + Vậy khẳng đinh với n ≥ Từ suy n k=0 (−1)k Cnk = ak + n (−1) k=0 k Cnk ak (1 − xa )n dx = x dx = 0 n!an n k=1 (1 + ka) Ví dụ 1.2 Chứng minh với số nguyên n > ta có đồng thức 1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + Lời giải Ta chứng minh quy nạp theo n + Với n = ta có 1.2 = = (1 − 1)21+1 + Chứng tỏ kết luận với n = + Giả sử kết luận với n ≥ Khi 1.2 + 2.22 + · · · + n.2n = (n − 1)2n+1 + + Ta phải chứng minh kết luận với n + Tức 1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = n2n+2 + Thật vậy, ta có 1.2 + 2.22 + · · · + n.2n + (n + 1)2(n+1) = (n − 1)2n+1 + + (n + 1)2n+1 = n2n+2 + Chứng tỏ kết luận với n + Vậy khẳng định với số nguyên n > Ví dụ 1.3 Dãy (an ) cho sau: a0 = 1, a1 = 3, a2 = 6, a3 = 10, a4 = 15, a5 = 21, Xác định (an ) theo n chứng minh bất đẳng thức T = 1− 1− 1− 1 1 − < + 10 an n Lời giải Ta có a0 = 1, a1 = = a0 + + 1, a2 = = a1 + + 1, a3 = 10 = a2 + + 1, a4 = 15 = a3 + + 1, a5 = 21 = a4 + + 1, Suy an = an−1 + n + Điều dễ dàng có chứng minh quy nạp (n + 1)(n + 2) ak − (k + 1)(k + 2) − k(k + 3) Suy − = = = ak ak (k + 1)(k + 2) (k + 1)(k + 2) Vậy an = + + + + + n + n + = Như 1− 1 = 1− ak k+1 1+ k+2 Suy 1 − 1+ n+1 n+2 1 1 1 = − − − − 1+ 2 (n + 1) (n + 2) 2 2 (n + 1) − 1 −1 −1 −1 + = 32 42 52 (n + 1)2 (n + 2) 2 2 2.3.4 (n − 1) n (n + 1)(n + 2)(n + 3) = 2.32 42 52 (n − 1)2 n2 (n + 1)2 (n + 2) n+3 n+3 1 = < = + 3(n + 1) 3n n T = 1− Vậy an = 1.2 1+ 1− 1+ 1 (n + 1)(n + 2) T < + n Hai quy tắc đếm Chương trình tốn phổ thông lớp 11 trang bị cho học sinh hai quy tắc đếm bản, quy tắc cộng quy tắc nhân Đây hai công cụ quan trọng giúp học sinh giải số toán tổ hợp đơn giản Quy tắc cộng phát biểu sau: Giả sử, cơng việc thực theo k phương án A1 , A2 , , Ak Có n1 cách thực phương án A1 , n2 cách thực phương án A2 , , nk cách thực phương án Ak Khi cơng việc thực n1 + n2 + · · · + nk cách Bản chất quy tắc cộng cơng thức tính số phần tử hợp n tập hợp hữu hạn đôi không giao Cụ thể ta có: Cho A1 , A2 , , Ak tập rời Khi A1 ∪ A2 ∪ · · · ∪ Ak = A1 + A2 + · · · + Ak Khi công việc thực nhiều cơng đoạn liên tiếp, ta phải sử dụng quy tắc nhân Quy tắc nhân cho nhiều công đoạn phát biểu sau: Giả sử công việc bao gồm k cơng đoạn A1 , A2 , , Ak Công đoạn A1 thực theo n1 cách, cơng đoạn A2 thực theo n2 cách, , cơng đoạn Ak thực theo nk cách Khi cơng việc thực theo n1 n2 nk cách xk x + y k a(x2 − 12 )(x2 − 22 ) (x2 − n2 ) = ta suy hệ thức n 2 k=1 x + k 2 x (x + k ) n x Từ − + k=1 − (x2 + 12 ) (x2 + n2 ) + x(x1 x + y1 )(x2 + 22 )(x2 + 32 ) (x2 + n2 ) + x(x2 x + y2 )(x2 + 12 )(x2 + 32 ) (x2 + n2 ) + · · · + x(xn x + yn )(x2 + 12 )(x2 + 22 ) (x2 + (n − 1)2 ) = a(x2 − 12 )(x2 − 22 ) (x2 − n2 )  n   a = −(−1) với x =   n  n   a(−1) (12 + k )    k=1  −x1 + iy1 = với x = i  n    (k − 1)    k=2   n   n  (22 + k ) a(−1)   k=1 với x = 2i Ta nhận nghiệm −22 x2 + 2iy2 = n  2  (k − )    k=1,k=2         n   n  a(−1) (n2 + k )    k=1   −n2 xn + niyn = với x = ni  n−1    (k − n2 )  k=1 n (r2 + k ) k=1 n Như hệ giải xong với y1 = · · · = yn = xr = r2 với (k − r2 ) k=1,k=r r = 1, , n n xk x a(x2 − 12 )(x2 − 22 ) (x2 − n2 ) Vì − + = nên n x k=1 x2 + k 2 x (x + k ) n n k=1 xk = hay k=1 + k k=1 (s2 + k2) s=1 = với x = n k2 n (s2 − k )(1 + k ) s=k n Hệ 3.1 Ta ln có n (−1)n−k n−k (s2 + k )C2n s=1 + k2 k=1 64 = (2n)! n n (s2 + k ) s=1 Chứng minh Từ k=1 = 1, theo chứng minh trên, n k2 (s2 − k )(1 + k ) s=k n (s2 − k ) = s=k n n (s + k) = (−1)k−1 (s − k) s=k s=k n n k=1 (n − k)!(n + k)! suy 2k (s2 + k ) s=1 k−1 (−1) (n − k)!(n + k)!(1 + k ) n (−1)k−1 n (s2 + k )Cn−k 2n s=1 Nhân hai vế với (2n)! có + k2 k=1 = = (2n)! n Ví dụ 3.6 Giả sử ϕ(x) = (x + αi ) Khi ta có đồng thức: i=1 (i) (−1)i Cni ϕ(i) 4n! = + (−1)n ϕ(0) 2i − c i=1 (ii) (−1)i−1 i n 2n (n!)2 Cn i = (2n)! i=1 2i − n n Lời giải Xuất phát từ phương trình x1 x2 xn c(x − α1 )(x − α2 ) (x − αn ) + + ··· + − = 1+x 2+x n + x 2x + (2x + 1)(x + 1)(x + 2) (x + n) ta suy (i) thay x1 , , xn x = 0; (ii) suy từ (i) Ví dụ 3.7 Với số tự nhiên dương n ln có đồng thức (−1)k Cn+k 2n = 2+1 k k=−n n (i) (2n)! n (k + 1) k=1 n+k (−1)k kC2n = k2 + k=−n n (ii) n+k (−1)k C2n = 2 k=−n k + n n (iii) (2n)! n n2 (k + n2 ) k=1 n+k (−1)k kC2n = (iv) k + n2 k=−n n 65 n ak = 2 2 x(x − 1)(x − ) (x − n ) k=−n x − k (−1)n−k với k = −n, −n + 1, , n − 1, n ta có biểu Khi có ak = (n − k)!(n + k)! Lời giải Giả sử diễn n k=−n (−1)n−k Cn+k (2n)! 2n = x−k x(x2 − 1)(x2 − 22 ) (x2 − n2 ) (i) (ii) Với x = i có n (2n)! = n (k + 1) k=−n n+k (−1)k C2n i= i−k n k=−n n+k (−1)k C2n (1 − ki) k2 + k=1 n+k (−1)k C2n Do = k2 + k=−n n (2n)! n (k + 1) n+k (−1)k kC2n = k2 + k=−n n k=1 (iii) (iv) Với x = ni ta nhận đồng thức đây: (2n)! n (k n = + n2 ) k=−n n+k (−1)k C2n ni = ni − k n k=−n n+k (−1)k C2n (n2 − nki) k + n2 k=1 n+k (−1)k C2n Vậy = 2 k=−n k + n n (2n)! n n2 (k + n2 ) n+k (−1)k kC2n = k + n2 k=−n n k=1 3.2 Xây dựng đồng thức qua số phức Sử dụng công thức Moivre số phức để xây dựng đồng thức tính số tổng có liên quan tổ hợp Ví dụ 3.8 Tính tổng sau đây: (i) Tổng T1 = + Cn4 + Cn8 + (ii) Tổng T2 = Cn1 + Cn5 + Cn9 + (iii) Tổng T3 = Cn2 + Cn6 + Cn10 + (iv) Tổng T4 = Cn3 + Cn7 + Cn11 + (v) Tổng S = (T1 − T3 )2 + (T2 − T4 )2 (v) Tổng P = T12 + T22 + T32 + T42 66 Lời giải Từ (1 + i)n = + iCn1 − Cn2 − iCn3 + Cn4 + iCn5 − Cn6 − (1 + i)n = nπ nπ n 2 cos + i sin suy 4 nπ n nπ T2 − T4 = 2 sin n T1 − T3 = 2 cos Vì 2n = (1 + 1)n = T1 + T2 + T3 + T4 = (1 − 1)n = T1 − T2 + T3 − T4 ta suy hệ phương trình:  nπ n  cos T − T =      nπ n  T2 − T4 = 2 sin   T1 + T2 + T3 + T4 = 2n      T − T + T − T = Giải hệ phương trình ta T1 = n n−1 nπ + 2 cos n n−1 nπ + 2 sin n nπ n−1 T3 = − 2 cos n nπ T4 = 2n−1 − 2 sin T2 = Từ suy S = 2n P = 22n−2 + 2n−1 Ví dụ 3.9 Giả sử hai dãy số nguyên (an ) (bn ) xác định sau:    a0 = 3, a1 = 8, a2 = 58      an+2 = 8an+1 − 3an + 3an−1 , n ≥ 2;   b0 = 3, b1 = 5, b2 = 45      bn+2 = 5bn+1 + 10bn + 7bn−1 , n ≥ 2013 b + b = C Chứng minh: C2014 b2013 + · · · + C2014 2014 a2013 − C2014 a2012 + · · · + 2013 a − a C2014 Lời giải Đây toán dãy số nguyên lại xét tốn C Xét phương trình f (x) = x3 − 8x2 + 3x − = Gọi nghiệm phương trình 67 C x1 , x2 , x3 Dễ dàng kiểm tra x01 + x02 + x03 = a0 , x1 + x2 + x3 = a1 , x21 + x22 + x23 = a2 Tổng quát xn1 + xn2 + xn3 = an , n ≥ Tương tự y1n + y2n + y3n = bn , n ≥ 0, y1 , y2 , y3 ba nghiệm phương trình g(y) = y − 5y − 10y − = Kiểm tra trực tiếp: f (y + 1) = g(y) g(x − 1) = f (x) Vậy ta nhận hệ thức sau: an = xn1 + xn2 + xn3 = (y1 + 1)n + (y2 + 1)n + (y3 + 1)n bn = y1n + y2n + y3n = (x1 − 1)n + (x2 − 1)n + (x3 − 1)n , n ≥ Do   an = C bn + C bn−1 + · · · + C n−1 b1 + C n b0 n n n n  bn = C an − C an−1 + · · · + (−1)n−1 C n−1 a1 + (−1)n C n a0 n n n n Suy 2013 2013 C2014 b2013 + · · · + C2014 b1 + b0 = C2014 a2013 − C2014 a2012 + · · · + C2014 a1 − a0 Ví dụ 3.10 Giả sử hai dãy số nguyên (an ) (bn ) xác định sau:    a0 = 3, a1 = 2, a2 = −6      an+2 = 2an+1 − 5an + an−1 , n ≥ 2;   b0 = 3, b1 = −4, b2 = −2      bn+2 = −4bn+1 − 9bn − 9n−1 , n ≥ Khi ta có kết sau đây: (i) an = Cn0 bn + 2Cn1 bn−1 + · · · + 2n−1 Cnn−1 b1 + 2n Cnn b0 ; (ii) bn = Cn0 an − 2Cn1 an−1 + · · · + (−1)n−1 2n−1 Cnn−1 a1 + (−1)n 2n Cnn a0 Lời giải Đây toán dãy số nguyên lại xét tốn C Xét phương trình f (x) = x3 − 2x2 + 5x − = Gọi nghiệm phương trình C x1 , x2 , x3 Dễ dàng kiểm tra x01 + x02 + x03 = a0 , x1 + x2 + x3 = a1 , x21 + x22 + x23 = a2 Tổng quát xn1 + xn2 + xn3 = an , n ≥ 68 Tương tự y1n + y2n + y3n = bn , n ≥ 0, y1 , y2 , y3 ba nghiệm phương trình g(y) = y + 4y + 9y + = Kiểm tra trực tiếp: f (y + 2) = g(y) g(x − 2) = f (x) Vậy ta nhận hệ thức sau: an = xn1 + xn2 + xn3 = (y1 + 2)n + (y2 + 2)n + (y3 + 2)n bn = y1n + y2n + y3n = (x1 − 2)n + (x2 − 2)n + (x3 − 2)n , n ≥ Do   an = C bn + 2C bn−1 + · · · + 2n−1 C n−1 b1 + 2n C n b0 ; n n n n  bn = C an − 2C an−1 + · · · + (−1)n−1 2n−1 C n−1 a1 + (−1)n 2n C n a0 n n n n Ta kết (i) (ii) Ví dụ 3.11 Với số nguyên dương n ta có 3n−1 2k+1 k (−1)k C6n = 0; k=0 3n 2k k (−1)k C6n = 26n k=0 Lời giải Xét toán C Ta có đồng thức sau √ π π (1 + i 3)6n = 26n (cos + i sin )6n = 26n (cos n2π + i sin n2π) = 26n 3 √ 3n−1 k 2k k k 2k+1 k Suy 26n = (1 + i 3)6n = 3n k=0 (−1) C6n + i k=0 (−1) C6n Do ta có điều phải chứng minh 3.3 Xây dựng đồng thức qua hàm sinh Một nguồn gốc dẫn đến khái niệm hàm sinh Định lý khai triển Nhị thức Newton (1 + x)n = nk=0 Cnk xk khai triển chuỗi lũy thừa phân thức = + x + x2 + x3 + Đây kỹ thuật giải tích với 1−x nhiều ứng dụng tổ hợp nghiên cứu dãy số Trong mục này, tác giả sử dụng hàm sinh để xây dựng đồng thức tổ hợp Trước tiên, ta bắt đầu với khái niệm hàm sinh 69 3.3.1 Khái niệm hàm sinh Định nghĩa 3.1 Cho dãy số thực (an ) Ta lập chuỗi lũy thừa ∞ an x n S(x) = n=0 Khi chuỗi lũy thừa S(x) hội tụ đến hàm f (x) ta gọi hàm f (x) hàm sinh dãy (an ) cho Nhận xét 3.1 Trong nhiều trường hợp ta chưa biết dãy số lập luận ta lại tìm hàm sinh f (x) Và từ hàm sinh ta tìm dãy số, cơng thức khai triển Maclaurine hàm f (x): dn an = f (x)|x=0 , n = 0, 1, 2, 3, n! dxn Khi giải toán tổ hợp, việc tìm nghiệm tốn thường cơng việc phải làm Với nhiều tốn phần việc tương đối khó khăn Kỹ thuật hàm sinh giúp ta giải nhiều tốn hóc búa thực tế 3.3.2 Một số đồng thức liên quan đến hàm sinh = + x + x2 + x3 + 1−x = + 2x + 3x2 + 4x3 + (1 − x) n(n + 1) n(n + 1)(n + 2) = + nx + x + x + n (1 − x) 2! 3! ∞ i Ci+n−1 xi = i=0 = − x + x2 − x3 + 1+x = + xr + x2r + x3r + − xr Mệnh đề 3.1 Cho hàm sinh G(x) = (1 + x + x2 + )n r i) Đặt ar hệ số xr khai triển G(x) ar = Cn+r−1 m n m 2m n mn ii) (1 − x ) = − Cn x + Cn x − · · · + (−1) x iii) (1 + x + x2 + · · · + xm−1 )n = (1 − xm )n (1 + x + x2 + )n 70 Mệnh đề 3.2 [Cơng thức xác định hệ số tích hai hàm sinh] Cho hai hàm sinh hai dãy (an ); (bn ) là: A(x) = a0 + a1 x + a2 x2 + B(x) = b0 + b1 x + b2 x2 + Đặt G(x) = A(x)B(x) = (a0 + a1 x + a2 x2 + )(b0 + b1 x + b2 x2 + ) = a0 b0 + (a0 b1 + a1 b0 )x + (a0 b2 + a1 b1 + a2 b0 )x2 + Khi hệ số xr khai triển G(x) a0 br + a1 br−1 + a2 br−2 + · · · + ar−2 b2 + ar−1 b1 + ar b0 Chú ý 3.1 Gọi A(x) hàm sinh cho dãy cách chọn phần tử từ tập A, B(x) hàm sinh cho dãy cách chọn phần tử từ tập B Nếu A B rời hàm sinh cho số cách chọn phần tử từ tập A ∪ B A(x)B(x) 3.3.3 Ứng dụng hàm sinh Trong số tốn đếm, thay tính trực tiếp số cách chọn, ta đưa việc tính hệ số hàm sinh sinh dãy cách chọn Ví dụ 3.12 Giả sử có loại kẹo: Chanh, dâu, sơcơla, sữa Tìm hàm sinh cho số cách chọn n kẹo thỏa mãn điều kiện sau đây: a Mỗi loại kẹo xuất lẻ lần b Số kẹo loại chia hết cho c Khơng có kẹo socola nhiều kẹo chanh Lời giải a Vì loại kẹo xuất nên ta cần tìm hàm sinh cho số cách chọn loại kẹo Ta có cách chọn kẹo cách chọn kẹo cách chọn kẹo cách chọn kẹo 71 Vậy hàm sinh cho số cách chọn loại kẹo x + x3 + x5 + Suy ra, hàm sinh cho số cách chọn n kẹo từ loại kẹo A(x) = (x + x3 + x5 + )4 = x4 (1 + x2 + x4 + )4 = x4 (1 − x2 )4 b Ta có, số cách chọn kẹo thỏa mãn điều kiện số kẹo loại chia hết cho cách chọn kẹo cách chọn kẹo cách chọn kẹo cách chọn kẹo cách chọn kẹo cách chọn kẹo cách chọn kẹo Hàm sinh cho số cách chọn loại kẹo thỏa mãn điều kiện + x3 + x6 + x9 + Vậy hàm sinh cho số cách chọn n kẹo từ loại kẹo thỏa mãn điều kiện B(x) = (1 + x3 + x6 + x9 + )4 = (1 − x3 )4 c Lập luận tương tự trên, ta có: + Hàm sinh cho số cách chọn kẹo sôcôla + Hàm sinh cho số cách chọn kẹo chanh + x + x2 + Hàm sinh cho số cách chọn kẹo dâu + x + x2 + x3 + · · · = 1−x Hàm sinh cho số cách chọn kẹo sữa + x + x2 + x3 + · · · = 1−x Vậy hàm sinh cho số cách chọn n kẹo từ loại kẹo thỏa mãn điều kiện 1 + x + x2 C(x) = 1(1 + x + x ) = 1−x 1−x (1 − x)2 72 Ví dụ 3.13 Giả sử có số lượng đủ lớn loại hoa gồm táo, mận, lê, đào Hỏi có cách xếp giỏ gồm n trái thỏa mãn yêu cầu sau đây: + Số táo phải chẵn; + Số mận phải chia hết cho 5; + Số lê không vượt 4; + Số đào không nhiều Lời giải Gọi an , bn , cn , dn tương ứng số cách chọn n quả: táo, mận, lê, đào thỏa mãn u cầu tốn Khi đó, số cách chọn n trái thỏa mãn yêu cầu toán Sn = ap b q c r d s p+q+r+s=n Ta có: Hàm sinh dãy (an ) A(x) = + x2 + x4 + · · · = − x2 Hàm sinh dãy (bn ) B(x) = + x5 + x10 + x15 + · · · = − x5 Hàm sinh dãy (cn ) A(x) = + x + x2 + x3 + x4 = − x5 1−x Hàm sinh dãy (dn ) D(x) = + x Do Sn = p+q+r+s=n ap bq cr ds nên hàm sinh dãy Sn S(x) = A(x)B(x)C(x)D(x) 1 − x5 (1 + x) − x2 − x5 − x = (1 − x)2 = Khai triển S(x) = theo chuỗi lũy thừa ta có (1 − x)2 ∞ (n + 1)xn S(x) = + 2x + 3x + · · · = n=0 Vậy Sn = n + 73 Ví dụ 3.14 [VMO 2012] Cho nhóm gồm gái, kí hiệu G1 , G2 , G3 , G4 , G5 12 chàng trai Có 17 ghế xếp thành hàng ngang Người ta xếp nhóm người cho ngồi vào ghế cho điều kiện sau đồng thời thỏa mãn: + Mỗi ghế có người ngồi; + Thứ tự ngồi cô gái xếp theo thứ tự từ trái qua phải G1 , G2 , G3 , G4 , G5 ; + Giữa G1 G2 có chàng trai; + Giữa G4 G5 có chàng trai nhiều chàng trai Hỏi có cách xếp vậy? Lời giải Gọi x1 số chàng trai xếp bên trái G1 x2 số chàng trai xếp G1 G2 x3 số chàng trai xếp G2 G3 x4 số chàng trai xếp G3 G4 x5 số chàng trai xếp G4 G5 x6 số chàng trai xếp bên phải G5 Khi đó, số (x1 , x2 , x3 , x4 , x5 , x6 ) hồn tồn xác định vị trí gái ta có: i) x1 + x2 + x3 + x4 + x5 + x6 = 12; ii) x2 ≥ 3; iii) ≤ x5 ≤ Ta tính số cách chọn (x1 , x2 , x3 , x4 , x5 , x6 ) Hàm sinh cho số cách chọn x1 , x3 , x4 , x6 1+t+t2 +t3 +· · · = 1−t t3 1−t Hàm sinh cho số cách chọn x5 t + t2 + t3 + t4 = t(1 + t + t2 + t3 ) Hàm sinh cho số cách chọn x2 t3 + t4 + t5 + · · · = Vây hàm sinh cho số cách chọn (x1 , x2 , x3 , x4 , x5 , x6 ) f (t) = t4 t4 t5 t6 t7 (1 + t + t + t ) = + + + (1 − t)5 (1 − t)5 (1 − t)5 (1 − t)5 (1 − t)5 Số cần tìm hệ số t12 khai triển f (t) thành lũy thừa hay tổng hệ số t8 , t7 , t6 , t5 khai triển g(t) = Hệ số của tk khai triển (1 − t)5 k Suy số cách chọn Ck+4 (1 − x)5 (x1 , x2 , x3 , x4 , x5 , x6 ) C12 + C11 + C10 + C95 74 Do vai trò 12 người nam nên số cách xếp thỏa mãn điều kiện toán (C12 + C11 + C10 + C95 )12! Tiếp theo ta xét toán nhị phân Cây nhị phân mà đỉnh có khơng q hai Ví dụ 3.15 Cho trước n đỉnh mặt phẳng Hỏi xây dựng nhị phân từ đỉnh này? Lời giải Trong nhị phân n đỉnh, ta ln có đẳng thức: n=1+l+r đó: l số đỉnh trái r số đỉnh phải Kí hiệu cn số nhị phân n đỉnh (n = 0, 1, 2, 3, ) Tập nhị phân n đỉnh phân hoạch thành lớp theo số đỉnh trái l = 0, 1, 2, 3, , n − Vậy cn = c0 cn−1 + c1 cn−2 + c2 cn−3 + · · · + cn−1 c0 , n ≥ Xây dựng hàm sinh ∞ cn x n C(x) = n=0 Theo (3.2) ta có ∞ (c0 cn−1 + c1 cn−2 + c2 cn−3 + · · · + cn−1 c0 )xn C(x) = + n=1 ∞ (c0 cn + c1 cn−1 + c2 cn−2 + · · · + cn c0 )xn =1+x n=0 = + x.C (x) Ta phương trình bậc hai C(x) x.C (x) − C(x) + = Giải phương trình ta hàm sinh C(x) = 1± 75 √ − 4x 2x (3.1) Để khai triểm Maclaurine hàm sinh ta cần khai triển hàm nhận √ ∞ − 4x = − n=1 √ − 4x n−1 n C x n 2n−2 Hàm sinh C(x) hàm dương nên theo khai triển cơng thức nghiệm ta phải lấy dấu trừ nhận C(x) = 1− √ − 4x = 2x ∞ n=1 n−1 n−1 C x = n 2n−2 ∞ n=0 Vậy số nhị phân n đỉnh cn = C n , n = 0, 1, 2, 3, n + 2n Dãy số cn gọi dãy số Catalan 76 C n xn n + 2n Kết luận Trong luận văn này, tác giả đặt hoàn thành số kết sau: (i) Trình bày số khái niệm tổ hợp tổ hợp suy rộng; (ii) Trình bày bốn nguyên lý tổ hợp Đó Nguyên lý Dirichlet, Nguyên lý bù trừ, Nguyên lý cực hạn, Nguyên lý bất biến; (iii) Đưa ứng dụng giải số toán tổ hợp áp dụng nguyên lý trên; (iv) Xây dựng đồng thức tổ hợp; (v) Sử dụng kết đạt để giải số toán dạng khác; 77 Tài liệu tham khảo [1] Nguyễn Hữu Điển (1999), Phương pháp Dirichlet ứng dụng, NXB Khoa học kỹ thuật [2] Nguyễn Văn Mậu (2008), Chuyên đề chọn lọc tổ hợp toán rời rạc, NXB Giáo Dục [3] Nguyễn Văn Mậu (4/2012), Các chuyên đề toán bồi dưỡng học sinh giỏi , Kỷ yếu hội nghị khoa học, Hà Nội [4] Đinh Thị Kim Phương (11/2012), Các chuyên đề toán bồi dưỡng học sinh giỏi , Kỷ yếu hội nghị khoa học, Thái Nguyên [5] Phạm Minh Phương ( 2010), Một số chuyên đề toán tổ hợp bồi dưỡng học sinh giỏi THPT, NXB Giáo dục Việt Nam [6] Hồng Chí Thành (2001), Giáo trình tổ hợp, NXB Đại học Quốc gia Hà Nội [7] Tạp chí tốn học tuổi trẻ, Tuyển tập năm, NXB Giáo Dục, 2003 [8] Alexander Yong(2005), "On combinatorics of Quiver components Formulas", Journal of Algebraric Combinatorics, vol 21, 351- 371 [9] Kenneth H Rosen(1998), Toán học rời rạc ứng dụng tin học, NXB khoa học kĩ thuật [10] Tài liệu từ Internet 78 ... chỉnh hợp, tổ hợp, nhiều toán ta phải sử dụng số nguyên lý khác tổ hợp Vì vậy, để hiểu rõ nắm bắt sâu vể vấn đề này, chọn đề tài Một vài nguyên lý tốn tổ hợp Luận văn trình bày số nguyên lý tổ hợp. .. chỉnh hợp, tổ hợp, nhị thức Newton đồ thị Chương : Một vài nguyên lý tổ hợp Chương gồm nội dung chính, trình bày bốn ngun lý tổ hợp ví dụ áp dụng nguyên lý Cụ thể là: Mục 2.1 trình bày nguyên lý. .. Một vài nguyên lý tổ hợp 2.1 Nguyên lý Dirichlet 2.1.1 Nguyên lý Dirichlet 2.1.2 Nguyên lý Dirichlet áp dụng hình học 2.2 Nguyên lý bù trừ