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

Printable View

- Feb 23rd 2011, 08:12 AMdurrrrrrrrCombinatorics 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, 09:41 AMemakarov
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, 09:44 AMPlato
Given and in order for to be an injection then must be an injection.

There are injections .

Now for to be an injection it is not necessary for to be injective.

**However,****must be injective on the image of**

How many functions are there such that the restriction to is an injection? - Feb 24th 2011, 02:20 AMdurrrrrrrr
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, 02:43 AMPlato
- Feb 24th 2011, 05:47 AMdurrrrrrrr