Results 1 to 10 of 10

Thread: Product principle & the permutation formula (intuition)!

  1. #1
    Newbie
    Joined
    Feb 2018
    From
    Location
    Posts
    11

    Question Product principle & the permutation formula (intuition)!

    I'm new to permutations & counting principles.

    I've been told n! is the number of permutations of n different objects.

    I was also taught the product principle for events that are INDEPENDENT (one event doesn't affect the occurrence of the other event).

    I understand n different objects have n choices for the first place... down to one choice for the last spot.

    What I don't understand is the intuition for applying the product principle to get the number of permutations as follows...

    (n)(n - 1)(n - 2) ... (1).

    Isn't the first event for placing the first object (n choices) & the second event for placing the second object (n - 1 choices) & so on?

    If so; why can the product principle be applied to this? Why are these events independent if the previous event affects the number of choices for the following event?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,155
    Thanks
    3047
    Awards
    1

    Re: Product principle & the permutation formula (intuition)!

    Quote Originally Posted by Karnt View Post
    I was also taught the product principle for events that are INDEPENDENT (one event doesn't affect the occurrence of the other event).
    I understand n different objects have n choices for the first place... down to one choice for the last spot.
    (n)(n - 1)(n - 2) ... (1).
    You have completely confused me. You stated the exact same process twice?
    If there are six people to line up, we have six ways to choose the first, five ways to choose the second, etc.
    $6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$. We symbolize that product as $6!$. That is the product principle.

    Now please try to explain what is confusing you.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2018
    From
    Location
    Posts
    11

    Re: Product principle & the permutation formula (intuition)!

    Using that example of lining six people up...

    I see six separate events (putting someone in the first spot, then putting someone in the second spot & so on).

    Why are these events considered independent (one event doesn't affect the occurrence of another event)? I see the second event (placing someone in the second spot) as limited / affected by the first event (placing someone in the first spot) as one person isn't an option for that second event.

    A clarification on independent events could help?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,155
    Thanks
    3047
    Awards
    1

    Re: Product principle & the permutation formula (intuition)!

    Quote Originally Posted by Karnt View Post
    Using that example of lining six people up...
    I see six separate events (putting someone in the first spot, then putting someone in the second spot & so on).
    Why are these events considered independent (one event doesn't affect the occurrence of another event)? I see the second event (placing someone in the second spot) as limited / affected by the first event (placing someone in the first spot) as one person isn't an option for that second event.
    A clarification on independent events could help?
    Forget the words independent events they have absolutely nothing to do with the basic product principle.
    Look at this discussion. Do you see the word Independence in that discussion? Independent events are extremely important in probability but not basic counting.

    Here is another example. You are at school. From school there are five ways to drive to the town library. From the library there are three ways to drive to you club meeting. Then there are five ways to drive to the drugstore. From that drugstore there are four ways to drive home. To make those stops, there (5)(3)(5)(4)=300 ways to drive home making all the stops between.
    That is a simple simple application of the basic product principle. Independence has no role to play.
    You are to visit those places in a fixed order but you are free to choose the paths, of which there are three hundred.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2018
    From
    Location
    Posts
    11

    Re: Product principle & the permutation formula (intuition)!

    This is the definition of the product principle I was given...

    "If an event can occur in r number of ways and another independent event can occur in s number of ways, then there are r * s ways of first and second event occurring.".

    Independence was part of the definition and was further stressed after that definition.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    20,049
    Thanks
    3176

    Re: Product principle & the permutation formula (intuition)!

    First, yes, you are correct that choosing an object first and choosing an object second are not independent. That is why we cannot argue that "if we have n objects any one of them could be chosen first and any one of them could be chosen second so the there are n*n ways to choose the first two items".

    But we can say that there are n ways to choose the first one and then there are n-1 left so there are n-1 ways to choose the second. The acts of "choosing the first one" and, assuming that has already been done, "choosing the second from the remaining n-1" are independent.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,155
    Thanks
    3047
    Awards
    1

    Re: Product principle & the permutation formula (intuition)!

    Quote Originally Posted by Karnt View Post
    This is the definition of the product principle I was given...
    "If an event can occur in r number of ways and another independent event can occur in s number of ways, then there are r * s ways of first and second event occurring.".
    Independence was part of the definition and was further stressed after that definition.
    That is not correct. It is simply incorrect. Show the webpage to whomever.
    Here is another reference. Can you find the word independence on that website?
    Look here
    Look Here
    Look HERE also.
    You cannot find the word independence anywhere there. Can you?
    Who ever gave you that definition does not understand the basic principles of counting.
    If I were you, I would complain to the head of your program. Although I am now retired. I was a head of a mathematical sciences division in a university. As such, I saw so many people who came to us thinking that had a sound preparation (A.P. courses can be the worst) but actually had been given a mistaken start. Do not let that happen to yourself.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Feb 2018
    From
    Location
    Posts
    11

    Re: Product principle & the permutation formula (intuition)!

    Quote Originally Posted by HallsofIvy View Post
    First, yes, you are correct that choosing an object first and choosing an object second are not independent. That is why we cannot argue that "if we have n objects any one of them could be chosen first and any one of them could be chosen second so the there are n*n ways to choose the first two items".

    But we can say that there are n ways to choose the first one and then there are n-1 left so there are n-1 ways to choose the second. The acts of "choosing the first one" and, assuming that has already been done, "choosing the second from the remaining n-1" are independent.
    I was thinking of something like that from your second paragraph; but, I didn't like it because it seemed pedantic to define events (in that way) for something that is meant to be so easy. It's like putting assumptions into the definitions of the subsequent events (choosing the second item as the second event and choosing the third item as the third event and so on... ) based off the previous events and I didn't like that.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Feb 2018
    From
    Location
    Posts
    11

    Re: Product principle & the permutation formula (intuition)!

    Quote Originally Posted by Plato View Post
    Do not let that happen to yourself.
    Am trying to avoid problems before starting. I'll be asking some more questions on here.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Product principle & the permutation formula (intuition)!

    Quote Originally Posted by Plato View Post
    That is not correct. It is simply incorrect. Show the webpage to whomever.
    Here is another reference. Can you find the word independence on that website?
    Look here
    Look Here
    Look HERE also.
    You cannot find the word independence anywhere there. Can you?
    Who ever gave you that definition does not understand the basic principles of counting.
    If I were you, I would complain to the head of your program. Although I am now retired. I was a head of a mathematical sciences division in a university. As such, I saw so many people who came to us thinking that had a sound preparation (A.P. courses can be the worst) but actually had been given a mistaken start. Do not let that happen to yourself.
    I am at work, so I do not have time to find references. But, I believe independence has been defined differently in this context (many newer combinatorics books have taken to using the term independent events when defining the product principle). I remember the examples from my text better than the definitions themselves. Perhaps that will highlight what some texts now mean when they discuss independence.

    Example of independent events: You have the numbers 1 through n. You want to know the number of permutations of those n numbers. When choosing the first number, you have n choices obviously. Independent of the choice of the first number, you will always have n-1 numbers left to choose for the second choice.

    Example of dependent events: You have the numbers 1 through n. You want to know the number of permutations of those n numbers such that 2 does not follow 1. We naively attempt to use the same method for counting as above. For our first number, we still have n choices. For the second number, if our first choice was a 1, we have n-2 choices. If the first choice was not a 1, we have n-1 choices for the second number. Thus, the number of choices available to us is dependent upon our previous choice. With this counting scheme, we cannot apply the product principle. We would need to choose a different counting scheme to count this.

    Note: a simple counting scheme is to count the total number of permutations without restriction, then count the number of permutations that violate this restriction, and take the difference. But, that involves more than just the product principle.

    Again, I do not recall the specifics of how the definition for this type of independence is worded, but I do recall that it was mathematically sound when I took my first combinatorics course at university. The idea of this type of independence is that the specific objects available to choose at each step does not need to be independent. All that needs to be independent is the number of objects available to choose.
    Last edited by SlipEternal; Feb 21st 2018 at 06:26 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Jan 5th 2014, 05:06 AM
  2. Pigeon hole principle for odd or even product
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jun 25th 2010, 06:37 AM
  3. k constant in first principle formula
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Apr 24th 2010, 04:15 AM
  4. Replies: 1
    Last Post: Jan 24th 2010, 12:24 PM
  5. permutation and semidirect product
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 7th 2009, 11:09 AM

/mathhelpforum @mathhelpforum