Số Bell

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

Trong lý thuyết tổ hợp của toán học, số Bell thứ n (gọi theo tên của Bell, là số các phân hoạch của tập với n phần tử, hay cũng vậy, số các quan hệ tương đương trên tập ấy. Bắt đầu với B0 = B1 = 1, các số Bell đầu tiên là (dãy số A000110 trong bảng OEIS):

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975

Phân hoạch của một tập hợp[sửa | sửa mã nguồn]

Tổng quát, Bn là số các phân hoạch của tập hợp kích thước n. Phân hoạch của tập S là một họ các tập con không rỗng, rời nhau mà hợp của chúng bằng S.

Chẳng hạn, B3 = 5 vì tập hợp ba phần tử {abc} có thể phân hoạch theo 5 cách khác nhau:

Bản mẫu:''a'', {b}, Bản mẫu:''c''
Bản mẫu:''a'', Bản mẫu:''b'', ''c''
Bản mẫu:''b'', Bản mẫu:''a'', ''c''
Bản mẫu:''c'', Bản mẫu:''a'', ''b''
Bản mẫu:''a'', ''b'', ''c''}

B0 là 1 vì có đúng một phân hoạch của tập rỗng. Đây là trường hợp đặc biệt, đối với n >0 sẽ không xét tập con rỗng.

Chú ý rằng, trong mệnh đề trên chúng ta không phân biệt các thành phần của một phân hoạch. Như vậy các cách viết sau chỉ cùng một phân hoạch:

Bản mẫu:''b'', Bản mẫu:''a'', ''c''
Bản mẫu:''a'', ''c'', Bản mẫu:''b''
Bản mẫu:''b'', Bản mẫu:''c'', ''a''
Bản mẫu:''c'', ''a'', Bản mẫu:''b''

Các ý nghĩa khác của các số Bell[sửa | sửa mã nguồn]

Các số Bell cũng có thể xem như số các khả năng khác nhau đặt n quả bóng vào một hoặc nhiều hộp. Chẳng hạn với n = 3, ta có ba quả bóng được ghi nhãn a, b, and c, và ba hộp. Nếu không phân biệt thứ tự các hộp ta có năm cách phân phối:

  • Mỗi quả bóng vào một hộp
  • Tất cả ba quả bóng vào một hộp.
  • a vào một hộp; bc vào một hộp khác.
  • b vào một hộp; ac vào một hộp khác.
  • c vào một hộp; ba vào một hộp khác.

Tính chất của các số Bell[sửa | sửa mã nguồn]

Công thức truy hồi:

Chúng thoả mãn "Công thức Dobinski":

là momen thứ n của phân phối Poisson với kỳ vọng bằng 1.

Chúng thoả mãn tính chất "đồng dạng Touchard": Nếu psố nguyên tố bất kỳ thì

Mỗi số Bell là tổng của các "số Stirling hạng hai"

Số Stirling S(n, k) là số các phân hoạch tập hợp n phần tử thành đúng k tập con không rỗng.

Số Bell thứ n cũng là tổng các hệ số trong đa thức có biểu thức của momen thứ n của phân phối xác suất bất kỳ như một hàm của n tích luỹ đầu tiên.

Chuỗi hàm luỹ thừa của các số Bell là

Công thức tiệm cận[sửa | sửa mã nguồn]

Công thức tiệm cận của các số Bell là

Trong đó , Whàm Lambert W.

(Lovász, 1993)

Lược đồ tam giác của các số Bell[sửa | sửa mã nguồn]

Các số Bell có thể dễ dàng tính 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 Peirce:

  1. Bắt đầu với số một. Đặt số này trên dòng thứ nhất.
  2. Tạo một dòng mới bằng việc lấy phầh tử cực 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
  3. Lần lượt tính 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ó
  4. 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ử
  5. Số nằm phía trái mỗi dòng là số Bell cho mỗi dòng.

Như vây, dòng thứ nhất chỉ gồm số 1. Dòng tiếp theo (thứ hai) được tạo ra bằng cách lấy phần tử đầu tiên bên phải của dòng trên đặt vào vị trí đầu tiên bên trái. Ta có:

 1
 1 x

Giá trị của x là tổng của hai phần tử ở cột tước nó cúng dòng (là 1) và dòng trên (cũng là 1) bằng 2.

 1
 1 2
 y

Giá trị y bằng giá trị đầu tiên tính từ bên phải của dòng trên (bằng 2), và tiếp theo:

 1
 1 2
 2 3 x

Bằng cách ấy ta có 5 dòng đầu của tam giác là:

 1
 1 2
 2 3 5
 5 7 10 15
15 20 27 37 52

Dòng thứ năm được tính như sau:

  • Lấy 15 từ dòng thứ tư
  • 15 + 5 = 20
  • 20 + 7 = 27
  • 27 + 10 = 37
  • 37 + 15 = 52

Số đứng ở dòng thứ n và côth thứ k là số các phân hoạch của tập {1,..., n} sao cho n là không cùng một lớp với bất kỳ số nào trong các phần tử k, k + 1,..., n − 1. Chẳng hạn có 7 phân hoặc của {1,..., 4} sao cho 4 không cùng lớp với các phần tử 2, 3, và có 10 phân hoạch của {1,..., 4} sao cho 4 không cùng lớp với phần tử 3. Hiệu của hai số trên (bằng 3) là số các phân hoạch của {1,..., 4} sao cho 4 cùng lớp với 2 nhưng không cùng lớp với 3. Số này có ngiã rằng có 3 phân hoặc của {1,..., 3} sao cho 3 không cùng lớp với 2.

Dùng phương pháp này có thể tính nhờ JavaScript như trên cho 219 số Bell đầu tiên:

function write_bell (hBound) { // writes Bell-0,..., Bell-hBound
var value = [ 123.456, 1 ] // value [0] = unimportant, value [1] = 1
for (var rowNr = 0; rowNr <= hBound; rowNr ++) {
value [rowNr] = value [1]
for (var colNr = rowNr - 1; colNr >= 1; colNr--) value [colNr] += value [colNr+1]
document.write ('Bell-' + rowNr + ' = ' + value [1] + '<br>')
}
}
write_bell (218)

Các số nguyên tố Bell[sửa | sửa mã nguồn]

Một số nguyên tố Bell là một số Bell đồng thời là số nguyên tố. Các số nguyên tố Bell đầu tiên là:

2, 5, 877, 27644437, 35742549198872617291353508656626642567, 359334085968622831041960188598043661065388726959079837

tương ứng với các số Bell thứ 2, 3, 7, 13, 42 và 55. Số nguyên tố Bell tiếp theo là B2841, xấp xỉ với 9.3074 × 106538.

Tới năm 2005, số nguyên tố Bell lớn nhất đã biết là B2841. Phil Carmody phát biểu rằng nó là số nguyên tố năm 2002. Gần hai năm sau, Ignacio Larrosa Canestro đã chứng minh rằng nó là số nguyên tố.

Xem thêm[sửa | sửa mã nguồn]

Liên kết[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]