Given: M = {1, 2,…, m} for m ∈ ℕ and N = {0, 1,…, 9}; injective and bijective mappings

rootmeister64

New member
Joined
Nov 7, 2020
Messages
10
Hello. I was wondering if my solutions for those problems are correct. It would be very nice if you could have a look at them. Thank you!

Given: M = {1, 2,…, m} for m ∈ ℕ and N = {0, 1,…, 9}
f: M ⟼ N, f (x) = 2⋅x (mod 10)

a) Give the Inverse image of f when m = 3.
M = {1, 2, 3}
f(1) = 2, f(2) = 4, f(3) = 6
Therefore the image is: f(x)-1={2, 4, 6}(Is this a correct notation?)

b) Assumption: g is a bijective mapping from M to N. How many maps h: M ⟼ N are there then?
Since there is no limit for m, I would say that there is an infinite amount of mappings from M to N.

c) How many permutations of N with 9 cycles are there?
Since we have 10 elements in N there will always be a cycle with 2 elements.
Only the cycle with two elements will ‘change’ the permutation. Therefore we have 10 * 9 = 90 cycles. However since (a, b) = (b, a) we have to divide this amount by 2. Thus there are only 45 permutations.

d) Give all 3-multisets of {0, 1}.
{0, 0, 0}, {0, 0, 1}. {0, 1, 1}, {1, 1, 1}

e) How many injective mappings are there from {0, 1} into the image of f, for m ≥ 5?
The image of f for m ≥ 5 is {0, 2, 4, 6, 8}. Thus we have to map from {0, 1} to {0, 2, 4, 6, 8}.
For 0 we have 5 options and for 1 we have 4 options. Therefore 5*4 = 20 possible mappings.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
10,916
a) Give the Inverse image of f when m = 3.
b) Assumption: g is a bijective mapping from M to N. How many maps h: M ⟼ N are there then?
c) How many permutations of N with 9 cycles are there?
d) Give all 3-multisets of {0, 1}.
e) How many injective mappings are there from {0, 1} into the image of f, for m ≥ 5?

The image of f for m ≥ 5 is {0, 2, 4, 6, 8}. Thus we have to map from {0, 1} to {0, 2, 4, 6, 8}.
For 0 we have 5 options and for 1 we have 4 options. Therefore 5*4 = 20 possible mappings.
First some notation. If \(A~\&~B\) are sets then \(\|A\|\) stands for the number of elements in \(A\).
\(A^B\) is the set of all mappings \(A\to B\). In the context of the question let's use finite subsets if \(\mathbb{N}\). So say \(\|A\|=m~\&~\|B\|=n.\)
1) If \(m\le n\) then there are \( _mP_n=\dfrac{m!}{(m-n)!}\) injections from \(A\to B\) That answers e).
2) if \(m<n\) then there are \(\sum\limits_{k = 0}^n {{{( - 1)}^k}\dbinom{n}{k}{{(n - k)}^m}} \) surjections from \(A\to B\).
3) If \(m=n\) then there are \( _m!\) bijections from \(A\to B\).
SEE HERE for multi-sets. Beyond those, I don't know what you are asking.
 
Top