Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<a_2<\ldots <a_i$.

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

share|improve this question
    
Did you mean $a_i = i$? –  PEV Jan 26 '11 at 22:10
    
No. I really mean that $a_i=n$ is the maximal integer, before that we have an increasing sequence, and the rest can be arbitrary elements. –  Jaakko Seppälä Jan 26 '11 at 22:14
    
@PEV , no I think he mean what he wrote, the last number in the permutation is the largest number of the set. every other element of the permutation are in decreasing order e.g. for {1,2,3} we get 3,23,13,123 but not 213 –  Arjang Jan 26 '11 at 22:15
    
@Arjang: Not quite. We might have for example $(1,3,6,7,5,4,2)$. Now the largest number is in the middle, before it we have $1<3<6<7$ and three last digits can be in arbitrary order. I wrote it a bit clearly. –  Jaakko Seppälä Jan 26 '11 at 22:22
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. –  Dinesh Jan 26 '11 at 22:33

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
    
@Jaska: There is probably a closed-form for the sum in the end, but I'm on my way out of the office. I'll check later. –  Arturo Magidin Jan 26 '11 at 22:34
    
@Arturo: The closed form is $e \Gamma(n+1, 1)- \Gamma(n+1)$. –  PEV Jan 26 '11 at 22:39
    
@Arturo: Shouldn't it be $\binom{n-1}{i-1}$? You can't choose $n$, so you're selecting $i-1$ elements from $n-1$. –  Mike Spivey Jan 26 '11 at 22:41
    
@Mike: Yes indeed; screwed that up in a rather silly way. –  Arturo Magidin Jan 26 '11 at 22:42
    
@PEV: So with the correct computation, will that be $e\Gamma(n,1)-\Gamma(n)$? –  Arturo Magidin Jan 26 '11 at 22:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.