7
$\begingroup$

The following question is motivated by my research.

Let's consider a permutation $\sigma$ of the set $\{1, \ldots, n\}$. We define an element $i \in \{1, \ldots, n\}$ to be locally minimal for $\sigma$ if it satisfies the conditions $i \leq \sigma(i)$ and $i \leq \sigma^{-1}(i)$. I am interested in studying the total number of locally minimal elements.

For any fixed point $i$ where $\sigma(i) = i$, it is considered a locally minimal element for $\sigma$.

The values of this function range between 1 (since $i=1$ is locally minimal) and $n$ (the total number of locally minimal elements is only equal to $n$ when $\sigma$ is the identity permutation). It is worth noting that each cycle in the cycle decomposition of $\sigma$ generates at least one locally minimal element.

My question is whether this function, or a related function, is known and has been previously studied. I attempted to locate this function on the website https://www.findstat.org/, but I was unable to find any relevant information.

$\endgroup$
5
  • 1
    $\begingroup$ Do you have some sample values? (Also, while I think that talking about motivation is good, "the following question is motivated by my research" really doesn't give information about motivation, and so might be better removed.) $\endgroup$
    – LSpice
    Commented Jul 13, 2023 at 15:54
  • 1
    $\begingroup$ Each cycle from cycle decomposition generates its own number of local minimums. For example m((1,2,3,4))=1, m((1,3,2,4))=2, m((1,3,2)(4))=2, m((1,2),(3),(4))=3. $\endgroup$
    – Petya
    Commented Jul 13, 2023 at 16:03
  • 2
    $\begingroup$ I wrote a quick Magma program to calculate the number of permutations on n symbols with exactly 2 local minima, and got the following results: {(2,1),(3,3),(4,13),(5,56),(6,236),(7,976),(9,3984)}. Putting this sequence into OEIS does not generate any matches. So maybe this is a green field... $\endgroup$ Commented Jul 15, 2023 at 13:16
  • 1
    $\begingroup$ Note that OEIS sequence A346317 is related. It is the number of permutations with exactly two cycles, each of which has a single local minimum. $\endgroup$ Commented Jul 15, 2023 at 20:47
  • 2
    $\begingroup$ Better reference here: A000431. Looks like local minima may be called "valleys", or intermediary peaks. $\endgroup$ Commented Jul 15, 2023 at 21:09

0

You must log in to answer this question.

Browse other questions tagged .