Edit: Slight mistake in the computation which trickled down.
First, let's count the number of $n$-tuples with with the property you describe. You know that $a_i$ is going to be. To select the previous $i-1$ elements, all you need is to select arbitrary $i-1$ elements from the remaining $n-1$ elements in your set, and place them in order. The remaining $n-i$ elements may be selected for $a_{i+1},\ldots,a_n$ arbitrarily. This gives $\binom{n-1}{i-1}(n-i)! = \frac{(n-1)!}{(i-1)!}$
Now, suppose you have two distinct $n$-tuples corresponding to the same $i$. Can they represent the same permutation? No: because two $n$-cycles represent the same permutation if and only if one can be obtained from the other by repeated cycling, $(a_1,\ldots,a_n) \to (a_2,\ldots,a_n,a_1) \to $ etc. Since both have $n$ in the same position in the cycle, the two $n$-tuples represent distinct permutations. So $S_i = \frac{(n-1)!}{(i-1)!}$.
So the number you want is $\sum_{i=1}^{n} S_i = \sum_{i=1}^n\frac{(n-1)!}{(i-1)!} = e\Gamma(n,1)-\Gamma(n)$ (thanks to PEV for the last equality).