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

1. ## 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?

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

Originally Posted by Karnt
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.

3. ## 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?

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

Originally Posted by Karnt
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.

5. ## 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.

6. ## 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.

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

Originally Posted by Karnt
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.

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

Originally Posted by HallsofIvy
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.

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

Originally Posted by Plato
Do not let that happen to yourself.
Am trying to avoid problems before starting. I'll be asking some more questions on here.

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

Originally Posted by Plato
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.