# Counting functions

22990atinesh

## Homework Statement

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

## The Attempt at a Solution

##^{m-1}P_n##. Is it correct

## Answers and Replies

##^{m-1}P_n##. Is it correct

What does that notation mean?

Joffan
Two more questions:
- How many functions are there in F altogether?
- What kind of functions fail to satisfy the given property?

Homework Helper
Dearly Missed

## Homework Statement

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

## The Attempt at a Solution

##^{m-1}P_n##. Is it correct

Show your reasoning---do not just write down the answer, or what you think is the answer.

22990atinesh
Two more questions:
- How many functions are there in F altogether?
- What kind of functions fail to satisfy the given property?

That's the exact question that has been asked.

22990atinesh
What does that notation mean?

Its a Permutation

Its a Permutation

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?

Joffan
Two more questions:
- How many functions are there in F altogether?
- What kind of functions fail to satisfy the given property?
That's the exact question that has been asked.
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...
## ^{m-1}P_n##. Is it correct
No.

Last edited:
22990atinesh
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.
So How can we solve this

Joffan
So How can we solve this
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?