Question

do you know how many onto functions are there from a set A to set B of cardanility m and n respectively ?

Answer 1

Yes I know.

Answer 2

lol let see what james and zarkon say

Answer 3

This one is well known for a any combinatorics student.

Answer 4

Lets say if you have 12 pieces of distinct candies and 3 children, in how many ways can you distribute them if each get at-least one ?

Answer 5

btw easy one: how many injection is possible ?

Answer 6

and what about bijection ?

Answer 7

if n<m and under a function each element of A can map to only one element of B, there can be no onto functions. I think

Answer 8

yep, but n>m

Answer 9

It's the opposite, I think, because you're mapping from A to B. A elements have to be more than B.

Answer 10

n^m i think

Answer 11

Or equal*.

Answer 12

i think n>m is a lot harder to think for me

Answer 13

n and m don't have any restrictions do they? You can have everything map to the same value, or you can have some values unmapped if m is smaller.

Answer 14

no,Mr.Math myin is right, if \( f:A \to B \) cardnality of B should be greater than or equal to A

Answer 15

Fool: why? f(anything) mapping to 6.32 is still a valid function, even though cardinality of A is infinite and cardinality of B is 1.

Answer 16

Well, I don't give easy problems to men-i-naya ;) :D

Answer 17

if n = m we have a bijection...

Answer 18

ktk you are counting onto functions, assume finite sets.

Answer 19

we are*

Answer 20

are you saying with finite sets it's not legal to have more than one value map to the same value?

Answer 21

@ktklown: I am not talking about anything else outside this precise problems with precise constraints.

Answer 22

So B has m elements and the first element of A can map to any the elements in B.
The second can map to any of the remaining m-1 elements in B.
Third can map to any of the m-2 elements in B.
and so on...
So the total number of onto functions is m(m-1)(m-2)...(3)(2)(1)=m!

Answer 23

but for the last case needs more thinking

Answer 24

myin your analysis is right for bijection

Answer 25

I still think that cardinality of A has to be greater than equal than B. Can you find a surjection from \((1,2)\to (a,b,c)\)?

Answer 26

yes, we can Mr.Math

Answer 27

m<n here there are no onto functions

Answer 28

wait no i had my cardinalities mixed up

Answer 29

|A|=m
|B|=n

Answer 30

The condition should be \(m\ge n\).

Answer 31

I'm confused now. Its bed time.

Answer 32

lol

Answer 33

|A|=m; and |B|=n and 1<= n <=m, then the number of onto functions form A to B is ?

Answer 34

I blame fool and mr. math for all of my confusion.
Fool for asking a hard problem this late and mr. math for being there.

Answer 35

lol, :D

Answer 36

Give yourself an applause.

Answer 37

lol, that's what I've been saying @fool :D

Answer 38

look at Stirling numbers of the second kind

Answer 39

yes there goes Zarkon!

Answer 40

I'm sorry myin, but you've been having the wrong condition :P

Answer 41

but not exactly \( \left\{\begin{matrix} m \\ n \end{matrix}\right\} \) though.

Answer 42

i got my m and n mixed up for the sets earlier

Answer 43

you will need an n! too.

Answer 44

yep! \[ n! \times \left\{\begin{matrix} m \\ n \end{matrix}\right\} \]

Answer 45

btw Zarkon, do you know the inclusion-exclusion approach for this one ?

Answer 46

if m=n: So B has n elements and the first element of A can map to any the elements in B.
The second can map to any of the remaining n-1 elements in B.
Third can map to any of the n-2 elements in B.
and so on...
So the total number of onto functions is n(n-1)(n-2)...(3)(2)(1)=n!