Question

Calculate in recursion the number of permutations of the numbers 1..N in which each number is greater than all those to its left or smaller than all those to its left.

Answer 1

In the recursive definition, we have to represent the number of permutations of the N numbers in terms of number of permutations of M numbers where M should be less than N. Also, we have to provide a base case to stop the recursion from going on forever.

SOLUTION we are numbers will be equal to 2. P(1) similar to the above case when N=2, for Let PCN) denote the number of permutations of N numbers in which no two numbers are equalo If N=1, P(N) = 1 as there is only I way to permute just one number. If N=2, first lets choose which of the two numbers will take the leftmost spot (assuming arranging numbers foom left to right ). Since we have 2 numbers, we have 2 options for the leftmost number. Irrespective of the number we choose, we have 1 number left to be arranged on the right which can be done in P(1) = 1 way(s). Finally by the fundamental principle of counting, number of permutations of two different natural number N, we will have N every options for choosing the leftmost digit and for the N numbers chosen, the remaining any of

(N-1) numbers can be arranged to the right in P(N-1) ways. By fundamental principle of the total number of permutations of N distinct numbers turns out to be equal P(N) = NxP(N-1), with as the base case. counting to P(1) = of Using the above a analysis, the number of permutatione the numbers 1,...,N , where each number is greater than those to its left or smaller than those to its left (this condition makes sure all N numbers are distinct), will be equal to P(N) = NX PCN-1), with a P(1) = as the base case. Above is the required recursive expression which will be true for every natural number N.