1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Determine the order of a subset of S_n

  1. Oct 11, 2014 #1
    1. The problem statement, all variables and given/known data
    We have a set S = {a,b,c,d} and a set X such that X = {##f:S \rightarrow S| ## f is bijective and ## f(x) \neq x## for each ##x \in S##}. What is the order of the set?

    2. Attempt at Solution/My Reasoning

    The order of the set of all bijective functions is simply the 4!. There is one element of set of all bijective functions such that f(x) = x, so we subtract 1 from the order of that set.

    Now we keep one element set equal to itself and find all functions such that only that element returns itself. Then you have 3 spots in which the other elements can be mapped to. However, you don't want an element to be mapped to itself so you only have 2 ways in which you can complete this. So you have ## {4 \choose 3} \cdot 2!## ways in which you can do this. Where ##{4 \choose 3}## is the number of ways you can choose that one element.

    Next we keep two elements equal to themselves and find all functions where the other two are not. So we have only 1 way in which they can be mapped so then we have ##{4 \choose 2} \cdot 1!## functions such that this is true.

    In total we should have 9 functions that satisfy the requirements of X. Is my way of thinking about this right? How can we generally determine the order of this subset of functions?
     
  2. jcsd
  3. Oct 11, 2014 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, it's correct. Permutations like this are called 'derangements'. You can Google that if you want the general case.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Determine the order of a subset of S_n
Loading...