Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations of the form a_1<a_2>a_3< >a_n

  1. Jul 27, 2009 #1
    I've been thinking about this one for over a week now. Does anyone have any smart way of counting the permutations of {1,2,3,...,n} that are of the form a_1< a_2 > a_3 < ... > a_n?

    You notice that there are (n-1) ways to choose the first elt. since the first choice cannot be n. And the complicated thing is that for an odd choice, if you choose the lowest possible elt., then the next choice cannot be the lowest poss elt. For even choices, if you choose the highest poss. elt., you cannot choose the highest elt. for the next choice. So, clearly thinking about this in terms of how many ways to choose individual elts. is probably not optimal. Can someone suggest another way of thinking about it? Thanks.
  2. jcsd
  3. Jul 28, 2009 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook