# Combinations?

• May 29th 2009, 07:53 PM
fardeen_gen
Combinations?
If X is a set containing n elements and Y is a set containing m elements, how many functions are there from X to Y? How many of these functions are one-to-one?
• May 31st 2009, 01:49 AM
Isomorphism
Quote:

Originally Posted by fardeen_gen
If X is a set containing n elements and Y is a set containing m elements, how many functions are there from X to Y? How many of these functions are one-to-one?

For every element in X, I just need to associate an element of Y(for which I have m choices). Thus $\displaystyle m^n$ functions.

For one-one functions, For every element in X, I need to associate only one element of Y. Thus for the first one I have, m choices. Then for the second element, I have m-1 choices and so on. So it is $\displaystyle \frac{m!}{(m-n)!}$
• May 31st 2009, 01:56 AM
Moo
And for your information, there are $\displaystyle m\times (m-1)\times \cdots\times (m-n+1)$ injective functions from X to Y.
• May 31st 2009, 02:26 AM
Isomorphism
Quote:

Originally Posted by Moo
And for your information, there are $\displaystyle m\times (m-1)\times \cdots\times (m-n+1)$ injective functions from X to Y.

Isnt that the same as $\displaystyle \frac{m!}{(m-n)!}$? (Wondering)
• May 31st 2009, 02:33 AM
Moo
Yes, it's the same.
But that's what I had in my notes. (they're from last year, so I don't have the proofs...)

I'm wondering... If $\displaystyle m\neq n$, is it possible to have one-to-one functions from X to Y ? :D

We may consider that we're dealing with functions whose domain is X, and whose range is Y. In which case, there is no one-to-one functions (Thinking)

If $\displaystyle m=n$, the number of bijective functions is n!
• May 31st 2009, 06:46 AM
pankaj
Quote:

Originally Posted by fardeen_gen
If X is a set containing n elements and Y is a set containing m elements, how many functions are there from X to Y? How many of these functions are one-to-one?

O.K fardeen_gen.
Do you know the number of ONTO functions from X to Y