Luận văn Phép phân hoạch tập howpjvaf một số ứng dụng trong toán sơ cấp

kê. Ng−ời ta có thể sử dụng phần mềm Maple để tính các số Stirling loại hai. Số Stirling loại hai d−ợc đặt theo tên của nhà toán học James Stirling (1692-1770), ng−ời đã giới thiệu và nghiên cứu khái niệm này vào Thế kỉ 18. Chú ý rằng nếu {X1, . . . , Xk} là một phân hoạch của tập X thành k khối thì 1 6 k 6 n, trong đó n > 0 là số phần tử của X . Vì thế ta có công thức tính số Bell thông qua số Stirling loại hai nh− sau. 1.2.4 Bổ đề. Bn = S(n, 1) + . . . + S(n, n− 1) + S(n, n). 1.2.5 Ví dụ. Để tính B5, theo Bổ đề 1.2.4 ta cần tính S(5, k) với k = 1, 2, 3, 4, 5. Ta có S(5, 1) = 1, S(5, 2) = 15, S(5, 3) = 25, S(5, 4) = 10, S(5, 5) = 1. Do đó B5 = S(5, 0) + S(5, 1) + S(5, 2) + S(5, 3) + S(5, 4) + S(5, 5) = 52. 12 Từ Bổ đề 1.2.4 ta thấy rằng các số Stirling loại hai rất quan trọng trong việc tính toán số Bell. Do đó trong phần tiếp theo của tiết này chúng ta nghiên cứu một số tính chất về số Stirling loại hai. Kết quả sau đây cho ta một số công thức tính số Stirling loại hai. Với k ∈ {0, 1, . . . , n}, ta đặt Ckn = n! k!(n − k)! . Ta gọi Ckn là hệ số nhị thức thứ k ứng với n hay số tổ hợp chập k của n phần tử. 1.2.6 Định lý. Cho n, k là các số tự nhiên với k 6 n. Khi đó (i) S(n, k) = 1 k! k∑ i=0 (−1)k−iinCik. (ii) S(n, k) = n! k! ∑ i1+...+ik=n 1 i1! . . . ik! . (iii) S(n + 1, k) = n∑ r=k−1 kn−rS(r, k − 1). Chứng minh. Giả sử có bộ số (i1, i2, . . . , ik) sao cho k∑ j=1 ij = n với ik ≥ 1. Ta sẽ xác định số cách phân hoạch tập X thành k tập con không rỗng sao cho số phần tử của các tập là ij với j ∈ {1, 2, . . . , k}. Số cách chọn i1 từ tập hợp n phần tử của tập X là Ci1n . Với mỗi cách chọn i1 phần tử thì có Ci2n−i1 cách chọn i2 phần tử. Với mỗi cách chọn i1 phần tử và i2 phần tử thì có Ci3n−i1−i2 cách chọn i3 phần tử. Tổng quát với mỗi cách chọn i1 phần tử và . . . ik−1 phần tử thì có C ik n−i1−i2−...−ik cách chọn ik phần tử. Hơn nữa, các tập con của phân hoạch không phân biệt thứ tự, tức là bộ số sau không phân biệt thứ tự (i1, i2, . . . , ik). Do đó số cách phân hoạch tập hợp X thành k tập con không rỗng sao cho số phần tử của các tập là ij với j ∈ {1, 2, . . . , k} bằng 1 k! Ci1n C i2 n−i1 . . .Cikn−i1−i2−...−ik hay 1 k! n! i1!i2!. . .ik! hay n! k! 1 i1!i2!. . .ik! . Số cách phân hoạch tập hợp X thành k tập con không rỗng là S(n, k) = ∑ i1+...+ik=n n! k! ( 1 i1! . . . ik! ) hay S(n, k) = n! k! ∑ i1+...+ik=n 1 i1! . . . ik! . 13 1.2.7 Ví dụ. Giả sử ta cần tìm S(5, 3). Sử dụng Định lí 1.2.6(i) ta có S(5, 3) = 1 3! [(−1)305C03 + (−1) 215C13 + (−1) 035C33 = 25. Giả sử ta cần tìm S(6, 4). Sử dụng Định lí 1.2.6(i) ta có S(6, 4) = 1 4! [(−1)406C04 + (−1)316C14 + (−1) 226C24 + (−1)3 6C34 + (−1) 046C44 ] = 65. Chúng ta cũng có thể sử dụng Định lí 1.2.6 (ii) để tính S(6, 4). Bằng cách sử dụng Định lí 1.2.6 (iii) ta đ−ợc S(6, 4) = 5∑ r=3 45−rS(r, 3) = 42S(3, 3) + 4S(4, 3) + S(5, 3) = 16 + 24 + 25 = 60 hoặc S(7, 4) = 6∑ r=3 46−rS(r, 3) = 43S(3, 3) + 42S(4, 3) + 4S(5, 3) + S(6, 3) = 64 + 96 + 100 + 90 = 350. (1.1) (1.2) Công thức tính số Sirling loại 2 bằng cách trực tiếp nh− trong Định lí 1.2.6(i) với số n gặp khá nhiều khó khăn khi số tự nhiên n lớn dần lên. Mệnh đề sau đây sẽ giúp ta khắc phục đ−ợc một phần những khó khăn đó. 1.2.8 Mệnh đề. Cho n, k là các số tự nhiên với 2 6 k 6 n. Khi đó S(n + 1, k) = kS(n, k) + S(n, k − 1). Chứng minh. Xét tập hợp bất kì có n + 1 phần tử, chẳng hạn A = {x1, x2, x3, . . . , xn+1}. 14 Theo định nghĩa S(n + 1, k) là số phân hoạch tập hợp A thành k khối. Mặt khác ta có thể chia tập B tất cả các phân hoạch trên thành 2 tập con rời nhau nh− sau: B1 gồm tất cả các phân hoạch của tập hợp A thành k khối trong đó có một khối là {xn+1}, còn B2 gồm tất cả các phân hoạch của tập hợp A thành k khối trong đó không có khối nào là {xn+1}. Khi đó mỗi phân hoạch thuộc B1 sẽ chia tập hợp {x1, x2, x3, . . . , xn} thành k− 1 khối và có S(n, k− 1) cách chia nh− thế. Do đó lực l−ợng của B1 là S(n, k−1). Nếu {xn+1} không là một khối thì xn+1 sẽ nằm trong một khối với ít nhất một phần tử khác của A. Vì có S(n, k) cách phân hoạch tập hợp {x1, x2, x3, . . . , xn} thành k khối nên ta có tất cả kS(n, k) cách phân hoạch của tập hợp A thành k khối, trong đó không có khối nào là xn+1. Do đó lực l−ợng của B2 là kS(n, k). Theo qui tắc cộng, ta có: S(n + 1, k) = kS(n, k) + S(n, k − 1). 1.2.9 Ví dụ. Chẳng hạn khi đã biết S(5, 3) = 25, S(5, 4) = 10 thì có thể tính đ−ợc S(6, 4) bằng công thức sau đây S(6, 4) = 4S(5, 4) + S(5, 3) = 40 + 25 = 65. Nh− vậy, với công thức truy hồi trên có −u điểm rất lớn so với công thức tính số Sirling loại 2 bằng cách trực tiếp nh− trong Định lí 1.2.6(i) với số n lớn. Phần cuối của tiết này trình bày một công thức tổng quát để tính số Stirling loại hai của một tập hợp gồm n phần tử với phân hoạch thành k khối, chẳng hạn k = 2, 3, 4, 5, n − 1, n − 2. 1.2.10 Mệnh đề. Ta có các đẳng thức sau (i) S(n, 2) = 2n−1 − 1, n ≥ 2; (ii) S(n, 3) = 3n − 3.2n + 3 6 , n ≥ 3; 15 (iii) S(n, 4) = 4n − 4.3n + 6.2n − 4 24 , n ≥ 4; (iv) S(n, 5) = 5n−1 − 4n + 2.3n − 2n+1 + 1 24 , n ≥ 5; (v) S(n, n − 1) = C2n, n ≥ 2; (vi) S(n, n− 2) = C3n + 3C 4 n, n ≥ 4. Chứng minh. Ta sẽ chứng minh các đẳng thức trên bằng ph−ơng pháp qui nạp đồng thời kết hợp với công thức truy hồi S(n + 1, k) = kS(n, k) + S(n, k − 1). (i) Khi n = 2, ta có S(n, 2)=S(2, 2) = 1 và 2n−1 − 1 = 2 − 1 = 1, do đó đẳng thức đúng với n = 2. Giả sử đẳng thức đúng với n = k ≥ 2, tức là S(k, 2) = 2k−1 − 1. Ta cần chứng minh đẳng thức đúng với n = k + 1. Ta có S(k + 1, 2) = 2S(k, 2) + S(k, 1) = 2S(k, 2) + 1 = (2k−1 − 1)2 + 1 = 2k − 1. Ngoài ra công thức trên còn có thể lí giải nh− sau: Mỗi cách phân hoạch tập hợp X gồm n phần tử thành 2 tập con A và B thì 2 tập con đó là bù của nhau, tức là A = X B. Mà có 2n cặp (A,B) có thứ tự, bao gồm cả hai cặp (A, ∅), (∅, B). Nh− vậy, nếu không tính hai cặp này thì có 2n − 2 cặp bù nhau có thứ tự. Vì trong phân hoạch ta không xét thứ tự của các cặp nên số cặp không có thứ tự là 2n − 2 2 = 2n−1 − 1. (ii) Khi n = 3, ta có S(n, 3) = S(3, 3) = 1 và 3n − 3.2n + 3 6 = 33 − 3.23 + 3 6 = 1. Do đó đẳng thức đúng với n = 3. Giả sử đẳng thức đúng với n = k ≥ 3, tức là S(k, 3) = 3k − 3.2k + 3 6 . Ta cần chứng minh đẳng thức đúng với 16 n = k + 1. Thật vậy, ta có S(k + 1, 3) = 3S(k, 3) + S(k, 2) = 3 3k − 3.2k + 3 6 + 2k−1 − 1 = 3k − 2.2k + 1 2 . (iii) Khi n = 4, ta có S(n, 4) = S(4, 4) = 1 và 4n − 4.3n + 6.2n − 4 24 = 44 − 4.34 + 6.24 − 4 24 = 1. Do đó đẳng thức đúng với n = 4. Giả sử đẳng thức đúng với n = k ≥ 4, tức là S(k, 4) = 4k − 4.3k + 6.2k − 4 24 . Ta cần chứng minh đẳng thức đúng với n = k + 1. Thật vậy, ta có S(k + 1, 4) = 4S(k, 4) + S(k, 3). Theo kết quả (ii) ở trên ta có S(k, 3) = 3k − 3.2k + 3 6 . Suy ra S(k + 1, 4) = 4 4k − 4.3k + 6.2k − 4 24 + 3k − 3.2k + 3 6 = 4k+1 − 4.3k+1 + 6.2k+1 − 4 24 . (iv) Khi n = 5, ta có: S(n, 5) = S(5, 5) = 1 và 5n−1 − 4n + 2.3n − 2n+1 + 1 24 = 54 − 45 + 2.35 − 26 + 1 24 = 1. Vì thế đẳng thức đúng với n = 5. Giả sử đẳng thức đúng với n = k ≥ 5, tức là S(k, 5) = 5k−1 − 4k + 2.3k − 2k+1 + 1 24 . Ta cần chứng minh đẳng thức đúng với n = k + 1. Thật vậy, ta có S(k + 1, 5) = 5S(k, 5) + S(k, 4). Theo kết quả (iii) ở trên ta có S(k, 4) = 4k − 4.3k + 6.2k − 4 24 . 17 Vì thế S(k + 1, 5) = 5 5k−1 − 4k + 2.3k − 2k+1 + 1 24 + 4k − 4.3k + 62k − 4 24 = 5k − 4k+1 + 2.3k+1 − 2k+2 + 1 24 . (v) Khi n = 2, ta có S(2, 1) = C22 = 1, do đó đẳng thức đúng với n = 2. Giả sử đẳng thức đúng với n = k, tức là S(k, k − 1) = C2k , k ≥ 2, k ∈ N . Ta cần chứng minh đẳng thức đúng với n = k + 1. Thật vậy, ta có S(k + 1, k) = kS(k, k) + S(k, k − 1) = k + C2k = C 2 k+1. (vi) Khi n = 4, ta có S(4, 2) = 7, C34 +3C 4 4 = 7 nên đẳng thức đã cho đúng với n = 4. Giả sử đẳng thức đã cho đúng với n = k, tức là S(k, k − 2) = C3k +3C 4 k, k ≥ 4, k ∈ N . Ta cần chứng minh đẳng thức đúng với n = k+1. Thật vậy, ta có S(k + 1, k − 1) = (k − 1)S(k, k − 1) + S(k, k − 2) = (k − 1)C2k + C 3 k + 3C 4 k = C 3 k+1 + 3C 4 k+1. 1.2.11 Ví dụ. Theo công thức trong mệnh đề trên ta có S(8, 3) = 38 − 3.28 + 3 6 = 966; S(10, 4) = 410 − 4.310 + 6.210 − 4 24 = 34105. Nh− vậy các công thức trong mệnh đề trên mang hiệu ứng khá mạnh giúp ta có thể tra cứu số phân hoạch của tập hợp gồm n phần tử thành k khối với những giá trị của k đặc biệt ở trên. 18 1.3 Một số công thức tính hàm phân hoạch tập hợp Hàm phân hoạch tập hợp là hàm biến nguyên với giá trị nguyên đ−ợc cho bởi công thức f(n) = Bn với mọi n ∈ N. Mục tiêu của tiết này là chứng minh chi tiết một số công thức tính hàm phân hoạch tập hợp, tức là tính số Bell Bn, đồng thời đ−a ra tam giác Pascal tính hàm phân hoạch tập hợp. 1.3.1 Mệnh đề. Ta có công thức truy hồi sau đây. Bn+1 = n∑ k=0 CknBk = C 0 nB0 + C 1 nB1 + C 2 nB2 + . . . + C k nBk + . . . + C n nBn. Chứng minh. Ta xây dựng phiếm hàm tuyến tính L : R[x]→ R xác định bởi (x)k = Akx = x(x − 1) . . . (x − k + 1) → L((x)k) = 1 với mọi k = 0, 1, 2 . . .. Ta chứng minh đ−ợc xn = n∑ k=0 S(n, k)Akx. Do đó L(xn) = n∑ k=0 S(n, k)L((x)k) = n∑ r=0 S(n, k) = Bn. Ta có (x)n+1 = x(x− 1) . . . (x− n) = x(x− 1)n. Suy ra L((x)n+1) = L((x)n) = L(x(x− 1)n). Do đó L(p(x)) = L((x)n) = L(xP (x − 1)) với mọi P (x). Bây giờ ta cho P (x) = (x + 1)n, ta đ−ợc L((x + 1)n) = L(xn+1), hay n∑ k=0 CknL(x k) = Bn+1. Nh− vậy, n∑ k=0 CknBk = Bn+1. 1.3.2 Ví dụ. B5 = C04B0 + C 1 4B1 + C 2 4B2 + C 3 4B3 + C 4 4B4 = 1 + 4 + 12 + 20 + 15 = 52 B10 = C 0 9B0 + C 1 9B1 + C 2 9B2 + C 3 9B3 + C 4 9B4 + C 5 9B5 + C 6 9B6 + C 7 9B7 + C89B8 + C 9 9B9= 1+9+72+420+1890+6552+17052+31572+37260+21147 = 115975 19 Sau đây ta sẽ đ−a ra tam giác Bell để tính số phân hoạch của tập hợp gồm n phần tử với n nhận những giá trị đầu tiên là 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Đây là kết quả tổng hợp của những định lí, mệnh đề ở trên. Tr−ớc hết ta mô tả cách xây dựng tam giác Bell qua chú ý sau đây. 1.3.3 Chú ý. Các số Bell có thể tính dễ dàng bằng cách xây dựng tam giác Bell, còn đ−ợc gọi là dãy Aitken hoặc tam giác Pierce. Ta có thể mô tả cách xây dựng tam giác Bell nh− sau: Bắt đầu với số 1 và đặt số này trên dòng thứ nhất. Tạo một dòng mới bằng cách lấy phần tử bên phải của dòng ngay trên nó làm phần tử đầu tiên bên trái của dòng mới. Lần l−ợt các số tiếp theo của dòng mới bằng cách lấy tổng phần tử bên trái nó với phần tử đứng cùng cột phần tử ấy ở dòng tr−ớc nó. Tiếp tục b−ớc ba cho đến khi số phần tử của dòng mới nhiều hơn số phần tử của dòng trên một phần tử. Số nằm phía phải mỗi dòng là số Bell cho mỗi dòng. Cụ thể tam giác Bell cũng có qui luật thiết lập cụ thể, có nét t−ơng tự nh− qui luật thiết lập tam giác Pascal của các số tổ hợp. Hàng đầu tiên là chữ số 1, đây là số Bell đầu tiên. Với mọi i ≥ 1 hàng thứ i + 1 đ−ợc điền theo nguyên tắc sau đây: Chữ số cuối cùng của hàng thứ i đ−ợc đặt lên đầu hàng thứ i + 1. Với mọi j > 1 số thứ j của hàng i + 1 là tổng của số thứ j − 1 của hàng i + 1 và số thứ j − 1 của hàng i. Số cuối cùng của hàng i + 1 là số Bell của hàng đó. 20 Tr−ớc hết ta có bảng tính các số S(n, k), tức là các số Stirling loại 2. S(n, k) 1 2 3 4 5 6 7 8 9 10 Bn n = 1 1 1 n = 2 1 1 2 n = 3 1 3 1 5 n = 4 1 7 6 1 15 n = 5 1 15 25 10 1 52 n = 6 1 31 90 65 15 1 203 n = 7 1 63 301 350 140 21 1 877 n = 8 1 127 966 1701 1050 266 28 1 4140 n = 9 1 255 3025 7770 6951 2646 462 36 1 21147 n = 10 1 511 9330 34105 42525 22827 5880 750 45 1 115975 Tiếp theo, chúng ta đ−a ra bảng tám giác tính số Bell Bn, tức là số phân hoạch tập hợp n phần tử. Trong bảng này, dòng đầu tiên là số Bell ứng với n = 1, cuối dòng thứ 2 là số Bell ứng với n = 2. Cứ tiếp tục nh− thế, số cuối nằm trong mỗi dòng là số Bell ứng với số n của dòng đó. Chẳng hạn ở dòng thứ 9 thì số Bell là B9 = 21147. n = 1 1 n = 2 1 2 n = 3 2 3 5 n = 4 5 7 10 15 n = 5 15 20 27 37 52 n = 6 52 67 87 114 151 203 n = 7 203 255 322 409 523 674 877 n = 8 877 1080 1335 1657 2066 2589 3263 4140 n = 9 4140 5017 6097 7432 9089 11155 13744 17007 21147 1.3.4 Chú ý. (i) Chúng ta hoàn toàn có thể phát triển tam giác Bell với số tự nhiên n lớn hơn nữa, đây là một −u điểm rất lớn để tính số phân hoạch của tập hợp có nhiều phân tử. 21 (ii) Một số nguyên tố Bell là một số Bell đồng thời là một số nguyên tố. Các số nguyên tố Bell đầu tiên là 2, 5, 27644437, 35742549198872617291353508656626642567, 3593340855968622831041960188598043661065388726959079837. Các số nguyên tố Bell ở trên t−ơng ứng là các số Bell thứ 2, 3, 7, 13, 42, 55. Số nguyên tố Bell tiếp theo là B2841 xấp xỉ với 93074106538. Đến năm 2005, số nguyên tố Bell lớn nhất đã biết là B2841. Năm 2002, PhilCarmody phát biểu rằng B2841 là số nguyên tố. Gần hai năm sau, Ignacio Larrosa Canestro đã chứng minh đ−ợc B2841 là số nguyên tố. Ch−ơng 2 Một số ứng dụng trong toán sơ cấp Trong ch−ơng này, ta xem xét một số ứng dụng của lý thuyết phân hoạch trên một số lĩnh vực của toán học, chẳng hạn nh− đại số tổ hợp hay xác suất thống kê, đặc biệt thấy đ−ợc ứng dụng của phép phân hoạch tập hợp trong hình học sơ cấp. 2.1 Phân hoạch chẵn, lẻ và ứng dụng trong toán sơ cấp Cho X là tập có n phần tử. Một phân hoạch tập hợp X đ−ợc gọi là phân hoạch có điều kiện nếu ta gắn một điều kiện nào đó trên các tập con trong phân hoạch. Sau đây ta sẽ xét hai loại phân hoạch đặc biệt, đó là phân hoạch chẵn và phân hoạch lẻ. 2.1.1 Định nghĩa. Một phân hoạch tập hợp X đ−ợc gọi là phân hoạch chẵn nếu mỗi tập con trong phân hoạch có số phần tử là số chẵn. Một phân hoạch tập hợp X đ−ợc gọi là phân hoạch lẻ nếu mỗi tập con trong phân hoạch có số lẻ phần tử. 2.1.2 Kí hiệu. Với tập X có n phần tử ta kí hiệu: (i) E(n, k) là số phân hoạch tập X thành k tập con sao cho mỗi tập con có chẵn phần tử. (ii) O(n, k) là số phân hoạch tập X thành k tập con sao cho mỗi tập con 22 23 có một số lẻ phần tử. (iii) En là số phân hoạch tập X thành các tập con gồm chẵn phần tử. (iv) On là số phân hoạch tập X thành các tập con gồm lẻ phần tử. 2.1.3 Chú ý. Ta có En = n∑ k=0 E(n, k) và On = n∑ k=0 O(n, k). 2.1.4 Mệnh đề. Với m, n là các số nguyên d−ơng, ta có các đẳng thức sau: (i) E(2m, 2) = 22m−2 − 1; (ii) E(2m,m) = (2m)! m!2m ; (iii) O(2n, 2) = 22n−2; (iv) O(n, n− 2) = C3n = n(n− 1)(n− 2) 6 , n ≥ 4. Chứng minh. (i) Gọi A là tập các phân hoạch một tập X gồm 2m phần tử thành các tập con có số chẵn phần tử. Để tạo ra một phân hoạch trong A, đầu tiên là chọn 2j phần tử từ 2m phần tử cho tập con thứ nhất, có C2j2m cách chọn 2j nh− thế. Sau đó chọn 2m−2j phần tử còn lại cho tập con thứ hai, có đúng 1 cách chọn. Do j có thể nhận các giá trị 1, 2, 3, . . . ,m − 1 và số cách chọn ứng với mỗi j tính 2 lần nên ta có công thức E(2m, 2) = 1 2 m−1∑ j=1 C2j2m = 1 2 (C22m + C 4 2m + . . . + C 2m−2 2m ). Khai triển nhị thức (1 + x)2m sau đó cho x = 1, x = −1 ta nhận đ−ợc 22m = (1 + 1)2m = C02m + C 1 2m + C 2 2m + C 3 2m + C 4 2m + . . . + C 2m−1 2m + C 2m 2m ; 02m = (1− 1)2m = C02m −C 1 2m + C 2 2m − C 3 2m + C 4 2m + . . .− C 2m−1 2m + C 2m 2m . Cộng từng vế các đẳng thức trên ta nhận đ−ợc 22m = 2C0m + 2(C 2 2m + C 4 2m + . . . + C 2m−2 2m ) + 2C 2m 2m . Khi đó E(2m, 2) = 22m−2 − 1. (ii) Khi phân hoạch tập hợp gồm 2m thành m tập con không rỗng mà mỗi 24 tập con gồm số chẵn phần tử thì số phần tử trong mỗi tập con là 2. Đầu tiên ta chọn 2 phần tử cho tập hợp con thứ nhất thì có C22m cách chọn, sau đó chọn tiếp 2 phần tử cho tập con thứ 2 từ 2m− 2 phần tử còn lại thì có C22m−2 cách chọn. Cứ nh− thế đến khi ta chọn 2 phần tử còn lại cho tập con cuối cùng thì có C22 cách chọn. Theo qui tắc nhân và phân hoạch không có tính thứ tự các tập hợp con trong phân hoạch nên ta có E(2m,m) = 1 m! C22mC 2 2m−2 . . . C 2 4C 2 2 ; E(2m,m) = 1 m! (2m)! 2!(2m− 2)! (2m− 2)! 2!(2m− 4)! . . . 4! 2!2! 2! 2! = (2m)! m!2m . (iii) Mỗi cách phân hoạch tập hợp gồm 2n phần tử thành 2 tập con không rỗng gồm hai b−ớc sau: Đầu tiên là chọn 2j − 1 phần tử từ 2n phần tử cho tập hợp thứ nhất có C2j−12n cách. Sau đó chọn 2n + 1− 2j phần tử còn lại cho tập hợp thứ hai có 1 cách. Do j có thể nhận các giá trị 1, 2, 3, . . . , n và số cách chọn ứng với mỗi j tính 2 lần nên ta có công thức O(2n, 2) = 1 2 n∑ j=1 C2j−12n = 1 2 (C12n + C 3 2m + . . . + C 2n−1 2n . Khai triển nhị thức (1 + x)2n sau đó cho x = 1, x = −1 ta nhận đ−ợc 22n = (1 + 1)2n = C02n + C 1 2n + C 2 2n + C 3 2n + C 4 2n + C 5 2n + . . . + C 2n−1 2n + C 2n 2n ; 02n = (1− 1)2n = C02n − C 1 2n + C 2 2n − C 3 2n + C 4 2n −C 5 2n + . . .− C 2n−1 2n + C 2n 2n . Cộng từng vế các đẳng thức trên ta nhận đ−ợc O(2n, 2) = 22n−2. (iv) Khi phân hoạch tập hợp gồm n phần tử thành n−2 tập con không rỗng mà mỗi tập con gồm một số lẻ phần tử thì sẽ có một tập có 3 phần tử và n − 3 tập còn lại mỗi tập có một phần tử. Có C3n cách chọn 3 phần tử để tạo thành một tập có 3 phần tử. Có duy nhất một cách phân hoạch n − 3 phần tử để tạo thành n− 3 tập không rỗng, mỗi tập có một phần tử. Do đó 25 theo qui tắc nhân, ta có O(n, n− 2) = C3n = n(n− 1)(n− 2) 6 với n ≥ 4. Từ Mệnh đề 2.1.4, ta có bảng sau để tính các số E(n, k) và O(n, k) với những n nhỏ. O(n, k) k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 On n = 1 1 1 n = 2 0 1 1 n = 3 1 0 1 2 n = 4 4 0 0 1 5 n = 5 1 0 10 0 1 12 n = 6 1 16 0 20 0 1 37 n = 7 1 0 91 0 35 0 1 128 n = 8 0 64 0 366 0 56 0 1 457 E(n, k) k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 En n = 1 0 0 n = 2 1 0 1 n = 3 0 0 0 0 n = 4 1 3 0 0 4 n = 5 0 0 0 0 0 0 n = 6 1 15 15 0 0 0 31 n = 7 0 0 0 0 0 0 0 0 n = 8 1 63 210 105 0 0 0 0 379 2.1.5 Ví dụ. Có 20 vận động viên trong một cuộc thi đấu cầu lông. Ban tổ chức cần chia các vận động viên thành 10 cặp thi đấu. Số cách chia là số phân hoạch tập hợp 20 phần tử thành 10 tập con mà mỗi tập con gồm đúng 2 phần tử. Số cách là E(20, 10) = 654729685. 26 2.1.6 Ví dụ. Tại vòng chung kết Worldcup thế giới diễn ra tại Brazil năm 2014, Ban tổ chức chọn đ−ợc 16 đội bóng vào đấu loại trực tiếp. Các đội bóng sẽ tham gia bốc thăm để chia thành 8 cặp đấu. Hai đội thuộc 1 cặp sẽ thi đấu để chọn ra đội thắng vào tứ kết. Khi đó, số khả năng phân chia cặp đấu là số phân hoạch tập hợp gồm 16 phần tử thành 8 tập con không rỗng mà mỗi tập con gồm đúng 2 phần tử. Số đó là E(16, 8) = 2027025. T−ơng tự số cách chia 8 đội thắng thành 4 cặp đấu cho vòng tứ kết là E(8, 4) = 105, và số cách chia 4 đội thắng cho vòng bán kết là E(4, 2) = 3. Bây giờ ta sử dụng các công thức trên để giải một số bài toán sơ cấp. 2.1.7 Bài toán. Phân phối n quả cầu phân biệt vào m hộp giống nhau. Có bao nhiêu cách phân phối sao cho mỗi hộp có chẵn quả cầu và bao nhiêu cách phân phối sao cho mỗi hộp có lẻ quả cầu. Lời giải. Vì các quả cầu là phân biệt nhau và các hộp là giống nhau nên số cách phân phối để mỗi hộp có một số chẵn (lẻ) phần tử bằng số cách phân hoạch tập hợp gồm n phần tử thành m tập con sao cho mỗi tập có số chẵn (lẻ) quả cầu. Do đó số cách phân phối sao cho mỗi hộp có chứa một số chẵn quả cầu bằng E(n,m) cách và số cách phân phối sao cho mỗi hộp có chứa số một số lẻ quả cầu bằng O(n,m) cách. 2.1.8 Bài toán. Có bao nhiêu cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp chứa một số chẵn đồ vật. Có bao nhiêu cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp chứa một số lẻ đồ vật. Lời giải. Vì các đồ vật là khác nhau và các hộp là giống nhau nên số cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp có một số chẵn đồ vật bằng số phân hoạch tập hợp5 phần tử phân biệt thành 3 tập 27 con sao cho mỗi tập con có chứa một số chẵn phần tử và bằng E(5, 3) = 0. T−ơng tự số cách phân phối 5 đồ vật khác nhau vào 3 hộp giống nhau sao cho mỗi hộp có một số lẻ đồ vật bằng O(5, 3) = 10. 2.2 Một số ứng dụng giải toán tổ hợp và hình học sơ cấp Nh− trong Định nghĩa 1.2.2, số phân hoạch tập X gồm n phần tử thành k khối đ−ợc kí hiệu là S(n, k) và đ−ợc gọi là số Stirling loại 2. Nh− vậy S(n, k) chính là số cách phân phối n quả cầu phân biệt vào k hộp giống nhau mà không có hộp nào rỗng. Chẳng hạn, số cách phân phối 10 quả cầu phân biệt vào 5 hộp giống nhau mà không có hộp nào rỗng là S(10, 5) = 52525. 2.2.1 Bài toán. Có bao nhiêu cách phân phối 2015 quả cầu phân biệt vào 100 hộp phân biệt. Lời giải. Giả sử các hộp giống nhau. Khi đó phân phối 2015 quả cầu phân biệt vào 100 hộp giống nhau chính là số phân hoạch một tập hợp gồm 2015 phần tử thành 100 khối, đó là S(2015, 100). Với mỗi cách phân phối 2015 quả cầu vào 100 hộp giống nhau, bằng cách hoán vị 100 hộp ta sẽ đ−ợc 100! phân phối 2015 quả cầu vào 100 hộp phân biệt. Do đó số cách phân phối 2015 quả cầu phân biệt vào 100 hộp phân biệt là 100! x S(2015, 100). 2.2.2 Bài toán. Phân phối n quả cầu phân biệt vào k hộp phân biệt. Có bao nhiêu cách phân phối sao cho mỗi hộp chứa một số chẵn quả cầu và có bao nhiêu cách phân phối sao cho mỗi hộp chứa một số lẻ quả cầu. Lời giải. Giả sử các hộp giống nhau. Số cách phân phối sao cho mỗi hộp chứa một số chẵn quả cầu là E(n, k) và số cách phân phối sao cho mỗi hộp chứa một số lẻ quả cầu là O(n, k). Với mỗi cách phân phối vào k hộp giống nhau, bằng cách hoán vị k hộp, ta đ−ợc một phân phối vào k hộp 28 khác nhau. Do đó số cách phân phối n quả cầu phân biệt vào k hộp phân biệt sao cho mỗi hộp chứa một số chẵn quả cầu là k! x E(n, k) và số cách phân phối n quả cầu phân biệt vào k hộp phân biệt sao cho mỗi hộp chứa một số lẻ quả cầu là k! x O(n, k). 2.2.3 Bài toán. Tính số nghiệm nguyên không âm của ph−ơng trình x1 + x2 + x3 + . . . + xk = n. Lời giải. Xét dãy có độ dài là n + k − 1 bao gồm n phần tử x và k − 1 số 0 nh− sau x . . . x︸ ︷︷ ︸ x1 0x . . . x︸ ︷︷ ︸ x2 0 . . . x . . . x︸ ︷︷ ︸ xk , trong đó x1 +x2 +x3 + . . .+xk = n và xi > 0 với mọi i ∈ {1, 2, 3, . . . , k}. Nhận xét rằng có 1 song ánh từ tập các nghiệm nguyên d−ơng của ph−ơng trình đã cho vào tập các dãy dạng x1, . . . , xk thỏa mãn điều kiện trên. Mặt khác, số các dãy có dạng trên t−ơng ứng với số cách chọn k−1 vị trí cho số 0, là tập con gồm k−1 phần tử của tập hợp gồm n−1 phần tử. Do đó số các dãy dạng thỏa mãn điều kiện trên là Ck−1n−1 . Vì thế số nghiệm nguyên d−ơng của ph−ơng trình là Ck−1n−1 . Nhận xét rằng nếu x1 + x2 + x3 + . . . + xk = n và xi ≥ 0 với i ∈ {1, 2, 3, . . . k} thì (x1 + 1) + (x2 + 1) + . . . + (xk + 1) = n + k với xi+1 > 0 và i ∈ {1, 2, 3, . . . k}. Đảo lại, nếu y1+y2+y3+. . .+yk = n+k và yi > 0 với mọi i ∈ {1, 2, 3, . . . k} thì (y1 − 1) + (y2 − 1) + . . . + (yk − 1) = n với yi ≥ 0 và i ∈ {1, 2, 3, . . . k}. Do đó số nghiệm nguyên không âm của ph−ơng trình là Ck−1n+k−1 = C n n+k−1. 29 2.2.4 Bài toán. Chọn ngẫu nhiên một số tự nhiên có 3 chữ số. Tính xác suất để chọn đ−ợc một số có tổng các chữ số chia hết cho 10. Lời giải. Gọi số cần lập có dạng abc thỏa mãn a 6= 0 và a, b, c ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Số có 3 chữ số tùy ý là 9 x 102 = 900 số. Nhận xét rằng số nghiệm không âm của ph−ơng trình a + b + c = n là C2n+2. Theo giả thiết, ta có 2 tr−ờng hợp sau đây. Tr−ờng hợp 1: a + b + c = 10. Khi đó số nghiệm nguyên không âm với a, b, c tùy ý là C212. Số nghiệm a, b, c thỏa mãn a = 0, 0 6 b, c 6 9 và b, c ∈ N là C111. Số nghiệm a, b, c thỏa mãn a = 10, b = c = 0 là 1. Kết hợp lại, tr−ờng hợp này có C212 − C 1 11 − 1 = C 2 11 − 1 số thỏa mãn yêu cầu bài toán. Tr−ờng hợp 2: a + b + c = 20. Đặt a = 9 − x, b = 9 − y, c = 9− z. Khi đó, ta có x, y, z ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} và x + y + z = 7, x 6= 9. Số nghiệm x, y, z thỏa mãn là C29 và các số thỏa mãn tr−ờng hợp này là C29 . Tóm lại số các số thỏa mãn yêu cầu bài toán là C211 + C 2 9 − 1 = 90. Vì vậy, xác suất cần tìm là P = 90 900 = 1 10 . 2.2.5 Bài toán. Chọn ngẫu nhiên một số tự nhiên có 3 chữ số. Tính xác suất để chọn đ−ợc một số có tổng các chữ số chia hết cho 9. Lời giải. Gọi số cần lập có dạng abc thỏa mãn a 6= 0 và a, b, c ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. 30 Số có 3 chữ số tùy ý là 9 x 102 = 900 số. Nhận xét rằng số nghiệm không âm của ph−ơng trình a + b + c = n là C2n+2. Theo giả thiết ta có 3 tr−ờng hợp sau đây. Tr−ờng hợp 1: a+ b+ c = 9, khi đó số nghiệm nguyên không âm với a, b, c tùy ý là C211. Số nghiệm a, b, c thỏa mãn a = 0, 0 6 b, c 6 9 và b, c ∈ N là C110. Kết hợp lại, tr−ờng hợp này có C 2 11 −C 1 10 = C 2 10 số thỏa mãn yêu cầu bài toán. Tr−ờng hợp 2: a + b + c = 18. Đặt a = 9 − x, b = 9 − y, c = 9− z. Khi đó, ta có x, y, z ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} và x + y + z = 9, x khác 9. Vì thế số nghiệm x, y, z thỏa mãn là C211 − 1, do đó số các số thỏa mãn tr−ờng hợp này là C211 − 1. Tr−ờng hợp 3: a + b + c = 27, khi đó a = 9, b = 9, c = 9 nên có 1 số thỏa mãn tr−ờng hợp này. Tóm lại số các số thỏa mãn yêu cầu bài toán là C210+C 2 11−1+1 = 100. Xác suất cần tìm là P = 90 900 =