Luận văn Một vài nguyên lý và bài toán tổ hợp

Nội dung tài liệu: Luận văn Một vài nguyên lý và bài toán tổ hợp

1. ĐẠ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
2. ĐẠ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
3. Mục lục Mở đầu 3 1 Ki¸n thùc chu©n bị 5 1.1 Nguy¶n lý quy n¤p . . . . . . . . . . . . . . . . . . . .5 1.2 Hai quy t­c đếm cơ b£n . . . . . . . . . . . . . . . . . .8 1.3 Ho¡n vị . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.4 Ch¿nh hñp . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 Tê hñp . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.1 Tê hñp . . . . . . . . . . . . . . . . . . . . . . . 14 1.5.2 Ứng dụng trong sè học . . . . . . . . . . . . . . 16 1.6 Nhị thùc Newton . . . . . . . . . . . . . . . . . . . . . 18 1.7 Đồ thị c¥y . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 Mët vài nguy¶n lý trong tê hñp 26 2.1 Nguy¶n lý Dirichlet . . . . . . . . . . . . . . . . . . . . 26 2.1.1 Nguy¶n lý Dirichlet . . . . . . . . . . . . . . . . 26 2.1.2 Nguy¶n lý Dirichlet ¡p dụng trong h¼nh học tê hñp 31 2.2 Nguy¶n lý bù trø . . . . . . . . . . . . . . . . . . . . . 34 2.3 Nguy¶n lý cực h¤n . . . . . . . . . . . . . . . . . . . . . 42 2.4 Nguy¶n lý b§t bi¸n . . . . . . . . . . . . . . . . . . . . 51 3 Mët vài đồng nh§t thùc trong tê hñp 60 3.1 X¥y dựng đồng nh§t thùc qua h» phương tr¼nh . . . . . 60 3.2 X¥y dựng đồng nh§t thùc qua sè phùc . . . . . . . . . 66 3.3 X¥y dựng đồng nh§t thùc qua hàm sinh . . . . . . . . . 69 3.3.1 Kh¡i ni»m hàm sinh . . . . . . . . . . . . . . . . 70 3.3.2 Mët sè đồng nh§t thùc li¶n quan đến hàm sinh . 70 3.3.3 Ứng dụng cõa hàm sinh . . . . . . . . . . . . . . 71 K¸t luªn ............................ 77 Tài li»u tham kh£o ...................... 78 1
4. Lời c£m ơn Tôi xin được bày tỏ láng k½nh trọng và 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 cũng như gi£i đáp c¡c th­c m­c cõa tôi trong suèt qu¡ tr¼nh tôi thực hi»n đề tài. Tôi xin gûi lời c£m ơn ch¥n thành tới c¡c th¦y cô Khoa To¡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; c¡c 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 và b¤n b± đã luôn động vi¶n tôi trong suèt qu¡ tr¼nh học tªp và thực hi»n luªn v«n. 2
5. Mở đầu Tư duy v· tê hñp xu§t hi»n tø r§t sớm trong lịch sû ph¡t triºn cõa nh¥n lo¤i. Tuy nhi¶n, lý thuy¸t tê hñp được xem h¼nh thành như mët ngành to¡n học vào kho£ng th¸ kỷ 17 b¬ng mët lo¤t c¡c công tr¼nh nêi ti¸ng cõa c¡c nhà to¡n học như Passcal, Fermat, Leibniz, Euler, . . . . Kº tø sau khi tin học ra đời, lý thuy¸t tê hñp ph¡t triºn ngày càng m¤nh m³. C¡c v§n đề li¶n quan đ¸n lý thuy¸t tê hñp là mët bë phªn quan trọng, h§p d¨n và l½ thú cõa to¡n học nói chung và cõa to¡n rời r¤c nói ri¶ng. Nó không ch¿ có nëi dung phong phú, đa d¤ng, mà cán có nhi·u ùng dụng trong thực t¸ đời sèng. Trong to¡n sơ c§p, tê hñp cũng xu§t hi»n với nhi·u bài to¡n hay với độ khó cao. Khi gi£i c¡c bài to¡n tê hñp, ta ph£i li»t k¶, đếm c¡c đối tượng theo c¡c t½nh ch§t nào đó. Để làm được vi»c này, ngoài vi»c sû dụng hai quy t­c đếm cơ b£n, c¡c ki¸n thùc v· ho¡n vị, ch¿nh hñp, tê hñp, trong nhi·u bài to¡n ta ph£i sû dụng mët sè nguy¶n lý kh¡c trong tê hñp. V¼ vªy, để hiºu rã và n­m b­t s¥u hơn vº v§n đề này, tôi đã chọn đề tài Mët vài nguy¶n lý và bài to¡n tê hñp. Luªn v«n đã tr¼nh bày mët sè nguy¶n lý cơ b£n trong tê hñp và x¥y dựng mët sè bài to¡n ¡p dụng. Luªn v«n gồm ph¦n mở đầu, ba chương, k¸t luªn và danh mục tài li»u tham kh£o. Chương 1 : Ki¸n thùc chu©n bị. Trong chương này, t¡c gi£ đã tr¼nh bày mët sè lý thuy¸t v· nguy¶n lý quy n¤p, hai quy t­c đếm cơ b£n, ho¡n vị, ch¿nh hñp, tê hñp, nhị thùc Newton và đồ thị c¥y. Chương 2: Mët vài nguy¶n lý trong tê hñp. Chương 2 gồm 4 nëi dung ch½nh, tr¼nh bày bèn nguy¶n lý cơ b£n trong tê hñp và c¡c v½ dụ ¡p dụng c¡c nguy¶n 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ý này cán được gọi là nguy¶n lý lồng chim bồ c¥u. Gi£ sû có mët đàn chim bồ c¥u bay vào chuồng. N¸u sè chim nhi·u hơn sè ng«n chuồng th¼ ½t nh§t có ng«n 3
6. có nhi·u hơn 1 con chim. Ph¡t triºn d¤ng to¡n này, Piter Gustave Dirichlet đã đưa ra mët nguy¶n lý chùng minh to¡n học đơn gi£n, được ph¡t biºu như sau: "N¸u có N đồ vªt được đặt vào k hëp th¼ tồn t¤i mët hëp chùa ½t nh§t N   + 1 đồ vªt." k Mục 2.2 tr¼nh bày Nguy¶n lý bù trø. Khi hai công vi»c có thº làm đồng thời, chúng ta không thº dùng quy t­c cëng để t½nh sè c¡ch thực hi»n nhi»m vụ gồm c£ hai vi»c. Cëng sè c¡ch thực hi»n méi vi»c s³ d¨n đến sự trùng lặp, v¼ nhúng c¡ch làm c£ hai công vi»c s³ được t½nh hai l¦n. Để t½nh đúng sè c¡ch thực hi»n nhi»m vụ này ta cëng sè c¡ch làm méi mët trong hai vi»c rồi trø đi sè c¡ch làm đồng thời c£ hai công vi»c. Nguy¶n lý này được mở rëng cho trường hñp đếm sè ph¦n tû cõa hñp c¡c tªp hñp b§t k¼. Đó là Nguy¶n lý bù trø. Nguy¶n lý thù 3 là Nguy¶n lý cực h¤n, được tr¼nh bày trong mục 2. 3. Nguy¶n lý này ch¿ ra r¬ng tồn t¤i ph¦n tû lớn nh§t và ph¦n tû nhỏ nh§t cõa mët tªp hñp húu h¤n. Nguy¶n lý này có r§t nhi·u ùng dụng trong vi»c gi£i c¡c bài to¡n tê hñp, gi£i mët sè phương tr¼nh nghi»m nguy¶n, chùng minh c¡c b§t đẳng thùc, . . . . Cuèi cùng, mục 2. 4 tr¼nh bày nguy¶n lý thù 4 là Nguy¶n lý b§t bi¸n. Trong mục này, t¡c gi£ đã tr¼nh bày hai m¨u bài to¡n têng qu¡t thường được gi£i b¬ng nguy¶n lý b§t bi¸n và đưa ra mët v½ dụ sû dụng nguy¶n lý b§t bi¸n. Chương 3. Mët vài đồng nh§t thùc trong tê hñp. Chương này tr¼nh bày mët sè v½ dụ v· x¥y dựng đồng nh§t thùc trong tê hñp qua h» phương tr¼nh, sè phùc và hàm sinh, . . . 4
7. Chương 1 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 (α) đúng với mët α 2 N. (ii) P (n + 1) đúng khi P (n) đúng, ở đó n ≥ α; n 2 N th¼ P (n) đúng với mọ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 (α) đúng với mët α 2 N. (ii) P (n + 1) đúng khi P (α);P (α + 1); :::; P (n) đúng, ở đó n ≥ α; n 2 N, th¼ P (n) đúng với mọi sè tự nhi¶n n ≥ α. C¡ch chùng minh mët định lý hay mët bài to¡n có sû dụng nguy¶n lý quy n¤p được gọi là ph²p quy n¤p hay phương ph¡p quy n¤p to¡n học. Sau đây, ta s³ x²t mët sè v½ dụ ¡p dụng hai nguy¶n lý này. V½ dụ 1.1. Chùng minh r¬ng, với sè nguy¶n n ≥ 1 và sè thực a > 0 ta luôn có đồng nh§t thùc n X (−1)kCk n!an n = : ak + 1 Qn (1 + ka) k=1 k=1 Lời gi£i. Trước ti¶n, ta chùng minh b¬ng quy n¤p theo n r¬ng Z 1 n a n n!a (1 − x ) dx = Qn : 0 k=1(1 + ka) 5
8. Thªt vªy Với n = 1 ta có Z 1  a+1 1 1 a x  a 1!a (1 − x )dx = x −  = = : 0 a + 1 0 a + 1 1 + 1:a Suy ra kh¯ng định đúng với n = 1. Đặt Z 1 a n In = (1 − x ) dx: 0 Gi£ sû n!an In = Qn : k=1(1 + ka) Ta ph£i chùng minh (n + 1)!an+1 I = : n+1 Qn+1 k=1(1 + ka) Ta có Z 1 Z 1 a n+1 a a n In+1 = (1 − x ) dx = (n + 1)a x (1 − x ) dx = (n + 1)a(In − In+!): 0 0 Hay (n + 1)a I = I : n+1 1 + (n + 1)a n Theo gi£ thi¸t quy n¤p ta có (n + 1)!an+1 I = : n+1 Qn+1 k=1(1 + ka) Suy ra kh¯ng định tr¶n đúng với n + 1. Vªy kh¯ng đinh tr¶n đúng với mọi n ≥ 1. Tø đó suy ra n n X (−1)kCk X Z 1 Z 1 n!an n = (−1)kCk xakdx = (1 − xa)ndx = : ak + 1 n Qn (1 + ka) k=0 k=0 0 0 k=1 V½ dụ 1.2. Chùng minh r¬ng với sè nguy¶n n > 0 ta có đồng nh§t thùc 1:2 + 2:22 + ··· + n:2n = (n − 1)2n+1 + 2: 6
9. Lời gi£i. Ta chùng minh b¬ng quy n¤p theo n. + Với n = 1 ta có 1:2 = 2 = (1 − 1)21+1 + 2. Chùng tỏ k¸t luªn đúng với n = 1. + Gi£ sû k¸t luªn đúng với n ≥ 1. Khi đó 1:2 + 2:22 + ··· + n:2n = (n − 1)2n+1 + 2: + Ta ph£i chùng minh k¸t luªn đúng với n + 1. Tùc là 1:2 + 2:22 + ··· + n:2n + (n + 1)2(n+1) = n2n+2 + 2: Thªt vªy, ta có 1:2 + 2:22 + ··· + n:2n + (n + 1)2(n+1) = (n − 1)2n+1 + 2 + (n + 1)2n+1 = n2n+2 + 2: Chùng tỏ k¸t luªn đúng với n + 1. Vªy kh¯ng định đúng với mọi sè nguy¶n n > 0. V½ dụ 1.3. D¢y (an) được cho như sau: a0 = 1; a1 = 3; a2 = 6; a3 = 10; a4 = 15; a5 = 21; :::: X¡c định (an) theo n và chùng minh b§t đ¯ng thùc 1 1 1 1 1 1 T = 1 −
   1 −
   1 −
   :::1 −
   < + : 3 6 10 an 3 n Lời gi£i. Ta có a0 = 1; a1 = 3 = a0 + 1 + 1; a2 = 6 = a1 + 2 + 1; a3 = 10 = a2 + 3 + 1; a4 = 15 = a3 + 4 + 1; a5 = 21 = a4 + 5 + 1; ::: Suy ra an = an−1 + n + 1. Đi·u này d¹ dàng có được b¬ng chùng minh quy n¤p. (n + 1)(n + 2) Vªy a = 1 + 2 + 3 + 4 + ::: + n + n + 1 = : n 2 1 a − 1 (k + 1)(k + 2) − 2 k(k + 3) Suy ra 1 − = k = = : ak ak (k + 1)(k + 2) (k + 1)(k + 2) Như vªy 1 1 1 1 − = 1 −
   1 +
   : ak k + 1 k + 2 7
