Simple permutations for all $k$

Question

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

What don't you understand about the statement? Suppose $n=10$. Can you give an example of a permutation that passes the given test? One that does not? — lulu, Dec 02 '19 at 12:24
@lulu how many are the simple permutations. I don't understand what he wants — Lambert macuse, Dec 02 '19 at 12:33
Well, you could ask for clarification from whomever set the problem. There is something called a Simple Permutation...but of course the writer here might intend something else (perhaps just an ordinary permutation). You should know if something like that might be the intent of the question. — lulu, Dec 02 '19 at 12:40
Just to stress: I would not say that that definition of a "simple permutation" is at all common or familiar. I had to look it up to confirm the definition, for instance. Again, it ought to be clear from the context behind the problem whether such a notion is likely to have been intended. If not, and if there is no other context, I'd guess they just meant "permutation". — lulu, Dec 02 '19 at 12:43
As another point: I have no idea how to solve the problem if this technical notion of "simple" is intended. I think even the enumeration of the simple permutations is difficult (see this for instance). If you are encountering this problem in a first course on combinatorics, I'd strongly suspect that the author just intends "permutation". — lulu, Dec 02 '19 at 12:54

Donald Splutterwit · Accepted Answer · 2019-12-02T12:38:46.113

1

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}$.

edited Dec 02 '19 at 12:38

answered Dec 02 '19 at 12:32

Would simple permutations be the same as combinations? – Lambert macuse Dec 02 '19 at 12:40
For a combination the order of the elements does not matter ... so the constraint would not make sense ? – Donald Splutterwit Dec 02 '19 at 12:44
Right!! I understand now! Thanks for the tip – Lambert macuse Dec 02 '19 at 12:48

1 Answers1