Re: Permutations, confusion about notation

In article <1138049466.787378.225310@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
robison <robison.jack@xxxxxxxxx> wrote:
>Hello,
>
>I am a little confused by the notation used in permutations. For
>example, when I look at the wikipedia entry for permutations it states
>(like most places do) that the last entry (n - r + 1); however, I am
>really confused as to why they all sudden slap the - r and + 1 in
>instead of just contiune with the pattern of n(n - 1)(n - 2)(n -
>3)...
>
>Why do they put in the - r and the + 1?
>
>Thank you for your help

Suppose you have 10 things to choose from, all distinct. You want to
pick 5 of them, in order (order matters, so we are dealing with
permutations). You have

10 ways of choosing the first thing; after choosing that there are
9 = (10-1) remaining ways of choosing the second thing; then
8 = (10-2) remaining ways of choosing the third; then
7 = (10-3) remaining ways of choosing the fourth; and
6 = (10-4) remaining ways of choosing the fifth.

The total number of ways will be the product of these, since you need
to pick a first, a second, a third, a fourth, AND a fifth thing.

More generally, if you have n things to choose from, and you want to
pick r of them, without repetition, and where order matters, the first
thing can be picked in any of n different ways. If you have already
picked k objects, then you have n-k ways of picking the (k+1)-st
object.

So, since you want to go all the way to k+1 = r, that means that when
you pick the ->last<- object you want to pick, you will have n-k ways
of doing so; but since you are picking the r-th object, and k=r-1,
that means that you have n-(r-1) ways of doing so.

So: n ways for the first, (n-1) for the second, ..., up to (n-(r-1))
for the r-th.

You get n*(n-1)*(n-2)*...*(n-(r-1)) = (n-0)*(n-1)*...*(n-(r-1)).

You'll note that there are r factors, one each for the integers from 0
to r-1.

And then, instead of writing with n-(r-1) with a double subtraction,
just write it as n-r+1 by distributing the leftmost subtraction.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes")
======================================================================

Arturo Magidin
magidin@xxxxxxxxxxxxxxxxx

.

Relevant Pages

  • Re: some questions about permutation
    ... Two independently chosen RSA trapdoor permutations won't commute. ... I have said in former statement that two permutations have the same ... will use for choosing N and for choosing m, a, and b before we can give ...
    (sci.crypt)
  • Re: permutation question
    ... "the average is simply the sum of the times over all ... choosing a random ... over all permutations of the input divided by n ... the average of all possibilities of a single throw = the average of a single random throw. ...
    (sci.math)
  • Re: permutation question
    ... the input divided by n factorial, it's equivalent to choosing a random ... random permutation of the input be equivalent to the sum of the times ... over all permutations of the input divided by n factorial? ... Ken Pledger. ...
    (sci.math)
  • Re: permutation question
    ... "the average is simply the sum of the times over all ... choosing a random ... over all permutations of the input divided by n ...
    (sci.math)
  • Re: Permutations, confusion about notation
    ... robison wrote: ... > I am a little confused by the notation used in permutations. ... when I look at the wikipedia entry for permutations it states ...
    (sci.math)