I have a set, namely $\mathbb{Z}_6$, and I was taught how to find how many relations there are. For example, this set has $2^{36}$ relations. I was wondering how to find how many of these relations are mappings, and how many of these mappings are permutations. Can anyone help with some sort of formula for these types of questions?
1 Answer
Let $S$ be the set $\{1,2,3,4,5,6\}$.
Relations
Now relations are simply elements of the powerset of $S^2$. Counting the number of elements in the powerset of a set $A$ is simply $2^{|A|}$. And indeed, there are $36$ elements in $S^2$, so the correct answer is $2^{36}$ as you pointed out.
Mappings
Now mappings are elements of the powerset of $S^2$, such that so many rules apply. Instead, I want to think simply about the choices for $f(1), \dots,f(6)$, each one has $6$ choices, namely $1, \dots, 6$. So that's $6^6 = 46656$ in total. In general, the number of mappings from set $A$ to set $B$ is $|B|^{|A|}$.
Permutations
Each permutation is a special mapping. Now, after the initial $6$ choices for $f(1)$, we have $5$ choices for $f(2)$, and so on, until we have only one choice for $f(6)$. For this reason the number of permutations is $6! = 720$. In general, the number of permutations from a set $A$ to itself is $|A|!$
-
$\begingroup$ Thank you so much! Now I don't have to go sifting through hundreds of pages and exercises lol $\endgroup$– KiqroCommented Nov 15, 2017 at 1:34