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$.