A permutation $\psi: S \rightarrow S$, where $S = \{1,2,\dots,n\}$, is considered $\textit{descriptive}$ if for every $k < n$, the image under $\psi$ of $\{1,2,\dots,k\}$ is not simply $\{1,2,\dots,k\}$.
Determine the total number of $\textit{descriptive}$ permutations for the set $\{1,2,3,4,5,6\}$.
$\textbf{Analytical Journey:}$
-
$\textbf{Initial Observation:}$ It was identified that a critical condition for a permutation to be well-shuffled is $\psi(a_1) \neq a_1$. This observation suggested a strategy of partitioning based on the placement of elements, leading to an exploration of permutations excluding fixed points.
-
$\textbf{Principle of Inclusion-Exclusion Strategy:}$ The Principle of Inclusion-Exclusion was considered to remove permutations that are not well-shuffled from the total count of $15!$. The complexity arose in correctly identifying and subtracting permutations by their fixed points to avoid double-counting.
-
$\textbf{Recurrence Relation Formulation:}$ A recurrence relation approach was investigated to express the number of well-shuffled permutations for $n$ based on smaller instances. The challenge was in developing a relationship that incorporates the increasing complexity of the well-shuffled condition as $n$ grows.
-
$\textbf{Investigation of Generating Functions:}$ Generating functions were explored as a potential method to encapsulate the enumeration problem. The main hurdle was devising a function that naturally excluded permutations that did not meet the well-shuffled criterion, and translating this condition into mathematical terms was particularly challenging.
-
$\textbf{Pattern Identification through Smaller Cases:}$ By manually enumerating cases for smaller $n$, an effort was made to uncover patterns that might lead to a method applicable to larger instances. Although this process provided insight, it did not lead to an easily scaled method.
Best Answer
Let $a_n$ be the number of descriptive permutations on $\{1,\dots,n\}$. You can prove that, for all $n\ge 1$, $$ a_n=n!-\sum_{k=1}^{n-1}k!\cdot a_{n-k}\tag1 $$ This recurrence relation allows you to compute the entire list $a_1,a_2,a_3,a_4,a_5, a_{6}$ one at a time. Since $6$ is small enough, this is doable by hand.
The sequence $a_n$ is in OEIS, where the above recurrence is given: https://oeis.org/A003319.
Proof of (1): For each $k\in \{1,\dots,n-1\}$, let $E_k$ be the set of permutations, $\phi$, with the property that $\phi(\{1,\dots,k\})=k$, but $\phi(\{1,\dots,\ell\})\neq \{1,\dots,\ell\}$ for any $\ell>k$. In words, $E_k$ is the set of permutations for which the largest prefix preserved by the permutation is $\{1,\dots,k\}$.
Note that the sets $E_1,\dots, E_{n-1}$ are disjoint, and every permutation which is not well-mixed lies in $E_k$ for some $k$. Therefore, $$ a_n=n!-\sum_{k=1}^{n-1}|E_k| $$ All that remains is to prove $|E_k|=k!\cdot a_{n-k}$. Given $\phi\in E_k$, certainly $\phi(\{1,\dots,k\})=\{1,\dots,k\}$, so there are $k!$ ways to choose the list $(\phi(1),\dots,\phi(k))$. Furthermore, the list $(\phi(k+1),\phi(k+1),\dots,\phi(n))$ has the property that, for all $\ell\in \{k+1,\dots,n\}$, that $$ \phi(\{k+1,k+2,\dots,\ell\})\neq \{k+1,k+2,\dots,\ell\}.\tag2 $$ Indeed, if an $\ell$ existed satisfying the above, then we would have $\phi(\{1,\dots,\ell\})=\{1,\dots,\ell\}$, contradicting the definition of $E_k$. Now, if we define $\tilde\phi:\{1,\dots,n-k\}\to \{1,\dots,n-k\}$ by $$ \tilde\phi(x)=\phi(x+k), $$ then we see that $(2)$ is equivalent to $\tilde\phi$ being well-mixed. Therefore, there are $a_{n-k}$ to choose the list $(\phi(k+1),\dots,\phi(n))$. This completes the proof that $|E_k|=k!\cdot a_{n-k}$.