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 that 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 probelm 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.

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 that 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 probelm 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.

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 that 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 probelm 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$?

Thanks.

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 that 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 probelm 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 are even and all its interior local maxima are odd. Is it true (as I believe) that $p_n\to\infty$ p_n\to 0$ as $n\to\infty$? Can one be more precise about the behavior of $p_n$ as $n\to\infty$?

Thanks.

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 that 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 probelm 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 are even and all its interior local maxima are odd. Is it true (as I believe) that $p_n\to\infty$ as $n\to\infty$? Can one be more precise about the behavior of $p_n$ as $n\to\infty$?

Thanks.