Wednesday, March 29, 2006

Set To Set. Topic: Sets. Level: Olympiad.

Problem: (360 Problems For Mathematical Contests - 6.1.4) Let $ A $ be a set with $ n $ elements and let $ X $ be a subset of $ A $ with $ k \ge 1 $ elements. Find the number of functions $ f: A \rightarrow A $ such that $ f(X) = X $.

Problem: First consider the elements of $ X $. Since $ f(X) $ has to return the same set of elements, no two elements $ a,b \in X $ can have $ f(a) = f(b) $ (or we wouldn't be able to get the entire set back). So if we pick any element $ a $ we have $ k $ choices for $ f(a) $. Then when we pick $ b $ we only have $ k-1 $ choices for $ f(b) $. Continuing this, we find that there are $ k! $ ways to assign each element in $ X $.

Now for the other $ n-k $ elements of $ A $, we can arbitrarily assign where they map to. Since each has $ n $ elements to map to, there is an additional factor of $ n^{n-k} $ to the number of functions.

This gives us a total of $ k! \cdot n^{n-k} $ possible functions $ f $. QED.

--------------------

Comment: Basic sets and functions are a good thing to know in order to build on. They don't require much mathematical background to work through, and are mostly logical (with some combinatorics).

--------------------

Practice Problem: (360 Problems For Mathematical Contests - 6.1.1) Let $ A $ be a set with $ n $ elements and let $ B $ be a subset of $ A $ with $ m \ge 1 $ elements. Find the number of functions $ f: A \rightarrow A $ such that $ f(B) \subseteq B $.

No comments:

Post a Comment