Take a set of n distinct numbers.
How many permutations of this set with exactly one local maximum
are there?
Provide a proof of the formula you've derived.
(In reply to
not sure I understand by Steven Lord)
53124 has two local maxima, one at either end; the problem asks us to count only those permuations that have exactly one local maximum.
51324 has three local maxima, with one now also in the middle.
The local maximum can be at an end.
The absolute maximum must be the only local maximum allowed in order to be counted. Steve Herman's solution agrees. The absolute maximum can be anywhere; use it as your starting sequence. Each remaining number must be either on the left or right of that number and there's no choice as to where each number must fall; each new number must be in size place on whichever side it is placed. Since there are n-1 numbers besides the absolute maximum, and each has two choices on which side it's to go, there are 2^(n-1) ways of doing this, starting with the absolute maximum on the left and decreasing from there to starting with the abs. max on the right with all the others increasing until it.
|
|
Posted by Charlie
on 2018-10-30 17:47:15 |
re: not sure I understand
