Total number of strings constructed by a set of $N$ characters. Let $S=\{s_1,\ldots,s_N\}$ be a set of $N$ characters. What is the total number of strings that could be constructed using elements of the above set, granted that strings may be of length at least $1$ and each character is used only once?
For instance, for $N=2$, i.e., $S=\{s_1,s_2\}$, the number of all possible strings is equal to $4$. That is, these strings are the following: $s_1$, $s_2$, $s_1s_2$, and $s_2s_1$. If I am not mistaken, for $N=3$, this number is equal to $15$.
How could I compute this number analytically for an arbitrary choice of $N$? I am a bit stuck on this, so thank you very much for any help in advance!
 A: Using the expression $\operatorname{T}(n)=\sum_{k=1}^n k!{n \choose k}$ provided by HowDoIMath above, we can rewrite it as a recursive function:
\begin{split}
\operatorname{T}(n+1) &= \sum_{k=1}^{n+1} k!{n+1 \choose k} = \sum_{k=0}^n (k+1)!{n+1 \choose k+1} =
\sum_{k=0}^n (k+1)!\frac{(n+1)!}{(k+1)!(n+1-k-1)!} \\
&= (n+1)\sum_{k=0}^n k!\frac{n!}{k!(n-k)!} = (n+1)\sum_{k=0}^n k!{n \choose k} = \\
&= (n+1)\sum_{k=1}^n k!{n \choose k} +(n+1) = (n+1)\operatorname{T}(n) + (n+1).
\end{split}
The recurrence equation $\operatorname{T}(n)=n \operatorname{T}(n-1)+n$, with $\operatorname{T}(1)=1$, has solution
$$
\operatorname{T}(n)=e\cdot n\cdot\Gamma(n,1),
$$
Where $\Gamma$ is the upper incomplete gamma function. I found this solution by messing around in Mathematica, but once you have it, it is easy enough to prove that is the solution, by showing that it satisfies the recurrence relation, using integration by parts, and testing the initial value.
Now
\begin{split}
\Gamma(n,1) &= \int_1^\infty t^{n-1}e^{-t}dt=\int_0^\infty t^{n-1}e^{-t}dt -\int_0^1 t^{n-1}e^{-t}dt \\
&= \Gamma(n,0)-\int_0^1 t^{n-1}e^{-t}dt = (n-1)!-\int_0^1 t^{n-1}e^{-t}dt,
\end{split}
using that $\Gamma(n,0)$ is the usual gamma function $\Gamma(n)$. So we arrive at
$$
\operatorname{T}(N)=e\cdot N!-e\cdot N\int_0^1 t^{N-1}e^{-t}dt.
$$
We still have to prove that this is equal to $\lfloor e\cdot N!-1 \rfloor$, as mentioned again by HowDoIMath, but at least it's part of the way!
A: I'll show that HowDoIMath's answer $T(n)$ is equivalent to $\lfloor e\cdot n!-1\rfloor$.
Rewrite $T(n)$ as $n!\binom{n}0+(n-1)!\binom{n}1+(n-2)!\binom{n}2+\ldots+(n-(n-1))!\binom{n}{n-1}$.
Divide by $n!$ to get: $$T(n)=n!(\tbinom{n}0+\tfrac1n\tbinom{n}1+\tfrac1{n(n-1)}\tbinom{n}2+\ldots+\tfrac1{n(n-1)\ldots2}\tbinom{n}{n-1})$$
$$\therefore\ T(n)=n!(1+1+\tfrac1{2!}+\tfrac1{3!}+\ldots+\tfrac1{(n-1)!})$$
Thus $T(n)=n!(e-\tfrac1{n!}-f(n))$ where $f(n)=\tfrac1{(n+1)!}+\tfrac1{(n+2)!}+\tfrac1{(n+3)!}+\ldots$
Expanding, $T(n)=e\cdot n!-1-n!f(n)$.
We already know that this is an integer, so all that remains is to show that $n!f(n)<1$.
$$n!f(n)=\tfrac1{n+1}+\tfrac1{(n+1)(n+2)}+\tfrac1{(n+1)(n+2)(n+3)}+\ldots$$
But $$e-2=\tfrac12+\tfrac1{2\cdot3}+\tfrac1{2\cdot3\cdot4}+\ldots<1$$
By the comparison test, for $n>1$ each term of $n!f(n)$ is smaller than the corresponding term in $e-2$. Therefore the series converges, and is less than $1$.
A: Sloane has the sequence: https://oeis.org/A007526
He provides this amazing looking closed form for the general expression:
$\lfloor e\cdot N!-1\rfloor$
I haven't checked it, and have no idea why it is true, but I believe I saw something similar for derangements at some point.
