4
$\begingroup$

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:

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

Compute $\sum_{i=1}^n S_i$.

  • 2
    @Jaska: For such problems, OEIS is very valuable. The set up you describe is fairly easy to code and once you have the values of $\sum_{i=1}^n S_i$ for the first couple of $n$ (2,5,16,65), plug them into OEIS and you will have found the pattern. Of course, this is a poor substitute to actual reasoning but it can be a good first step.2011-01-26

1 Answers 1

4

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).

  • 0
    @Jaska: Quite so. Apolo$g$ies to PEV.2011-01-27