solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看96次
Constraining Strong c-Wilf Equivalence Using Cluster Poset Asymptotics. (arXiv:1807.04921v1 [math.CO])
来源于:arXiv
Let $\pi \in \mathfrak{S}_m$ and $\sigma \in \mathfrak{S}_n$ be permutations.
An occurrence of $\pi$ in $\sigma$ as a consecutive pattern is a subsequence
$\sigma_i \sigma_{i+1} \cdots \sigma_{i+m-1}$ of $\sigma$ with the same order
relations as $\pi$. We say that patterns $\pi, \tau \in \mathfrak{S}_m$ are
strongly c-Wilf equivalent if for all $n$ and $k$, the number of permutations
in $\mathfrak{S}_n$ with exactly $k$ occurrences of $\pi$ as a consecutive
pattern is the same as for $\tau$. In 2018, Dwyer and Elizalde conjectured
(generalizing a conjecture of Elizalde from 2012) that if $\pi, \tau \in
\mathfrak{S}_m$ are strongly c-Wilf equivalent, then $(\tau_1, \tau_m)$ is
equal to one of $(\pi_1, \pi_m)$, $(\pi_m, \pi_1)$, $(m+1 - \pi_1, m+1-\pi_m)$,
or $(m+1 - \pi_m, m+1 - \pi_1)$. We prove this conjecture using the cluster
method introduced by Goulden and Jackson in 1979, which Dwyer and Elizalde
previously applied to prove that $|\pi_1 - \pi_m| = |\tau_1 - \tau_m|$. A
consequenc 查看全文>>