Cm bằng phép song ánh nhá
bài toán tổ hợp sử dụng phép song ánh
Bắt đầu bởi Didier, 12-09-2011 - 18:04
#1
Đã gửi 12-09-2011 - 18:04
cho tập A={1,2,.............2n}Một Tập con B của A gọi là một tập cân nếu trong đó số các số chẵn và số các số lẻ bằng nhau .Hỏi A chứa bao nhiêu tập cân
#2
Đã gửi 12-09-2011 - 18:26
Bài này có trong cuốn "Tài liệu chuyên toán Đại số 10".
Giải:
Gọi C là họ tất cả các tập cân của A. Xét B là tập con của C nên B là tập cân.
Gọi L là tập tất cả các số lẻ của A. $L=\left\{ {1;3;5;...;2n-1} \right\} \Rightarrow |L|=n$
Gọi $B_1;B_2$ thứ tự là tập các số lẻ và các số chẵn của B.
Gọi X là họ tất cả các tập có n phần tử của tập A.
Xét cách tạo tập hợp Y với mỗi tập B như sau:
$Y = B_2 \cup \left( {L\backslash B_1 } \right)$
$|Y|=|B_2|+|L|-|B_1|=|L|=n$(do B là tập cân).
Suy ra, Y là một tập con của X.
Xét ánh xạ f đi từ tập C đến tập X, đặt tương ứng một tập B với một tập Y.
(Bạn tự cm f là song ánh nhé).
$|C|=|X|=C_{2n}^n$
Giải:
Gọi C là họ tất cả các tập cân của A. Xét B là tập con của C nên B là tập cân.
Gọi L là tập tất cả các số lẻ của A. $L=\left\{ {1;3;5;...;2n-1} \right\} \Rightarrow |L|=n$
Gọi $B_1;B_2$ thứ tự là tập các số lẻ và các số chẵn của B.
Gọi X là họ tất cả các tập có n phần tử của tập A.
Xét cách tạo tập hợp Y với mỗi tập B như sau:
$Y = B_2 \cup \left( {L\backslash B_1 } \right)$
$|Y|=|B_2|+|L|-|B_1|=|L|=n$(do B là tập cân).
Suy ra, Y là một tập con của X.
Xét ánh xạ f đi từ tập C đến tập X, đặt tương ứng một tập B với một tập Y.
(Bạn tự cm f là song ánh nhé).
$|C|=|X|=C_{2n}^n$
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!!
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.
#3
Đã gửi 22-09-2011 - 16:36
bài tập1:Gọi $ p_{n}(k)$là số hoạn vị của tập hợp $ {1,2,......,n}$có đúng k diểm cố định CMR$ \sum_{k=0}^{n}k.p_{n}(k)=n!$
bài tập 2 tính trung bình cộng các số$ n(n> 1)$chữ số tm các điều kiện
i)N gồm các chữ số $ {1,2,4,5}$ và hiệu số 2 chữ số liên tiếp luôn lớn hơn 1
j)N chia hết cho 11
bài tập 3 đặt $ F(k)=\sum_{i=0}^{k}\frac{(-1)^{i}}{i!},k\in \mathbb{N}$
Tính $ \sum_{i=0}^{k}\frac{F(k)}{(n-k)!}$
bài tập 2 tính trung bình cộng các số$ n(n> 1)$chữ số tm các điều kiện
i)N gồm các chữ số $ {1,2,4,5}$ và hiệu số 2 chữ số liên tiếp luôn lớn hơn 1
j)N chia hết cho 11
bài tập 3 đặt $ F(k)=\sum_{i=0}^{k}\frac{(-1)^{i}}{i!},k\in \mathbb{N}$
Tính $ \sum_{i=0}^{k}\frac{F(k)}{(n-k)!}$
Bài viết đã được chỉnh sửa nội dung bởi Didier: 22-09-2011 - 16:40
#4
Đã gửi 23-09-2011 - 16:55
Bài 1:
Tiếc là mình không thấy bộ gõ latex nên không trình bày cách thứ 2 được (cách này cũng xây dựng song ánh bằng việc so sánh lực lượng của hai tập, nhưng phải gõ công thức nhiều!)
Bây giờ ongtroi giải theo "song ánh" trên cơ sở: xây dựng hai cách đếm trên cùng một tập hợp!
Gọi A = {1, 2,..., n}. Với mọi x, y thuộc A. Ta xét tất cả các cặp (x, y) trong đó y là hoán vị với x làm điểm cố định. Với mỗi một giá trị của x, ta có (n - 1)! hoán vị y nhận x làm điểm cố định, và như thế có tất cả (n - 1)!n = n! cặp như vậy.
Nhưng nếu ta lại tính số cặp (x, y) theo y thì sẽ được tổng bên trái, vì với mỗi k, 0 < k < n, có pn(k) hoán vị với k điểm cố định và ứng với mỗi một hoán vị y này ta có cặp (x, y) khác nhau. Từ hai nhận xét đó ta có điều phải chứng minh.
Hỏi tiếp nữa: anh em nào có tài liệu song ánh không chia sẻ ongtroi với!
Tiếc là mình không thấy bộ gõ latex nên không trình bày cách thứ 2 được (cách này cũng xây dựng song ánh bằng việc so sánh lực lượng của hai tập, nhưng phải gõ công thức nhiều!)
Bây giờ ongtroi giải theo "song ánh" trên cơ sở: xây dựng hai cách đếm trên cùng một tập hợp!
Gọi A = {1, 2,..., n}. Với mọi x, y thuộc A. Ta xét tất cả các cặp (x, y) trong đó y là hoán vị với x làm điểm cố định. Với mỗi một giá trị của x, ta có (n - 1)! hoán vị y nhận x làm điểm cố định, và như thế có tất cả (n - 1)!n = n! cặp như vậy.
Nhưng nếu ta lại tính số cặp (x, y) theo y thì sẽ được tổng bên trái, vì với mỗi k, 0 < k < n, có pn(k) hoán vị với k điểm cố định và ứng với mỗi một hoán vị y này ta có cặp (x, y) khác nhau. Từ hai nhận xét đó ta có điều phải chứng minh.
Hỏi tiếp nữa: anh em nào có tài liệu song ánh không chia sẻ ongtroi với!
Bài viết đã được chỉnh sửa nội dung bởi ongtroi: 23-09-2011 - 16:57
- NHoang1608 và duylax2412 thích
#5
Đã gửi 05-01-2019 - 21:26
CHo mình hỏi họ các tập con là gì ạ
Bài viết đã được chỉnh sửa nội dung bởi Gianghg8910: 05-01-2019 - 21:27
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh