Dùng ánh xạ trong các bài toán Tổ hợp


Để đếm số phần tử của một tập hữu hạn A, ta tìm một tập hữu hạn B có cùng số phần tử như A nhưng dễ đếm hơn.

Nguyên lý ánh xạ. Cho AB là các tập hữu hạn khác rỗng và f:A\to B là một ánh xạ. Khi đó

a)Nếu f là đơn ánh thì |A|\leq |B|;

b)Nếu f là toàn ánh thì |A|\geq |B|;

c)Nếu f là song ánh thì |A|=|B|.

Continue reading “Dùng ánh xạ trong các bài toán Tổ hợp”