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

rootmeister64

New member
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
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.