[Toán 11] Tổ hợp khó

[baby_break_heart]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho trước số nguyên dương n và số nguyên dương r thoả mãn r<n-r+1. Giả sử X={1,2...,n}. Hỏi có bao nhiêu tập con A của X đồng thời có 2 tính chất sau:
+) A chứa r phần tử.
+) A không chứa 2 số nguyên liên tiếp.

 

[niemkieuloveahbu]

Mình gợi ý các bước giải chính:

Gọi A là họ tất cả các tập con của X có tính chất đã nêu,B là họ tất cả các tập con có r phần tử của tập hợp.

Y={1,2,...,n-(r-1)}

Thiết lập một ánh xạ f [TEX]A \to B[/TEX],ta chứng minh f là song ánh.
+) f là đơn ánh:Từ công thức [TEX]b_i=a_i-(i-1) \Rightarrow a_i=b_i+i-1[/TEX] nên nếu [TEX]f(A)=f(A')\Rightarrow A=A'[/TEX]

+) f là toàn ánh: [TEX]f(A)=B[/TEX]

Vì có một song ánh giữa A và họ các tập con có r phần tử của Y nên số các tâpj A có tính chất đã nêu = số tập con có r phần tử của Y.

Vậy có tất cả [TEX]C^r_{n-r+1}[/TEX] tập có tính chất đã nêu.