1. Limited time only! Sign up for a free 30min personal 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!

Number of functions such that f(i) not equal to i

  1. Feb 22, 2016 #1

    Titan97

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    ##A=\{1,2,3,4,5\}##, ##B=\{0,1,2,3,4,5\}##. Find the number of one-one functions ##f:A\rightarrow B## such that ##f(i)\neq i## and ##f(1)\neq 0\text{ or } 1##.

    2. Relevant equations
    Number of derangements of n things = $$n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots+(-1)^n\frac{1}{n!}\right)$$

    3. The attempt at a solution

    If either of ##0## and ##1## are not included in the range of ##f##, then total possibilities = ##2\times 44=88##

    If both ##0,1## are included in the range of ##f##, then one number from ##\{2,3,4,5\}## has to be mapped to ##1##. Number of possibilities is ##\binom{4}{1}##. Let me map ##1## to ##5##.
    For the remaining ##5## numbers, one number other than ##0,1## has to be excluded (since ##0,1## are in the range of ##f##) Number of such possibilities is ##\binom{3}{1}##. Let the number removed be ##4##.

    The remaining numbers ##\{0,1,2,3\}## has to be mapped to ##\{2,3,4,5\}##. How can I use principle of inclusion and exclusion here?
     
  2. jcsd
  3. Feb 22, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You can consider "mappings where both 2 and 3 are mapped to 2 and 3" and "mappings where either 2->2 or 3->3 but not both", and "all mappings". Not sure if that is faster than the approach "2 can be mapped to 3, or to 0 or 1, then ...".
     
  4. Feb 22, 2016 #3
    Use contraposition : Let ## f: A\to B ##

    Not## ( \forall i=1...5,\ f(i) \neq i \text{ and } f(1) \notin \{0,1\} ) \iff (\exists i = 1...5, f(i) = i \text{ or } f(1)\in \{0,1\} )##

    With that kind of reasoning, if ##N## is the total number of function from A to B, and ##M## the number you are are looking for, you should get a formula that looks like

    ##M = N - \# ((\cup_{i=1}^n A_i) \cup A) ##

    Hopefully the principle of inclusion exclusion will give you something interesting
     
  5. Feb 22, 2016 #4
    At second thought I think my previous post was unclear.
    What I meant is that if ##S## is the set of one to one maps from ##A## to ##B##,
    ##U## the subset of ##S## verifying your constraint, then ##S## is the disjoint union of ##U## and of its complement in ##S## (say ##V##). Then you know that ##|S| = |U| + |V| ##.
    Translate what it means for an element of ##S## to be in ##V##.
    Reduce into smaller unions, and apply the principle of inclusion exclusion.
     
  6. Feb 24, 2016 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    The formula you quote for derangements is a direct result of applying the principle of inclusion and exclusion, so try to use that rather than reinventing the wheel.
    If a mapping does not use 0 in B, it is a derangement of 5 objects, so the formula counts those.
    If a mapping does use the 0, you can extend the domain of the mapping in a unique way to make a derangement on B. Do you see how? That counts all those mappings, except that you have to discard some because 1 must not map to 0.
     
  7. Feb 24, 2016 #6

    Titan97

    User Avatar
    Gold Member

    I thought I could not use that formula if both 0,1 belong to the range of f because f(1) cannot take two values. (It works if either of 0,1 is excluded)
     
  8. Feb 24, 2016 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    As I posted, you just have to subtract out the derangements (of B) which mapped 1 to 0. How many things can 1 map to in a derangement of B? What fraction map it to 0?
     
  9. Feb 24, 2016 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    By the way, the really useful thing about the derangement formula is that you can pretend it is an infinite series and just round the result to the nearest integer. The error is less than 1/n.
     
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: Number of functions such that f(i) not equal to i
Loading...