Diễn Đàn MathScope

Diễn Đàn MathScope (http://forum.mathscope.org/index.php)
-   Logic, Tập Hợp, Toán Rời Rạc (http://forum.mathscope.org/forumdisplay.php?f=132)
-   -   Đếm số toàn ánh (http://forum.mathscope.org/showthread.php?t=37362)

congbang_dhsp 02-11-2012 01:14 AM

Đếm số toàn ánh
 
Cho tập $E$ có $n$ phần tử, tập $F$ có $m$ phần tử. Có bao nhiêu ánh xạ toàn ánh từ $E$ vào $F? \,\ (n \ge m)$

tantinh89 02-11-2012 05:28 PM

Trích:

Nguyên văn bởi congbang_dhsp (Post 175747)
Cho tập $E$ có $n$ phần tử, tập $F$ có $m$ phần tử. Có bao nhiêu ánh xạ toàn ánh từ $E$ vào $F? \,\ (n \ge m)$

Một hàm toàn ánh
$f:N \to M $ được đếm bằng cách thực hiện hành động H "tạo ra hàm toàn ánh" bao gồm 2 giai đoạn
${H_1} $ và ${H_2} $ như sau:
Giai đoạn ${H_1} $: Tạo ra một phân hoạch
$\mathop N\limits^{\_\_} $ của $N $ gồm $m $ khối. Áp dụng định nghĩa của số Stirling loại hai, ta có
$S(n,m) $ cách thực hiện giai đoạn ${H_1} $
Giai đoạn ${H_2} $: Tạo ra một hàm song ánh
$\mathop f\limits^{\_\_} :\mathop N\limits^{\_\_} \to M $. Áp dụng công thức đếm tất cả các hàm đơn ánh từ tập N vào tập M, ta có $m! $ cách thực hiện giai đoạn ${H_2} $
@ Theo quy tắc nhân, ta có:
Số các hàm toàn ánh $\mathop f\limits^{\_\_} :\mathop N\limits^{\_\_} \to M $ với
$\left| N \right| = n,\left| M \right| = m $ là:
$m!S(n,m) $

pgviethung 02-11-2012 07:31 PM

Bài này dùng nguyên lý bù trừ.
Ta sẽ đếm số ánh xạ không toàn ánh.
Gọi $A_i $ là tập các ánh xạ mà trong tập ảnh không chứa phần tử thứ i của tập F.
Như vậy thì tập các ánh xạ không toàn ánh là hợp của các $A_i $. Dùng nguyên lý bù trừ để đếm số phần tử.
P/S: nếu bạn học ở DHSPHN thì tham khảo sách Đại số sơ cấp của các thầy Dương Quốc Việt và Đàm Văn Nhỉ sẽ có phần này.


Múi giờ GMT. Hiện tại là 10:32 PM.

Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.

[page compression: 5.11 k/5.46 k (6.37%)]