Let S i be the number of permutations { a 1 , … , a n } = { 1 , . . . , n }, satisfying the following conditions:1. a i = n for some i ∈ { 1 , … , n }2. a 1 &lt; a 2 &lt; … &lt; a i .Compute ∑ i = 1 n S i .

Question

Let       S    i   be the number of permutations   {      a    1    ,  …  ,      a    n    }  =  {  1  ,  .  .  .  ,  n  }, satisfying the following conditions:1.       a    i    =  n for some   i  ∈  {  1  ,  …  ,  n  }2.       a    1    &amp;lt;      a    2    &amp;lt;  …  &amp;lt;      a    i  .Compute       ∑          i      =      1        n        S    i  .

reinmelk3iu · Accepted Answer

First, let&#039;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        ,  …  ,      a    n   arbitrarily. This gives                     (                            n        −        1                    i        −        1                            )              (  n  −  i  )  !  =            (      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    ,  …  ,      a    n    )  →  (      a    2    ,  …  ,      a    n    ,      a    1    )  → etc. Since both have 𝑛 in the same position in the cycle, the two 𝑛-tuples represent distinct permutations. So       S    i    =            (      n      −      1      )      !              (      i      −      1      )      !      .So the number you want is      ∑          i      =      1              n            S    i    =      ∑          i      =      1        n              (      n      −      1      )      !              (      i      −      1      )      !        =  e  Γ  (  n  ,  1  )  −  Γ  (  n  )

Let Si be the number of permutations {a1,…,an}={1,...,n}, satisfying the following conditions: 1. ai=n for some i∈{1,…,n} 2. a1<a2<…<ai. Compute ∑ni=1Si.

Answered question

Answer & Explanation

New Questions in Precalculus