INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More

This is a problem from CMI Entrance 2014 based on Map from a power set to n-set.

**Problem: Map from a power set to n-set**

**(1) Let A = {1, ... , k} and B = {1, ... , n}. Find the number of maps from A to B . (2) Define be the set of subsets of A. Let f be a map from such that if then = . Find the number of such functions. (For example if k = 3 and n =4 then answer is 100) **

(1) For each member x of set A we have n choices for f(x) in B. Hence the number of functions is

(2) **Claim (i):** is minimum for any such function f from . This is because hence must be larger than for any member of

**Claim (ii)** If we fix the values of the singleton sets then the entire function is fixed. That is if we fix the values of f({1}) , f({2}) , ... , f({k}). Since for any member of is union of several singleton sets. Hence it's value is the maximum of the functional values of those singleton sets. For example let then

**Claim (iii)** f({1}) , ... , f({k}) are individually independent of each other.

Now we fix . Since it is the smallest, the singleton sets map to i to n.

Hence if each of the singleton sets have n choices from 1 to n; hence there are functions. Similarly each of the singleton sets have n-1 choices from 2 to n; hence there are functions.

Thus the total number of functions =

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIAL
[…] Let A = {1, … , k} and B = {1, … , n}. Find the number of maps from A to B . Define be the set of subsets of A. Let f be a map from such that if then = . Find the number of such functions. (For example if k = 3 and n =4 then answer is 100). Solution […]