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!

Number of injections, of functions

  1. Apr 23, 2015 #1
    1. The problem statement, all variables and given/known data
    Show that the number of injections from ##E \rightarrow F ##, ##E,F## finite sets, ## p = \#E ,\ n = \#F,\ p\le n ##, is ##\frac{n!}{(n-p)!} ##
    Then, find the number of functions from ##E \rightarrow F ##.

    2. Relevant equations

    ## A = \{ \text{injections from }E \rightarrow F \} ##
    ## B = \{ \text{arrangements of } p \text{ elements among } n \} ##
    ## C = \{ \text{functions from }E \rightarrow F \} ##
    ## D = (F \cup \{a\}) \times ....\times (F \cup \{a\})##, ## p ## times , ## a \notin F ##

    3. The attempt at a solution

    Hello, I have to solve this problem for my homework. It took me a while but I think I have found it. Is it correct ?

    a) I want to prove that there is a bijection from ##A## to ##B## so that ##\# A = \#B = \frac{n!}{(n-p)!} ##.
    I define the mapping ## h: A \rightarrow B ## by ## h(f) = (f(x_1),...,f(x_p)) ##.

    We have ##h(f)\in B## because ##f## is injective.

    ##h## is injective because for all ##f,g\in A##, ## h(f) = h(g) \Rightarrow \forall i=1...p,\ f(x_i) = g(x_i) \iff f = g ##.

    For any arrangement ##(y_1,...,y_p)\in B##, I define ##f## such that for all ##i = 1...p##, ## f(x_i) = y_i ##. Then ##f## is necessarily injective because if we had ## f(x_i) = f(x_j)## and ## x_i \neq x_j ##, then we would have ## y_i = y_j ##, which contradicts the definition of an arrangement. So ## f\in A ## and ##h## is a surjection.

    So ## h ## is a bijection

    b) Same kind of problem.
    I define the mapping ## h: C \rightarrow D ## by ## h(f) = (y_1, ..., y_p)## where
    \begin{equation}
    y_i =
    \left\lbrace
    \begin{array}{ccc}
    f(x_i) & \mbox{if} & x_i\in \cal D(f)\\
    a & & \mbox{otherwise} \\
    \end{array}\right.
    \end{equation}

    Injectivity is shown the same way as above.

    For any tuple ##(y_1,...,y_p)\in D##, I define ##f## by ## f(x_i) = y_i \iff y_i \neq a ##. Clearly ##f## belongs to ##C## and h is surjective .

    Then h is bijective and ##\# C = \#D = (\#(F \cup \{a\}))^p = (n+1)^p ## (because ##\{a\}## and ##F## disjoint)
     
    Last edited: Apr 23, 2015
  2. jcsd
  3. Apr 23, 2015 #2
    a) seems correct to me

    b) You seem to also count the functions that have as domain any subset of E. Why you doing that? Otherwise the answer should be ##n^p##.
     
  4. Apr 23, 2015 #3
    Hello, thank you for proofreading.
    Concerning your question, the difference between a function ##f## and a mapping ##g## both from ## E \rightarrow F ##, is that ##{\cal D}(f)\subset E## while ##{ \cal D}(g) = E ##. There are functions that are not defined on ##E## entirely (ex: ##E = \mathbb{R},\ f(x) = \frac{1}{x},\ {\cal D}(f) = E - \{0\}## )
     
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 injections, of functions
  1. Injective Compositition (Replies: 10)

Loading...