10. Suy ra 1 1 1 1 1 1 T =1 −
    1 +
    1 −
    1 +
    ::: 1 −
    1 +
    2 3 3 4 n + 1 n + 2 1 1 1 1 1 1 = 1 −
    1 −
    1 −
    ::: 1 −
    1 +
    2 32 42 52 (n + 1)2 (n + 2) 1 32 − 1 42 − 1 52 − 1 (n + 1)2 − 1 1 =
    
    
    :::
    1 +
    2 32 42 52 (n + 1)2 (n + 2) 2:3:42:52 ::: (n − 1)2:n2(n + 1)(n + 2)(n + 3) = 2:32:42:52 ::: (n − 1)2:n2(n + 1)2(n + 2) n + 3 n + 3 1 1 = < = + : 3(n + 1) 3n 3 n (n + 1)(n + 2) 1 1 Vªy a = và T < + : n 2 3 n 1.2 Hai quy t­c đếm cơ b£n Chương tr¼nh to¡n phê thông lớp 11 đã trang bị cho học sinh hai quy t­c đếm cơ b£n, đó là quy t­c cëng và quy t­c nh¥n. Đây là hai công cụ quan trọng giúp học sinh gi£i được mët sè bài to¡n tê hñp đơn gi£n. Quy t­c cëng được ph¡t biºu như sau: Gi£ sû, mët công vi»c có thº được thực hi»n theo mët trong k phương ¡n A1;A2;:::;Ak: Có n1 c¡ch thực hi»n phương ¡n A1, n2 c¡ch thực hi»n phương ¡n A2,..., nk c¡ch thực hi»n phương ¡n Ak. Khi đó công vi»c có thº được thực hi»n bởi n1 + n2 + ··· + nk c¡ch. B£n ch§t cõa quy t­c cëng là công thùc t½nh sè ph¦n tû cõa hñp n tªp hñp húu h¤n đôi mët không giao nhau. Cụ thº ta có: Cho A1;A2;:::;Ak là c¡c tªp rời nhau. Khi đó A1 [ A2 [···[ Ak = A1 + A2 + ··· + Ak: Khi mët công vi»c được thực hi»n bởi nhi·u công đoạn li¶n ti¸p, th¼ ta ph£i sû dụng quy t­c nh¥n. Quy t­c nh¥n cho nhi·u công đoạn được ph¡t biºu như sau: Gi£ sû mët công vi»c nào đó bao gồm k công đo¤n A1;A2;:::;Ak. Công đo¤n A1 có thº thực hi»n theo n1 c¡ch, công đo¤n A2 có thº thực hi»n theo n2 c¡ch, . . . , công đo¤n Ak có thº thực hi»n theo nk c¡ch. Khi đó công vi»c có thº thực hi»n theo n1n2 : : : nk c¡ch. 8