2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you so much! Now I don't have to go sifting through hundreds of pages and exercises lol $\endgroup$ – Kiqro Nov 15 '17 at 1:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.