Decorated permutations and subset permutations

Question

Decorated permutations are defined as permutations where the fix-points come in two colors (say $\overline{\cdot}$ and $\underline{\cdot}$). For example, the 16 decorated permutations of length 3 are $$\overline{1}\overline{2}\overline{3},\underline{1}\overline{2}\overline{3},\overline{1}\underline{2}\overline{3},\overline{1}\overline{2}\underline{3},\underline{1}\underline{2}\overline{3},\underline{1}\overline{2}\underline{3},\overline{1}\underline{2}\underline{3},\underline{1}\underline{2}\underline{3},$$ $$\overline{1}32,\underline{1}32,\hspace{10pt} 21\overline{3},21\underline{3},\hspace{10pt} 231,\hspace{10pt} 312,\hspace{10pt} 3\overline{2}1,3\underline{2}1\ .$$ They play an important role in the context of the positive Grassmannian and are in bijection with many other combinatorial objects such as bounded affine permutations, Grassmann necklaces, Le-diagrams, positroids and equivalence classes of plabic graphcs, see, for example, here or here. These combinatorial objects have certainly been studied in detail in recent years. Their total number of clearly $\sum_{k=0}^n F(n,k)2^k$, where $F(n,k)$ denotes the number of permutations of length $n$ with $k$ fixed-points.

When looking for these on the OEIS, I saw that neither of the above names was found there, whilst subset permutations are found there as A000522. These are, given a set with $n$ elements, obtained by choosing $k$ elements among them, and then permute these $k$ elements, giving in total $\sum_{i=0}^{n} {n \choose k}k! = \sum_{k=0}^{n} n!/k!\ $. For example, for $n=3$, we obtain the following 16 elements: $$-,1,2,3,12,21,13,31,23,32,123,132,213,231,312,321.$$

I claim (and quickly prove below) that subset permutations also belong to the list of combinatorial objects in bijection with the above.

My questions are now

Have the later already appeared in this context?

and

Is the equality $\sum_{k=0}^n F(n,k)2^k = \sum_{k=0}^{n} n!/k!$ otherwise directly implied?

Construction of the bijection:

Take a subset permutation. This is, take a set of $k$ element in $\{1,\ldots,n\}$ together with a permutation of these. Consider this as a permutation of length $n$ with the remaining $n-k$ elements being fixed-points. Now label these $n-k$ fixed-points by $\underline{\cdot}$ and the additional fixed-points from the permutation of the $k$ elements by $\overline{\cdot}$. Than this is a bijection from subset permutations to decorated permutations.

For example, $143768$ as a subset permutation of $\{1,\ldots,8\}$ is mapped to $\overline{1}\underline{2}43\underline{5}76\overline{8}$. Also, the preimages of the 16 decorated permutations at the beginning are $$123,23,13,12,3,2,1,-,132,32,213,21,231,312,321,31.$$

Answer 1

Here is a direct proof for the formula via generating functions.

Using the formula for derrangement numbers, we have $$\begin{split} F(n,k)=&\binom nk\cdot !(n-k)\\ =&\frac{n!}{k!}\cdot [x^{n-k}]\ \frac{e^{-x}}{1-x}, \end{split}$$ where $[x^d]$ is the operator of taking the coefficient of $x^d$.

Then $$\begin{split} \sum_{k=0}^{n} F(n,k)\cdot 2^k = & \sum_{k=0}^{n} 2^k\frac{n!}{k!} [x^{n-k}]\ \frac{e^{-x}}{1-x} \\ = & n!\sum_{k=0}^{n} [x^k]\ e^{2x}\cdot [x^{n-k}]\ \frac{e^{-x}}{1-x} \\ = & n!\cdot [x^n]\ \frac{e^{x}}{1-x}\\ = &\sum_{k=0}^n \frac{n!}{k!}. \end{split}$$

Answer 2

Max's answer is neat in using $e^{2x}\frac{e^{-x}}{1-x}=\frac{e^x}{1-x}$. We offer one approach without generating functions. To this end, let $f_n:=\sum_{k=0}^n\frac1{k!}$ and $g_n:=\sum_{k=0}^n\frac{2^k}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}$. Assume empty sums to be $0$. Clearly, $f_{n+1}-f_n=\frac1{(n+1)!}$. On the other hand, we have \begin{align} g_{n+1}-g_n &=\sum_{k=0}^{n+1}\frac{2^k}{k!}\sum_{j=0}^{n+1-k}\frac{(-1)^j}{j!} -\sum_{k=0}^{n+1}\frac{2^k}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!} \\ &=\sum_{k=0}^{n+1}\frac{2^k}{k!}\frac{(-1)^{n+1-k}}{(n+1-k)!} =\frac{(-1)^{n+1}}{(n+1)!}\sum_{k=0}^{n+1}\binom{n+1}k(-2)^k \\ &=\frac{(-1)^{n+1}}{(n+1)!}(-1)^{n+1}=\frac1{(n+1)!}. \end{align} Therefore, $f_{n+1}-f_n=g_{n+1}-g_n$. Since $f_0=g_0=1$, it follows $f_n=g_n$ and $n!f_n=n!g_n$. Obviously, $n!f_n=\sum_{k=0}^n\frac{n!}{k!}$ and $$n!g_n=\sum_{k=0}^n2^k\frac{n!}{k!}\sum_{j=0}^{n-k}\frac{(-1)^j}{j!}=\sum_{k=0}^n2^k\binom{n}k\cdot !(n-k)=\sum_{k=0}^nF(n,k)2^k.$$