PhD Admissions Written Test (Basic)

Question

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 ________________________

Comments

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.