Counting total Number of Functions

[22990atinesh]

Homework Statement

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

 

[verty]

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.

 

[22990atinesh]

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.

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).

 

[verty]

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).

Why not try to verify your formulas by making n and m very small?

 

[22990atinesh]

Why not try to verify your formulas by making n and m very small?

Examples doesn't always works. If Logic is correct then example will definitely work.