Counting One-to-One Functions from n to m with Property f(i)<f(j)

In summary: Then try to write an example of a list that does not satisfy the condition. In summary, There are ##^{m-1}P_n## functions in F that satisfy the property ##f(i)<f(j)## for some ##1 \leq i \leq j \leq n##.To solve this problem, we can first find the total number of functions in F by assigning each element in the set {1,2,...,n} a possible value in the set {1,2,...,m}. This would result in m possible values for f(1), m-1 for f(2), and so on, resulting in m! possible functions in F.Next, we can consider the functions
  • #1
143
1

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

Homework Equations

The Attempt at a Solution


##^{m-1}P_n##. Is it correct
 
Physics news on Phys.org
  • #2
22990atinesh said:
##^{m-1}P_n##. Is it correct

What does that notation mean?
 
  • #3
Two more questions:
- How many functions are there in F altogether?
- What kind of functions fail to satisfy the given property?
 
  • #4
22990atinesh said:

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

Homework Equations

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.
 
  • #5
Joffan said:
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.
 
  • #6
Stephen Tashi said:
What does that notation mean?

Its a Permutation
 
  • #7
22990atinesh said:
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?
 
  • #8
Joffan said:
Two more questions:
- How many functions are there in F altogether?
- What kind of functions fail to satisfy the given property?
22990atinesh said:
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...
22990atinesh said:
## ^{m-1}P_n##. Is it correct
No.
 
Last edited:
  • #9
Joffan said:
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
 
  • #10
22990atinesh said:
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?
 
  • #11
22990atinesh said:
So How can we solve this

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

1. What is a one-to-one function?

A one-to-one function is a mathematical relationship between two sets, in which each element in the first set is paired with exactly one element in the second set. This means that for every input in the first set, there is only one corresponding output in the second set.

2. How do you count one-to-one functions from n to m?

To count one-to-one functions from n to m, you would use the formula n!/(n-m)!, where n is the number of elements in the first set and m is the number of elements in the second set. This formula takes into account the fact that each element in the first set can only be paired with one element in the second set.

3. What is the property f(i)

The property f(i)

4. Can you give an example of a one-to-one function from n to m with the property f(i)

Yes, an example of a one-to-one function from n to m with the property f(i)

5. Why is counting one-to-one functions from n to m with the property f(i)

Counting one-to-one functions from n to m with the property f(i)

Suggested for: Counting One-to-One Functions from n to m with Property f(i)<f(j)

Back
Top