This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function that assigns a number to each face and satisfying certain conditions.


The theory has found beautiful applications, but it has one limitation: discrete Morse functions are hard to find, unlike the smooth case where smooth Morse functions are a dime a dozen. That made me think that maybe there aren't too many such discrete Morse functions. So naturally one can ask, really, how many Morse functions are out there on a given triangulated space. 


The present question deals with the simplest triangulated space, namely a line segment divided into $n$-subintervals. The problem of counting the combinatorial Morse functions on this triangulated space reduces to the following purely combinatorial problem.


Consider the group $S\_{2n+1}$ of permutations of the set 


$$ V\_n:=\lbrace 0,1,\dotsc,2n\rbrace. $$


A point $i\in V\_n$ is called an *interior point* if $i\neq 0,2n$. An interior point $i\in V\_n$ is a *local minimum* of a permutation $\phi\in S\_{2n+1}$ if


$$ \phi(i-1)> \phi(i) <\phi(i+1). $$


A *local maximum* is defined in a similar fashion. Here is now the question.



> 
> Denote by $p\_n$ the probability that
>  a random permutation of $S\_{2n+1}$ has
>  the property that all its **interior**
>  local minima (**if any**) are even and all its
>  **interior** local maxima (**if any**) are odd. Is it
>  true (as I believe) that
>  $p\_n\to 0$ as $n\to\infty$? Can
>  one be more precise about the
>  behavior of $p\_n$ as $n\to\infty$? 
> 
> 
> 


For example, when $n=1$ the permutations of $\lbrace0,1,2\rbrace$ satisfying the above constraints are


$$ (0,1,2), (2,1,0), (0,2,1), (1,2,0). $$


Hence $p\_1=\frac{2}{3}$.


Thanks.



Combinatorial Morse functions and random permutations
The suggestion of Karl Waugh can be fixed. Let us call a permutation
*nice* if it satisfies the conditions of the problem. Let $a\_0
a\_1\cdots a\_{2n}$ be a permutation of $V\_n$. There are six possible
orderings of the numbers $a\_0, a\_1, a\_2$, all equally likely. Two of
these orderings are incompatible with niceness, so there is a $2/3$
probability of compatibility. Similarly there is a $2/3$ probability,
independent from the values of $a\_0,a\_1,a\_2$, that $a\_3,a\_4,a\_5$ are
compatible with niceness. Continuing this argument gives an upper
bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a
permutation of $0,1,\dots,2n$ to be nice.


**A further thought.** Alternating permutations are nice. The number
$E\_n$ of alternating permutations of $1,2,\dots,n$ (an Euler number)
satisfies $E\_n\sim C(2/\pi)^nn!$. If $f(2n+1)$ denotes the number of
nice permutations of $V\_n$, then this suggests that the limit
 $$ L=\lim\_{n\to \infty} \left(
 \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)} $$
exists. The observations above show that then
 $$ \frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac
 23\right)^{1/3}= 0.8735\cdots. $$
It would be interesting to determine this limit. The upper bound can
be made arbitrary close to $L$ by looking at blocks of length $k$
(rather than of length three) as $k\to\infty$. Doing it for $k=10$ yields (modulo computational error) an upper bound of $L\leq (405581/10!)^{1/5} = 0.64515\cdots$. 


