Home > Combinatorics > Số Stirling loại II

Số Stirling loại II


Đị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).

Categories: Combinatorics Tags:
  1. Anonymous
    August 23, 2011 at 2:38 am

    Minh cung dang lam luận văn thạc sĩ toán về vấn đề này . Bạn có tài liệu tham khảo ko . Giúp mình với …. nếu có file xin gởi về : rose99vn2005@gmail.com. Nếu đc cảm ơn bạn nhiều lắm

    • November 20, 2011 at 9:17 am

      Một số sách lên quan đến số Stirling mà bạn nên đọc
      Louis Comtet, Advanced combinatorics: the art of finite and infinite expansions
      Charles Jordan, Calculus of Finite Differences.

  2. Anonymous
    June 6, 2012 at 11:17 am

    Cảm ơn bạn nhiều

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: