# Combinatorics question

• Feb 23rd 2011, 09:12 AM
durrrrrrrr
Combinatorics question
Let A be a set of size n, B a set of size m, C a set of size k. n≤m≤k

How many ordered pairs of functions (f,g) are there such that f:A-->B, g:B-->C and gºf is injective?

(The working out is what I really want to know).

Thanks
• Feb 23rd 2011, 10:41 AM
emakarov
Hint: if g o f is an injection, then so is f, and g is injective on the image of f. Perhaps you can start by figuring the number of injective f's.
• Feb 23rd 2011, 10:44 AM
Plato
Quote:

Originally Posted by durrrrrrrr
Let A be a set of size n, B a set of size m, C a set of size k. n≤m≤k How many ordered pairs of functions (f,g) are there such that f:A-->B, g:B-->C and gºf is injective?

Given $|A|=n\le|B|=m\le|C|=k$ and $f:A\to B,~g:B\to C$ in order for $g\circ f:A\to C$ to be an injection then $f$ must be an injection.
There are $\frac{m!}{(m-n)!}$ injections $A\to B$.

Now for $g\circ f:A\to C$ to be an injection it is not necessary for $g$ to be injective.
However, $g$ must be injective on the image of $f,~f[A].$
How many functions $g:B\to C$ are there such that the restriction to $f[A]$ is an injection?
• Feb 24th 2011, 03:20 AM
durrrrrrrr
Quote:

Originally Posted by Plato
Given $|A|=n\le|B|=m\le|C|=k$ and $f:A\to B,~g:B\to C$ in order for $g\circ f:A\to C$ to be an injection then $f$ must be an injection.
There are $\frac{m!}{(m-n)!}$ injections $A\to B$.

Now for $g\circ f:A\to C$ to be an injection it is not necessary for $g$ to be injective.
However, $g$ must be injective on the image of $f,~f[A].$
How many functions $g:B\to C$ are there such that the restriction to $f[A]$ is an injection?

Thank you. There's just one thing I don't understand. This is what I have so far:
We have m!/(m-n)! injective functions f from A to B.
We have k!/(k-n)! injective functions g from Im(f) to C.
Why are we counting the the functions g from B to C that are not in the image of f?
I know we have k^(m-n) such as these, but why are we counting them?
• Feb 24th 2011, 03:43 AM
Plato
Quote:

Originally Posted by durrrrrrrr
Why are we counting the the functions g from B to C that are not in the image of f? I know we have k^(m-n) such as these, but why are we counting them?

If we have two mappings $g_1~\&~g_2$ which agree on $f[A]$ but differ on $B\setminus f[A]$ then is it not true that $(g_1, f) ~\&~( g_2, f)$ are two different pairs? The questions asks for pairs.
• Feb 24th 2011, 06:47 AM
durrrrrrrr
Quote:

Originally Posted by Plato
If we have two mappings $g_1~\&~g_2$ which agree on $f[A]$ but differ on $B\setminus f[A]$ then is it not true that $(g_1, f) ~\&~( g_2, f)$ are two different pairs? The questions asks for pairs.

Ah. I finally understand. Thank you