From Permutation Patterns to the Periodic Table

⁽The above abstract has been extracted by the translator from the original article (L. Pudwell, From Permutation Patterns to the Periodic Table, Notices of the American Mathematical Society, 67 994–1001.))

Abstract: Permutation patterns is a burgeoning area of research with roots in enumerative combinatorics and theoretical computer science. This article first presents a brief overview of pattern avoidance and a survey of enumeration results that are standard knowledge within the field. Then, we turn our attention to a newer optimization problem of pattern packing. We survey pattern packing results in the general case before we consider packing in a specific type of permutation that leads to a new and surprising connection with physical chemistry. Note that the original paper has published in ``Notices of the American Mathematical Society, 67, Number 7, 994-1001" and we have translated it into Farsi. This is just an extended abstract for Journal of Mathematics and Society.
 
 
1. Introduction
Let $S_k $ be the set of all permutations on $[k]=\{1, 2,\ldots,k\}$. Given $\pi \in S_k$ and $\rho \in S_l$, we say that $\pi$ contains $\rho$ as a pattern if there exist $1\leq i_1<i_2<\cdots<i_{\ell}\leq k$‎ such that $\pi_{i_a}\leq \pi_{i_b}$‎ if and only if $\rho_a\leq \rho_b$. In this case we say that $\pi_{i_1}\ldots \pi_{i_{\ell}}$‎ is order-isomorphic to $\rho$, and that $\pi_{i_1}\ldots \pi_{i_{\ell}}$‎ is an occurrence or a copy of $\rho$ in $\pi$. If $\pi$ does not contain $\rho$, then we say that $\pi$ avoids $\rho$.
 
The definition of pattern containment may be made more visual by considering the plot of $\pi$. In particular, for $\pi=\pi_1\pi_2\cdots \pi_k\in S_k$, the plot of $\pi$ is the graph of the points $(i‎,‎\pi_i)$ in the Cartesian plane.
 
Of particular interest are the sets $S_k(\rho)=\{ \pi \in S_k \vert \pi ~ avoids~ \rho\}$. For example, 
‎\[S_4(123)=\{1432‎, ‎2143‎, ‎2413‎, ‎2431‎, ‎3142‎, ‎3214‎, ‎3241,‎ 3412‎, ‎3421‎, ‎4132‎, ‎4213‎, ‎4231‎, ‎4312‎, ‎4321\}‎\]
and $\pi= 43512\in S_5(123)$‎ since there is no increasing subsequence of length 3 in $\pi$.

 
2. Main Results
Much of the existing literature in permutation patterns studies the quantity $s_k(\rho)=\vert S_k(\rho)\vert$ for various patterns $\rho$.
 
Starting with the simplest case, it is immediate that $s_k(1)=0$ if $k\geq 1$ since each digit of a nonempty permutation is a copy of the pattern 1. We also have that $s_k(\rho)=\vert S_k(\rho)\vert$ for $k\geq 0$, since the unique permutation of length $𝑘$ avoiding 12 (resp., 21) is $J_k$ (resp., $I_k$). For more information, please refer to the original paper.
 
Rather than focusing on packing in all permutations, the author of the original paper in the rest of the paper focus on packing patterns into permutations with extra restrictions. This family of packing problems will provide a new link between permutations and physical chemistry.
Definition 2.1. Permutation $\pi$ is an alternating permutation if ‎\[\pi_1 <\pi_2>\pi_3<\pi_4\cdots.\] Alternating permutations are also known as zig-zag permutations or up-down permutations.
Theorem 2.2. The maximum number of copies of $123$ in an alternating permutation of length $k$ is given by
‎\[ν(123‎, ‎\widehat{I_k})=\lbrace
\dfrac{(k-2)(k^2-4k+6)}{6}     k‎~is ~ even‎,
\dfrac{(k-1)(k-2)(k-3)}{6}         k~is~‎ odd‎.\rbrace 
‎‎\]
‎
3. Conclusion
This connection between pattern packing and physical chemistry is striking even to long-time permutation patterns researchers. Similarly, the quasi-polynomial sequence obtained for $\nu(123‎, ‎\widehat{I_k})$ had no previous interpretation in the literature other than as a sequence of atomic numbers. What, if any, chemical interpretation is there for $\nu(123‎, ‎\widehat{I_k})$ when $k>10?$ What other chemical or physical structures can be described in terms of pattern packing or pattern avoidance? Are there other combinatorial structures that give alternate ways to generate the sequences of atomic numbers of particular groups of chemical elements? The variety of applications of permutation patterns has grown tremendously in recent decades, and modeling electron orbitals can now be added to the list.