# Counting total Number of Functions

1. May 23, 2014

### 22990atinesh

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. May 23, 2014

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

3. May 23, 2014

### 22990atinesh

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
4. May 24, 2014

### verty

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

5. May 24, 2014

### 22990atinesh

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