Số Stirling Loại II - Tuan-Minh Nguyen

Trang chủ » Công Thức Số Stirling » Số Stirling Loại II - Tuan-Minh Nguyen

Có thể bạn quan tâm

Đị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:

\displaystyle S(n,k)=\frac{1}{k!}\sum_{0\le j\le k}{(-1)^jC^j_k(k-j)^n} \displaystyle=\frac{1}{k!}\sum_{1\le i\le k}{(-1)^{k-i}C^i_ki^n}

Ở đây ta sử kí hiệu kí hiệu \displaystyle C^k_n=\frac{n!}{(n-k)!k!} và \displaystyle 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 đó E=k^n và F=k!S(n,k). 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. \displaystyle F_k(x)=\sum_{n\ge k}S(n,k)x^n=\frac{x^k}{(1-x)(1-2x)...(1-kx)} (Generating Function)

2. \displaystyle E_k(x)=\sum_{n\ge k}S(n,k)\frac{x^n}{n!}=\frac{(e^x-1)^k}{k!}

3. S(n,k)=S(n-1,k-1)+kS(n-1,k)

4. S(n,k)=\displaystyle\sum_{k-1\le l\le n-1}{C^l_{n-1}S(l,k-1)}

5. S(n,k)=\displaystyle\sum_{k\le l\le n}{S(l-1,k-1)k^{n-1}}

6. m^n=\displaystyle\sum_{0\le k\le n}{S(n,k)A_m^k}

7. \displaystyle S(n,k)=\frac{k^n}{k!}-\frac{1}{k!}\sum_{j=1}^{k-1}{A_k^jS(n,j)}

8. \displaystyle S(n,k)=\sum_{0\le j\le n-k}{(-1)^jA_j^{k+1}S(n+k,k+j+1)}

9. \displaystyle S(n,k)=\sum_{r_1+r_2+...+r_k=n-k}{1^{r_1}2^{r_2}...k^{r_k}}

10. \displaystyle S(n,k)=\frac{1}{k!}\left| \begin{array}{ccccccc}1 & 1 & 1 & \ldots & 1 & 1 & 1\\ 1 & 2 & 2^2 & \ldots & 2^{k-3} & 2^{k-2} & 2^n\\ 1 & 3 & 3^2 & \ldots & 3^{k-3} & 3^{k-2} & 3^n\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots\\ 1 & k & k^2 & \ldots & k^{k-3} & k^{k-2} & k^n\end{array} \right|

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 \pi bất kì ứng với quan hệ tương đương R(\pi)=\bigcup_{B\in\pi}{B\times B} trên N.

Sau đây là phép chứng minh quan hệ đệ quy

\displaystyle S(n,k)=\sum_{k-1\le l\le n-1}{C^l_{n-1}S(l,k-1)}

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ử x_0\in N, và một tập con N_0\subset N sao cho x_0\in N_0 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 P_k của tập N \pi_1 R\pi_2 khi và chỉ khi \pi_1 và \pi_2 có chung khối N_0. R là quan hệ tương đương nên phân hoạch P_k thành các lớp tương đương. Giả sử N_0 có 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 S(n-s,k-1). Mặc khác có C^{s-1}_{n-1}=C^{n-s}_{n-1} cách chọn x_0 và N_0. Do đó:

\displaystyle S(n,k)=\sum_{s=1}^{n-k+1}{C_{n-1}^{n-s}S(n-s,k-1)} \displaystyle =\sum_{l=k-1}^{n-1}{C^l_{n-1}S(l,k-1)}.

(đặ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 \{x_0\} hoặc không chứa khối này,với x_0 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).

Share this:

  • Facebook
  • Email
  • Print
  • More
  • LinkedIn
  • Twitter
  • WhatsApp
  • Reddit
  • Tumblr
  • Pinterest
  • Telegram
Like Loading...

Related

Từ khóa » Công Thức Số Stirling