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!

Counting functions

Tags:
  1. Jan 6, 2015 #1
    1. The problem statement, all variables and given/known data
    Let F be the set of one-to-one functions from the set ##{1,2,..,n}## to the set ##{1,2,...,m}## where ##m \geq n \geq 1##. Then how many functions f in F satisfy the property ##f(i)<f(j)## for some ##1 \leq i \leq j \leq n##

    2. Relevant equations


    3. The attempt at a solution
    ##^{m-1}P_n##. Is it correct
     
  2. jcsd
  3. Jan 6, 2015 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    What does that notation mean?
     
  4. Jan 6, 2015 #3
    Two more questions:
    - How many functions are there in F altogether?
    - What kind of functions fail to satisfy the given property?
     
  5. Jan 6, 2015 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    Show your reasoning---do not just write down the answer, or what you think is the answer.
     
  6. Jan 6, 2015 #5
    That's the exact question that has been asked.
     
  7. Jan 6, 2015 #6
    Its a Permutation
     
  8. Jan 6, 2015 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    I think should be a "number of permutations". But how is it defined? Is it the number of permutations of m-1 things taken n at a time?
     
  9. Jan 6, 2015 #8
    No, those are simpler questions: the first about the whole of F, not the restricted set your question asks for, and the second about the nature of the excluded functions in your question. But they can lead to answering the original question.


    Incidentally...
    No.
     
    Last edited: Jan 6, 2015
  10. Jan 7, 2015 #9
    So How can we solve this
     
  11. Jan 7, 2015 #10
    Back to my 2 questions...

    1. The total number of functions in F is relatively simple: what is that number? Obviously you could assign ##m## possible values for ##f(1)##, then ##m-1## possible values for ##f(2)##, etc., to count all functions

    2. What functions does the condition "##f(i)<f(j)## for some ##1 \leq i \lt j \leq n##" exclude? How many ways are there to make such functions?
     
  12. Jan 7, 2015 #11

    Stephen Tashi

    User Avatar
    Science Advisor

    Think of an example. Suppose we have the set of numbers {1,2,3,4,5}. Suppose we have the constraint "List the numbers so that at least two of them are listed in ascending order". You could count the number N of possible lists that satisfy this constraint by counting the number M that do not satisfy it and computing 5! - M = N.

    The number M counts the lists satisfying the statement "It is not true that at least two of the numbers are listed in ascending order" which can be phrased as "It is not true that there exists x in the list and there exists a y in the list such that x and y are listed in ascending order.". You could approach this as an exercise in logic. How do you negate a statement that has a "there exists..." requirement? The general pattern is "It is not true that there exists..." changes to "For each..... it is not true that...".

    Or you might try writing an example of a list that satisfys the condition "It is not true that there are at least two numbers listed in ascending order".
     
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: Counting functions
  1. Counting question (Replies: 9)

  2. Counting question (Replies: 8)

  3. Counting combinations (Replies: 7)

  4. Counting permutations (Replies: 6)

Loading...