edited by
6,336 views
44 votes
44 votes

Let $F$ be the set of one-to-one functions from the set $\{1, 2, \dots, n\}$ to the set $\{1, 2,\dots, m\}$ where $m\geq n\geq1$.

  1. How many functions are members of $F$?

  2. How many functions $f$ in $F$ satisfy the property $f(i)=1$ for some $i, 1\leq i \leq n$?

  3. How many functions $f$ in $F$ satisfy the property $f(i)<f(j)$ for all $i,j \ \ 1\leq i \leq j \leq n$?

edited by

3 Answers

Best answer
62 votes
62 votes
(a) A function from A to B must map every element in A. Being one-one, each element must map to a unique element in B. So, for $n$ elements in A, we have $m$ choices in B and so we can have $^m\mathbb{P}_n$ functions.

(b) Continuing from (a) part. Here, we are forced to fix $f(i) = 1$. So, one element from A and B gone with $n$ possibilities for the element in A and 1 possibility for that in B, and we get $n \times$ $^{m-1}\mathbb{P}_{n-1}$ such functions.

(c) $f(i) < f(j)$ means only one order for the $n$ selection permutations from B is valid. So, the answer from (a) becomes $^m\mathbb{C}_n$ here.
edited by
–5 votes
–5 votes

A) mPn

B) mPn - m-1Pn

C) (m*(m-1))/2

Related questions

54 votes
54 votes
6 answers
2
Kathleen asked Sep 29, 2014
21,137 views
The number of equivalence relations of the set $\{1,2,3,4\}$ is$15$$16$$24$$4$
42 votes
42 votes
2 answers
3
27 votes
27 votes
4 answers
4
Kathleen asked Sep 29, 2014
6,708 views
A polynomial $p(x)$ is such that $p(0) = 5, p(1) = 4, p(2) = 9$ and $p(3) = 20$. The minimum degree it should have is$1$$2$$3$$4$