Count the bijections from A to B, given that |A|=|B|= n.
homework hint: No proof required. Count the bijections from {1,2} to {1,2}, then count the bijections from {1,2,3} to {1,2,3}, etc. When you are confident you know the formula for the number of bijections from {1,2,...,n} to {1,2,...n}, then write it down.
My question: what does counting bijections mean? I thought a function was either a bijection or not =|
Thanks for the response. I now understand what it means to count a bijection, but I still don't really understand what's going on here.
Let's say n=1, then we have {1} to {1}...There's only one function here that works right? f(x)=x?
Let's say n=2, then we have {1,2} to {1,2}...don't we still only have one function that works, f(x)=x?
I don't understand the problem =(
I think the part that I don't understand is, how did you come up with (1,1),(2,2) and (1,2),(2,1) are bijections of {1,2} to {1,2}?
Edit: Ah, I think I get it. When we say how many bijections are there from {1,2} to {1,2}, are we just asking how many different ways can we match numbers from one set to another? Like 1 can either go to 1 or 2. If the set was {1,2,3} then 1 can go to 1, 2, or 3? This would make sense to me...and gives me n! as an anwer
Thanks for the help guys!!
Yes, that's what bijections are. More formally, if you have these two sets, a bijective function between them is one that is one-to-one and onto.
One-to-one means that it connects exactly 1 element from set A and goes to exactly 1 element in set B.
Onto is when for every element x in set B, we have 1 or more elements in A that go to x.
1 ------- 2
2 ------- 1 is a bijection from {1,2,3} to {1,2,3}
3 ------- 3
1 ------- 2
2 ------- 2 is not a bijection since it is neither one to one, nor onto
3 ------- 3