About Warm-ups Problems News

Problem 11

Posted 06/11/2015
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

We say a permutation $\sigma=\sigma_{1}\sigma_2\cdots\sigma_n$ is log-concave if for any $2\le k\le n-1$, $\sigma_{k-1}\sigma_{k+1}<\sigma_k^2$.

We say a permutation $\sigma=\sigma_{1}\sigma_2\cdots\sigma_n$ is weakly log-concave if for any $2\le k\le n-1$, $\sigma_{k-1}\sigma_{k+1}\le\sigma_k^2$.

For example, $\sigma=1\ 2\ 4\ 3$ is not log-concave but weakly log-concave.

$a(n)$ is the number of log-concave permutations of length $n$.
$b(n)$ is the number of weakly log-concave permutations of length $n$.

Find $a(n)$ and $b(n)$.




Back to top