All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
One-peak sets (Posted on 2018-10-30) Difficulty: 3 of 5
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.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
re: not sure I understand | Comment 3 of 4 |
(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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information