Cyclic permutations realized by signed shifts (Q2448249): Difference between revisions

Let \(X\) be a linearly ordered set, \(f:X\to X\) be a map and \(n\) be a non-negative integer. If there are no repetitions among the first \(n\) elements of the sequence \(\{f^i(x)\}_{i\geqslant0}\) then the pattern of length \(n\) of \(f\) at \(x\) is \(\text{Pat}(x,f,n)=\text{st}(x,f(x),\ldots,f^{n-1}(x))\), where st is the reduction operation that outputs the permutation of \([n] =\{1, 2, \dots , n\}\) whose entries are in the same relative order as \(n\) entries in the input. An element \(x\in X\) is an \(n\)-periodic point of \(f\) if \(f^n(x)=x\) but \(f^i(x)\neq x\) for \(1\leqslant i<n\). If \(x\) is an \(n\)-periodic point, the permutation \(\text{Pat}(x, f, n)\) is denoted by \(\Pi(x, f)\) and is called the periodic pattern of \(f\) at \(x\). Let \(\mathcal{P}_n(f) = \{\Pi(x, f) : x \in X~ \text{is an } n\text{-periodic point of}~ f\}\) and \(\mathcal{P}(f)=\bigcup_{n\geqslant0}\mathcal{P}_n(f)\). Moreover, let \(p_n(f)=\frac{|\mathcal{P}_n(f)|}{n}\). Let \(k\geqslant2\) be fixed, and let \(\mathcal{W}_k\) be the set of infinite words \(s = s_1s_2\ldots\) over the alphabet \(\{0, 1, \ldots , k-1\}\). Let \({}<_{\text{lex}}\) denote the lexicographic order on these words. Put \(\bar{s_i}=k-1-s_i\). Fix \(\sigma = \sigma_0\sigma_1\ldots \sigma_{k-1}\in\{+,-\}^k\). Let \(T^+_\sigma = \{t : \sigma_t = +\}\), \(T^-_\sigma = \{t : \sigma_t = -\}\) and define \(\Sigma'_\sigma:(\mathcal{W}_k,{}<_{\text{lex}})\to(\mathcal{W}_k,{}<_{\text{lex}})\) by \(\Sigma'_\sigma(s_1s_2s_3s_4\ldots)=s_2s_3s_4\ldots\) whenever \(s_1\in T^+_\sigma\) and \(\bar{s_2}\bar{s_3}\bar{s_4}\dots\), otherwise. Let \(\prec_\sigma\) be the linear order on \(\mathcal{W}_k\) defined by \(s = s_1s_2s_3\dots \prec_\sigma t_1t_2t_3\dots = t\) if \(s_1<t_1\), or \(s_1=t_1\in T^+_\sigma\) and \(s_2s_3\dots \prec_\sigma t_2t_3\dots\), or \(s_1=t_1\in T^-_\sigma\) and \(t_2t_3\dots \prec_\sigma s_2s_3\dots\). The signed shift is then the map \(\Sigma_\sigma : (\mathcal{W}_k,\prec\sigma)\to(\mathcal{W}_k,\prec_\sigma)\) defined by \(\Sigma_\sigma(s_1s_2s_3s_4\ldots) = s_2s_3s_4\dots\). Let \(\mathcal{S}_n\) denote the set of permutations of \([n]\). We say that \(\tau\in\mathcal{S}_n\) contains \(\rho\in\mathcal{S}_m\) if there exist indices \(i_1<i_2<\ldots<i_m\) such that \(\text{st}(\tau_{i_1},\tau_{i_2},\ldots,\tau_{i_m})=\rho_1\rho_2\ldots\rho_m\). Otherwise, we say that \(\tau\) avoids \(\rho\). The set of permutations avoiding \(\rho\) is denoted by \(\text{Av}(\rho)\). A set of permutations \(\mathcal{A}\) is called a (permutation) class if it is closed under pattern containment. Given classes \(\mathcal{A}_0,\mathcal{A}_1, \ldots,\mathcal{A}_{k-1}\), their juxtaposition, denoted by \([\mathcal{A}_0,\mathcal{A}_1, \ldots,\mathcal{A}_{k-1}]\), is the set of permutations that can be expressed as concatenations \(\alpha_0\alpha_1\ldots\alpha_{k-1}\) where \(\text{st}(\alpha_t)\in\mathcal{A}_t\) for all \(0\leqslant t< k\). Let \(\mathcal{S}_\sigma\) be the juxtaposition \([\mathcal{A}_0,\mathcal{A}_1, \ldots ,\mathcal{A}_{k-1}]\) where, for \(0\leqslant t< k\), \(\mathcal{A}_t\) is \(\text{Av}(21)\) if \(\sigma_t=+\) and \(\text{Av}(12)\), otherwise. Let \(\mathcal{S}_n^\sigma=\mathcal{S}^\sigma\cap \mathcal{S}_n\). The set of cyclic permutations in \(\mathcal{S}_n\) (respectively, \(\mathcal{S}^\sigma\), \(\mathcal{S}^\sigma_n\)) is denoted by \(\mathcal{C}_n\) (respectively, \(\mathcal{C}^\sigma\), \(\mathcal{C}^\sigma_n\)). For a permutation \(\pi=\pi_1\pi_2\ldots\pi_n\) in one-line notation \(\hat{\pi}\) is \((\pi_1,\pi_2,\ldots,\pi_n)\) in cyclic notation. The authors give an outstanding proof to show that for a \(\sigma\in\{+,-\}^k\) with \(\sigma\neq -^k\), \(\pi\in\mathcal{P}(\Sigma_\sigma)\) if and only if \(\hat{\pi}\in\mathcal{C}^\sigma\). Moreover, it is shown that if \(\sigma=-^k\) then \(\pi\in\mathcal{P}_n(\Sigma_\sigma)\) implies that \(\hat{\pi}\in\mathcal{C}_n^\sigma\) and the converse holds if \(n\neq 2~\bmod 4\). It is also proved that \(p_n(\Sigma_{+-})=\frac{1}{2n}\sum_{d|n,~d~\text{odd}}\mu(d)2^{\frac{n}{d}}\), where \(\mu\) is the Möbius function. Let \(k\)-shift be the map \(\Sigma_k= \Sigma_\sigma\), where \(\sigma=+^k\). The author give some recursive formulas for \(p_n(\Sigma_k)\) for \(n\geqslant2\). Similar facts concerning the reverse \(k\)-shift map \(\Sigma_k^-= \Sigma_\sigma\), where \(\sigma=-^k\) are also given. In the last short section of the paper, using the formulas that the authors have found for the number of periodic patterns of the maps \(\Sigma_{+-}\), \(\Sigma_k\) and \(\Sigma_k^-\), they enumerate the number of cyclic permutations that avoid some certain patterns.