Phan Hoach

Mọi thứ đều là những con số “Số 1 là con số thần thánh tạo nên tất cả các con số bởi vì tất cả các số tự nhiên đều là tổng của hữu hạn các số 1. Số 2, số chẵn đầu tiên, được coi là số thuộc giới nữ và thể hiện sự đa dạng của các ý kiến. Số thuộc giới nam đầu tiên là số 3, nó thể hiện sự điều hòa bởi nó là tổng của 1 và 2. Số 4 tượng trưng cho sự công bằng. Số 5 được gắn với hôn nhân vì nó là tổng của số 2 và 3. Cứ tiếp tục như thế các con số được gắn với con người như thân thiện, hoàn hảo, dư giả, tự phụ…” (Theo Theoni Pappas) Phân hoạch là các thể hiện các con số và mở rộng hơn đối với tập hợp là việc phân tích chúng. Tìm hiểu về phân hoạch là tìm hiểu về ý nghĩa của từng con số. Phân hoạch có thể thấy từ rất nhiều hiện tượng trong cuộc sống, lấy một ví dụ đơn giản về sự phân rã của nguyên tử: nguyên tử phân rã thành các cụm hạt nhỏ hơn nhưng tổng khối lượng của chúng thì vẫn bằng ban đầu, các cụm hạt như vậy lại tiếp tục phân rã nhỏ hơn nữa cho tới khi chỉ là những đơn vị nhỏ nhất là các hạt như proton … 1. Phân hoạch tập hợp: Phân hoạch tập hợp n phần tử {1, 2, 3, …, n} là phân tập này thành các tập con khác rỗng. Ví dụ phân hoạch tập hợp {1, 2, 3, 4} có 15 cách như sau: {1,2,3,4} - {{1,2,3},{4}} - {{1,2,4},{3}} - {{1,2},{3,4}} - {{1,2},{3},{4}} - {{1,3,4},{2}} {{1,3},{2,4}} - {{1,3},{2},{4}} - {{1,4},{2,3}} - {{1},{2,3,4}} - {{1},{2,3},{4}} - {{1,4},{2},{3}} {{1},{2,4},{3}} - {{1},{2},{3,4}} - {{1},{2},{3},{4}}. 1.1. Số Stirling: Số Stirling xuất hiện nhiều trong các bài toán tổ hợp và gồm 2 loại là số Stirling loại một và số Stirling loại hai. 1.1.1. Số Stirling loại một: 1.1.1.1. Hoán vị vòng quanh: Định nghĩa số 1 về hoán vị vòng tròn: Mỗi hoán vị σ trên tập S gồm k phần tử được gọi là một hoán vị vòng tròn với độ lệch t khi và chỉ khi có thể sắp các phần tử của tập S theo thứ tự x1 < x2 < ··· < xk sao cho: σ(xi) = xi+t, ∀i = 1,2,...,k−t; σ(xi) = xi+t−k, ∀i = k−t + 1,k−t + 2,...,k.  Ví dụ: σ = ( 1234567 8 ) 34576182 Ta có thể sắp lại hoán vị này theo thứ tự sau: σ = ( 12345768 ) 34576812 Tức là ta sử dụng thứ tự x6 = 7,x7 = 6 và xi = i,∀ i ≠ 6,7. Ta thấy hoán vị này là hoán vị vòng tròn với độ lệch t = 2 như sơ đồ sau: 1 ↑ 6 → ← 3 ↓ 5 2 → ↑ 8 ← 4 ↓ 7 Ta có: σ(x1) = σ(1) = 3 = x3 σ(x2) = σ(2) = 4 = x4 σ(x3) = σ(3) = 5 = x5 σ(x4) = σ(4) = 7 = x6 σ(x5) = σ(5) = 6 = x7 σ(x6) = σ(7) = 8 = x8 và σ(x7) = σ(6) = 1 = x1 σ(x8) = σ(8) = 2 = x2 Ta có hai chu trình kí hiệu là (1356) và (2478). Chú ý: Nếu σ là một hoán vị vòng tròn với độ lệch t thì nó có thể được xây dựng với đúng s chu trình có độ dài bằng nhau, trong đó s là ước chung lớn nhất của k và t. Định nghĩa số 2 về hoán vị vòng tròn: Một hoán vị được gọi là hoán vị vòng tròn khi và chỉ khi nó có thể được xây dựng với chỉ một chu trình. Theo định nghĩa này thì mỗi hoán vị vòng tròn thỏa mãn định nghĩa số 1 và ước chung lớn nhất của k và t là 1. Ví dụ: σ = ( 1234567 8 ) 45768213 Hoán vị này có chu trình duy nhất là (14625837).  1 ↑ 7 → 4 → 6 → 2 ↓ 8 ← 5 ← 3 ← Định nghĩa 3 về hoán vị vòng tròn: Một hoán vị được gọi là hoán vị vòng tròn khi và chỉ khi chỉ nó chỉ có một chu trình có độ dài lớn hơn 1. Ví dụ, hoán vị sau là một hoán vị vòng tròn: σ = ( 1234567 8 ) 42765813 Hoán vị này có các chu trình (146837)(2)(5). 1 ↑ 7 → 4 ← 3 → 6 ↓ ← 8 1.1.1.2. Định nghĩa: n Các số Stirling (không dấu) loại một, kí hiệu bởi [ ] hoặc |s(n,k)| hoặc s’(n,k), là số hoán k vị của n phần tử với k chu trình rời nhau. Ví dụ, với n = 3, ta có 6 hoán vị, trong đó có:  Một hoán vị với ba chu trình là 123 = (1)(2)(3);  Ba hoán vị với hai chu trình là 132 = (1)(23), 213 = (3)(12), 321 = (2)(13);  Hai hoán vị với một chu trình là 312 = (123), 231 = (132). 3 3 3 Do đó: [ ] = 1, [ ] = 3, [ ] = 2. 1 2 3 Một số hình ảnh minh họa số Stirling loại một với n=4:  Các số Stirling loại một là các hệ số trong khai triển “giai thừa tăng” như sau: 𝑛 n [ ] 𝑥𝑘 𝑘=0 𝑘 x (n) = 𝑥 (𝑥 + 1)(𝑥 + 2). . . (𝑥 + 𝑛 − 1) = ∑ Ví dụ: x (3) = 𝑥 (𝑥 + 1)(𝑥 + 2) = 1. 𝑥 + 3. 𝑥 2 + 1. 𝑥 3 . 1.1.1.3. Công thức: Công thức truy hồi của các số Stirling loại một: n n n+1 [ ] = 𝑛. [ ] + [ ] 𝑘 𝑘 − 1 𝑘 n 0 0 Điều kiện ban đầu là: k>0 và [ ] = 1, [ ] = [ ] = 0. 0 0 𝑛 Ta có thể chứng minh như sau:  Xét việc lập một hoán vị của n + 1 phần tử từ n phần tử bằng cách thêm vào một phần tử sao cho hoán vị đó có k chu trình. Có hai cách lập:  Lập một chu trình đơn chỉ gồm phần tử mới thêm vào. Khi đó còn lại k − 1 chu n ] chu trình. trình lập từ n phần tử, có [ 𝑘−1  Chèn phần tử mới đó vào một trong các chu trình đã có. Xét hoán vị bất kì của n phần tử a1 a2 ···an trong đó có k chu trình: (𝑎 ⏟ 1 , … , 𝑎𝑗1 )(𝑎𝑗1+1 , … 𝑎𝑗2 ) … (𝑎𝑗𝑘−1+1 , … , 𝑎𝑛 ) 𝑘 𝑐ℎ𝑢 𝑡𝑟ì𝑛ℎ  Để lập một hoán vị mới của n + 1 phần tử với k chu trình, ta cần chèn phần tử mới đó vào một trong k chu trình này. Có n cách chèn phần tử mới vào trong dãy n n phần tử đó. Từ đó có 𝑛. [ ] cách. 𝑘  Tổng của hai giá trị ứng với hai khả năng trên cho ta kết quả cần chứng minh. 1.1.2. Số Stirling loại hai: 1.1.2.1. Định nghĩa : Các số Stirling loại hai đếm số cách phân hoạch của một tập thành k tập con khác rỗng. 𝑛 Số này thường được kí hiệu là { } hoặc S(n,k). 𝑘 Một số hình ảnh minh họa số Stirling loại hai: 4 Số Stirling loại hai { }: 𝑘 1.1.2.2. Công thức: Công thức của số Stirling loại hai: 𝑘 1 𝑛 𝑘 { } = ∑ (−1)𝑘−𝑗 ( ) 𝑗 𝑛 𝑘 𝑗 k! 𝑗=0 Công thức truy hồi của số Stirling loại hai:  { 𝑛 𝑛 𝑛+1 } = 𝑘. { } + { } 𝑘 𝑘−1 𝑘 𝑛 0 0 Điều kiện ban đầu: k>0 và { } = 1, { } = { } = 0. 0 0 𝑛 Ta có thể chứng minh công thức này bằng lập luận như sau:  Mỗi phân hoạch của tập n + 1 phần tử thành k tập con khác rỗng có hai khả năng, hoặc tập con chứa n + 1 hoặc không chứa. 𝑛  Số cách phân hoạch trong đó có tập con chứa n + 1 là { } vì ta phân hoạch n 𝑘−1 phần tử còn lại thành k−1 tập con. 𝑛  Số cách phân hoạch trong đó không chứa tập con n + 1 là 𝑘. { } vì ta phân hoạch 𝑘 mọi phần tử khác n + 1 thành k tập con và sau đó có k cách để chèn phần tử n+ 1 vào một trong các tập con này. 1.2. Số Bell: 1.2.1. Định nghĩa: Số Bell thứ n là số cách phân hoạch tập n phần tử, hay nói cách khác đây cũng là mối quan hệ tương đương xác định trên tập này. Một vài số Bell đầu tiên: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975... Gọi Bn là số Bell thứ n. Với n = 3, và tập S = {1, 2, 3}, ta có B3 = 5 vì có 5 cách phân hoạch: {{1}, {2}, {3}} {{1, 2}, {3}} {{1, 3}, {2}} {{1}, {2, 3}} {{1, 2, 3}}. Dưới đây là một số hình ảnh minh họa số cách phân tích số Bell dưới dạng lược đồ: Hình bao quanh biểu diễn tập, mỗi đường nối một điểm với nhau thể hiện các tập con: Tập {1, 2, 3}, có 5 phân hoạch:  Tập {1, 2, 3, 4}, có 15 phân hoạch: Tập {1, 2, 3, 4, 5}, có 52 phân hoạch: 1.2.2. Công thức truy hồi: Số Bell là tổng tất cả của những số Stirling loại hai: 𝑛 𝐵𝑛 = ∑ 𝑘=0 (𝑘) 𝑛 𝑘 1 𝑘 ∑ (−1)𝑘−𝑗 ( ) 𝑗 𝑛 𝑗 𝑘=0 k! 𝑗=0 𝑆𝑛 = ∑ Công thức truy hồi của số Bell: 𝑛 𝑛 ( ) 𝐵𝑘 𝑘=0 𝑘 𝐵𝑛+1 = ∑ Điều kiện ban đầu là B0 = 1.  Ta có thể chứng minh công thức này bằng lập luận như sau:  Bn+1 là số cách phân hoạch tập S = {1, 2, ..., n, n + 1}. Mỗi phân hoạch đều có một tập A nào đó chứa phần tử n + 1.  Bn+1 chính là số cách phân hoạch tập S trong đó có chứa tập A và số cách phân hoạch tập S \ A.  Tập S \ A có thể có k chạy từ 0 tới n, tương ứng với các trường hợp A ≡ S hoặc A ≡ {n + 1}. 𝑛  Với mỗi k ta có ( ) cách chọn tập con k phần tử của tập S \ A và Bk cách phân 𝑘 hoạch tập con đó nên ta có công thức trên. Các số Bell cũng thỏa mãn công thức Dobinski: 1 ∞ 𝑘𝑛 𝐵𝑛 = ∑ 𝑒 𝑘=1 𝑘! Tam giác Bell: Tam giác này được xây dựng như sau:  Hàng đầu tiên là số 1 – số Bell đầu tiên.  Hàng thứ i với i lớn hơn 1, số đầu tiên sẽ là số cuối cùng của hàng i-1. Các số tiếp theo bằng tổng của số liền trước nó và số ngay trên số trước nó.  Số cuối cùng là số Bell thứ i.  2. Phân hoạch số nguyên: Phân hoạch số nguyên là phân tích số nguyên dương n thành các số nguyên dương có tổng bằng n. Hai tổng nếu chỉ khác nhau bởi thứ tự các số hạng thì được coi là như nhau. Ví dụ, n=4 có những cách sau: 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1. 2.1. Phân hoạch hạn chế: 2.1.1. Định nghĩa: Phân hoạch số nguyên hạn chế là phân hoạch số nguyên nhưng có rằng buộc nhất định, chẳng hạn các số đều phải là số chẵn hoặc lẻ, nhỏ hơn số k, các số hạng phải khác nhau… Ví dụ: Trong số 22 phân hoạch của số 8, chỉ có sáu phân hoạch chứa các số hạng lẻ: 8=7+1 =5+3 =5+1+1+1 =3+3+1+1 =3+1+1+1+1+1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1. Cũng có 6 phân hoạch của số 8 trong đó các số hạng phân biệt: 8=8 =7+1