Archive

Archive for the ‘Combinatorics’ Category

Số Stirling loại II

October 24, 2008 3 comments

Định nghĩa: Số phân hoạch tập hợp n phần tử thành k khối (partittions in k blocks) gọi là số Stirling loại II, kí hiệu S(n,k)

Ta biết rằng mỗi cách phân hoạch một tập hợp tương ứng 1-1 với một quan hệ tương đương trên tập hợp đó. Do đó ý nghĩa của số Stirling là số các quan hệ tương đương với k lớp trên một tập hợp n phần tử.

Số Stirling có thể tính trực tiếp qua công thức sau:


Ở đây tôi sử kí hiệu kí hiệu C^k_n=\frac{n!}{(n-k)!k!}A^k_n=\frac{n!}{(n-k)!}

Thật vây, gọi N là tập hợp n phần tử đang xem xét. E là tập các ánh xạ từ N vào \{1, 2, ..., k\}, và F là tập con các toàn ánh trong E. Khi đó . Sử dụng nguyên lý bao hàm-loại trừ (The Principle of Inclusion and Exclusion, sẽ đề cập chi tiết về nguyên lý này trong một bài viết khác) suy ra dễ dàng được công thức trên.

Các tính chất:

1.   (Generating Function)
2.

3.
4.
5.

6.

7.

8.

9.

10.

Quan hệ tương đương liên hệ chặt chẽ với phân hoạch phân hoạch. Một quan hệ tương đương R trên một tập N tương ứng với một phân hoạch tập đó theo các lớp tương đương của R. Ngược lại một phân hoạch  bất kì ứng với quan hệ tương đương trên N.

Sau đây là phép chứng minh quan hệ đệ quy
 
bằng phương pháp phân lớp tập hợp theo quan hệ tương đương

Cố định một phần tử , và một tập con sao cho xét quan hệ tương đương R trên tập tất cả các phân hoạch thành k khối  của tập N
khi và chỉ khi có chung khối . R là quan hệ tương đương nên phân hoạch thành các lớp tương đương. Giả sử s phần tử thì mỗi lớp tương đương theo R có số phần tử bằng nhau và bằng  Mặc khác có cách chọn . Do đó:

(đặt l=n-s)

Dễ thấy công thức S(n,k)=S(n-1,k-1)+kS(n-1,k) nhận được từ hai trường hợp có chứa khối hoặc không chứa khối này,với là phần tử cố định của N. và c. suy ra từ a. Dĩ nhiên a., b., c. có thể suy ra trực tiếp từ công thức tính S(n,k).

Advertisements
Categories: Combinatorics Tags: