Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm preparing my discrete mathematics exam. Take one of the questions:

Given the two sets $$ A = \{ n \in \Bbb{N} | 1 \le n \le 18 \} = \{ 1, 2, \ldots, 18 \}\\B = \{ n \in A | (n, 18) = 2 \} = \{2,4,8,10,14,16\} \subset A $$

Find the cardinality of the set

$$ Z = \{ f \in A^B | \text{f is injective and } |B \cap f(B)| = 2 \} $$

These exercises can be solved by finding a bijection between $Z$ and some other set which is easier to handle. We are also required to explain why we found this set, optionally with drawings and so on. So, here's my solution:

Pick a $ C \in \binom{B}{2} $ and define:

$$ Z' = \{ f \in A^B | \text{f is injective and } f(C) \subset B \} $$

We have that

$$ Z' \sim Inject(C, B) \times Inject(B \setminus C, A\setminus B) $$

Therefore $$ Z \sim Z' \times \binom{B}{2} \sim Inject(I_2, B) \times Inject(I_4, A\setminus B)\times \binom{B}{2} $$

Now it is much easier to find the cardinality of the resulting set. In plain English, we pick two elements from $B$ and, for every possible way to send those elements back in two distinct elements of B, we send all the remaining elements to $A\setminus B$ in an injective manner (this is $Z'$). If we do this for every possible way to choose two elements from $B$ we have the resulting set.
And I would draw something like this:

sets

We are also awarded bonus points if we formally prove what we stated just above, that is if we actually find bijection between $Z$ and the other set. As far as I know, there are two ways to do this:

1) show a function $g:B \to A$ and its inverse $h: A \to B$, and prove that $g \circ h=id_A$ and $h \circ g = id_B$

2) show a function $g:B \to A$ and prove that it is both injective and surjective, so that it has an inverse.

Unfortunately, I have no idea on how to do this. Any help?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.