Number of permutations Is there some easy way to compute number of particular permutations? Namely let $S_i$ be the number of permutations $(a_1,...,a_n)$, $\{a_1,\ldots,a_n\}=\{1,...,n\}$, satisfying the following conditions:


*

*$a_i=n$ for some $i\in \{1,\ldots,n\}$.

*$a_1<a_2<\ldots <a_i$.


Compute $\sum_{i=1}^n S_i$. 
 A: 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). 
