Simple permutations for all $k$

32 Views Asked by At

a)How many are the simple permutations of the numbers $ 1,2, ..., n $ in which the k-th element is less than $ k + 4 $, for every $ k $?

b)How many are the simple permutations of the numbers $ 1,2, ..., n $ where the kth element is greater than $ k-3 $, for every $ k $?

Could someone give me a hint? I really didn't understand the statement

1

There are 1 best solutions below

3
On BEST ANSWER

Hint: $1$ must be mapped to $1,2,3$ or $4$. So there are $4$ possibilities.

$2$ must map to $1,2,3,4$ or $5$, less the element that $1$ was mapped to. So there are ? possibilities.

etc...

There will only be $4$ elements for $n-3$ to map to.

There will only be $3$ elements for $n-2$ to map to.

There will only be $2$ elements for $n-1$ to map to.

There will only be $1$ elements for $n$ to map to.

$6 \times 4^{n-3}$.