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

  • 0
    Did you mean $a_i = i$?2011-01-26
  • 0
    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.2011-01-26
  • 0
    @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 2132011-01-26
  • 0
    @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.2011-01-26
  • 0
    @Jaska: if the tuple represents a cycle, then some permutations may occur in more than $S_i$. for example, with $n=2$, the permtuation $(2,3,1)$ appears in $S_2$, but it also appears in $S_3$, written as $(1,2,3)$. Do you want to count it twice when you add up the $S_i$?2011-01-26
  • 0
    @Arturo Magidin: I want to count it twice. I was thinking () denotes the ordered tuple.2011-01-26
  • 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: 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.2011-01-26
  • 0
    @Arturo: The closed form is $e \Gamma(n+1, 1)- \Gamma(n+1)$.2011-01-26
  • 0
    @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$.2011-01-26
  • 0
    @Mike: Yes indeed; screwed that up in a rather silly way.2011-01-26
  • 0
    @PEV: So with the correct computation, will that be $e\Gamma(n,1)-\Gamma(n)$?2011-01-26
  • 0
    @Arturo: yes it would.2011-01-26
  • 0
    @PEV: Thanks. I'll add that.2011-01-27
  • 0
    I think the last line should be "thanks to PEV", not Jaska.2011-01-27
  • 0
    @Jaska: Quite so. Apologies to PEV.2011-01-27