Thread: What does it mean to "count" bijections

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 =|

Originally Posted by crabchef

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 =|

It means you have to count all the functions that are bijections between two given sets with n elements each. Try it with n = 1,2,3,4 and check whether you can find out a general pattern. Hint: factorial

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 =(

Originally Posted by crabchef

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?(

When you say “I don't understand the problem”, that is clearly the case.
There are two bijections from they are .

There are bijections from .

So in general, your answer for finite sets is simply .

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

No one mentioned it so far, so I will point out the obvious: counting bijections in this case is the same as counting permutations.