All permutation of a set including the ones where some elements of the set are missing

Question

I have following elements: $A$, $B$, $C$, $D$, $E$ and I want to find all permutations, including the ones where some elements from the set are not included in the permutation (For example $(C, D)$ or $(E, A, C)$). When all elements are respected in the permutations, then the answer would be simply $5!$. But how can I find the 'true' number of permutations?

Answer 1

Let $f(n)$ be the number of possible words of any length over the alphabet $\{1,\dotsb, n\}$ where each letter appears at most once(including the empty word). Then $$ f(n)=\sum_{i=0}^n\frac{n!}{(n-i)!}=n!\sum_{i=0}^n\frac{1}{i!} $$ In your case we want $f(5)$ or $f(5)-1$ if we exclude the empty word. It turns out that we can compute a closed form in general. Indeed, observe that

Note that $$ \begin{align} 0\leq en!-f(n)&=n!\left(\frac{1}{(n+1)!}+\frac{1}{(n+2)!}+\frac{1}{(n+3)!}\dotsb\right)\\ &=\frac{1}{(n+1)}+\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}+\dotsb\\ &<\frac{1}{(n+1)}+\frac{1}{(n+1)^2}+\frac{1}{(n+1)^3}+\dotsb\\ &=1/n\leq1 \end{align} $$ So $f(n)=\lfloor{en!}\rfloor$. If you want to exclude the empty word subtract one.

Answer 2

If your total set has $n$ elements you can choose $i$ of them in $n \choose i$ ways, then put those $i$ in order in $i!$ ways, so the total you are looking for is $$\sum_{i=0}^n{n \choose i}i!=\sum_{i=0}^n\frac{n!}{(n-i)!}=e\Gamma(n+1,1)$$ where $\Gamma(n+1,1)$is the incomplete gamma function. For $n=5$ this is $326$