in Others retagged by
64 views
0 votes
0 votes
Consider all permutations of the 16 numbers from 1 to 16 which satisfy the property that every number is placed such that it is either bigger than ALL numbers preceding it or it is smaller than ALL numbers preceding it. The number of such permutations is ________________________
in Others retagged by
64 views

1 comment

There would be $2$ such permutations i.e. $(1,2,...,16)$ and $(16,15,...,1)$

Your question is nothing but to find the number of strictly increasing or strictly decreasing functions $f: \{1,2,…,16\} \rightarrow \{1,2,…,16\}.$

$\implies$ Number of strictly increasing functions $f: \{1,2,…,n\} \rightarrow \{1,2,…,m\}$ is $\binom{m}{n}$ and

Number of strictly decreasing functions $f: \{1,2,…,n\} \rightarrow \{1,2,…,m\}$ is $\binom{m}{n}.$

Here, $m=n=16$ and so, Number of strictly increasing functions = $\binom{16}{16} = 1$ and Number of strictly decreasing functions = $\binom{16}{16} = 1$ and so total = $2$

Question would be interesting if they replace “bigger” with “bigger or equal” and lesser with “lesser or equal” (probably, you would not call it "permutation") then you need to find :

$\implies $ Number of nondecreasing functions $f: \{1,2,…,n\} \rightarrow \{1,2,…,m\}$ is $\binom{m+n-1}{m-1}$ and

Number of nonincreasing functions $f: \{1,2,…,n\} \rightarrow \{1,2,…,m\}$ is $\binom{m+n-1}{m-1}.$

So, in this case $(m=n=16)$, Number of nonincreasing or nondecreasing functions $f: \{1,2,…,16\} \rightarrow \{1,2,…,16\}$ is:

 $\binom{16+16-1}{16-1} + \binom{16+16-1}{16-1} \ – \ 16$. The subtraction of $16$ denotes there are $16$ permutations which are both nonincreasing and nondecreasing i.e. $(1,1,…,1),(2,2,…,2),…(16,16,…,16).$

Finding formula for such strictly increasing or nondecreasing functions has already been asked in both ISI and GATE exams. So, you could see those derivations for such formulae.
2
2

Please log in or register to answer this question.

Related questions