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!

Counting total Number of Functions

  1. May 23, 2014 #1
    1. The problem statement, all variables and given/known data

    Consider Sets A={1,2,3,...,n} and B={1,2,3,...,m} where 1<=n<=m. F:A->B

    1) Total no. of strictly increasing function i.e if x<y then f(x)<f(y)
    2) Total no. of non decreasing function i.e if x<y then f(x)<=f(y)

    How can we count total number of functions here

    2. The attempt at a solution

    1st element in set A has [(m-1)-n+1] choices
    2nd ... [(m-2)-n+1] choices
    3rd ... [(m-3)-n+1] choices

    and so on

    So for 1) I'm getting (m-1)(m-2)(m-3)...(m-2n+1)
    Is it the correct approach
  2. jcsd
  3. May 23, 2014 #2


    User Avatar
    Homework Helper

    Do you agree in problem 1 that F must be injective? I think you do, so think how this interplays with the strictly increasing condition.

    What I'm trying to get at is, there is a more conceptual way to count those functions.
  4. May 23, 2014 #3
    Sorry for 1) It should be (m-1)(m-2)(m-3)...(m-n) and If the function is injective then ans for 1) should be (m-n)(m-n-1)(m-m-2)...(m-2n+1).
    Last edited: May 23, 2014
  5. May 24, 2014 #4


    User Avatar
    Homework Helper

    Why not try to verify your formulas by making n and m very small?
  6. May 24, 2014 #5
    Examples doesn't always works. If Logic is correct then example will definately work. :smile:
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 total Number of Functions