Problem 56250. Counting Permutations

Dyuman Joshi

8 solvers

1 likes

Solve

Solve Later

In the permutations of the numbers 1 to n, count the number of permutations in which exactly m elements are greater than the previous element.
Example - 
n=4;
m=2;
%permutations in which exactly 2 numbers are greater than the previous element
y=[1 3 2 4
   1 4 2 3
   1 2 4 3
   2 3 1 4
   4 1 2 3
   2 4 1 3
   2 1 3 4
   1 3 4 2
   2 3 4 1
   3 1 2 4
   3 4 1 2]
%11 permutations
out=11;
n=3;
m=0;
%permutations in which exactly 0 numbers are greater than the previous element
y=[3 2 1];
%only 1 permutation
out=1;
n=3;
m=1;
%permutations in which exactly 1 numbers are greater than the previous element
y=[1 2 3
   1 3 2
   2 3 1
   2 1 3];
%4 permutations
out=4;
n=3;
m=2;
%permutations in which exactly 2 numbers are greater than the previous element
y=[1 2 3];
%only 1 permutation
out=1;
The task, here, is to calculate the output for all values of m (0 to n-1) given a natural number n, and output it in a row vector.
Check test case #1 for restricted functions.