[Math] Difference between the principle of addition, the principle of multiplication, permutations and combinations

combinationspermutations

According to my book:

1.The fundamental principle of counting is used to count the number of possible ways in which a task can be done without actually counting manually.

2.Under the fundamental principle of counting comes the principle of addition and the principle of multiplication.

3.The principle of addition states if a one task can be one done in $m$ ways and another task which is MUTUALLY EXCLUSIVE of the first task can be done in $n$ ways, then the number of possible ways in which either can be done is $m+n$.This result can be generalized.

4.The principle of multiplication states that if one task can be done in $m$ ways and another task which is INDEPENDENT of the first task can be done in $n$ ways, after the first task has been performed, then the number of possible ways in which both the tasks can be done is $m \times n$.This result can be generalized.

5.Permutations refer to the possible arrangements of a collection of objects.

6.Combinations refer to the possible selections of a collection of objects.

My problems:

1.I was having a lot of problems understanding the difference between the principle of addition and the principle of multiplication. I thought about it a lot and this is my interpretation:

(a).The addition principle is applied when we want to calculate the number of possible ways to perform a task (perform any one of the subtasks).

The task consists of $k$ subtasks ($n_1, n_2, n_3, …, n_k$), the subtasks can be done in $m_1, m_2, m_3, …, m_k$ ways respectively. Thus the number of possible ways to do the task is $m_1 + m_2 + m_3 +…+ m_k$.

(b).The multiplication principle is applied when we want to calculate the number of possible ways to perform a task(perform all the subtasks).The task consists of $k$ subtasks($n_1, n_2, n_3, …, n_k$), the subtasks can be done in $m_1, m_2, m_3, …, m_k$ ways respectively.Thus the number of possible ways to do the task is $m_1 \times m_2 \times m_3 \times … \times m_k$.

Am I correct?

2.I cannot understand the significance of the word MUTUALLY EXCLUSIVE in point number 3 and the word INDEPENDENT in point number 4. What does it mean when we say that one task is independent of the other and what is its significance here.

3.What is the difference between principle of multiplication and permutation. I guess permutation is a special case of the principle of multiplication.

4.What is the difference between principle of addition and combination.

Best Answer

Yes, you are correct. A more down to earth example, if I have $4$ apples and $3$ oranges in a basket, there are $3+4=7$ ways I can pick one fruit from the basket, and there are $3\cdot 4$ ways I can pick one apple and one orange from the basket.
The independent means that no matter how one task is performed, the number of ways you can perform the second task is the same. For example, the tasks "pick one apple" and "pick one orange" are independent in the previous example, since no matter what apple I pick, I still have the same $3$ oranges to pick from.$$$$ On the other hand, if my first "task" is "pick one fruit" and the second is "pick one orange", then the number of ways I can perform the second task depends on the way I performed my first task. If I picked an apple, I have $3$ ways of performing the second task. If I picked an orange, I have only $2$.
The formula for the number of permutations is obtained by applying the principle of multiplication.
These are two different things, the principle of addition is a general principle, while combinations are specific collections of objects from a set.

Related Solutions

[Math] Permutations and Combinations – How many different ways to do certain things before having to repeat

I agree with you on Event A; I'm not so sure about event C. And I disagree with your Event B.

For Event B: consider the case where Aji eats his sandwich second to last. You claim that there are six ways of doing this; I think there are only 4 ways: the meat must be put into the sandwich either first or second; then you have two choices of what else to do before eating the sandwich; the last thing you do is now forced. Explicitly (with m=putting meat, f=eating fruit, j=drinking juice, and s=eating sandwich) the only four things he can do are mfsj, mjsf, fmsj, and jmsf. I don't see six things.

Where is your counting error? It is true that you have three choices for the first position, but you don't have two choices for the second thing. You only have two choices for the second thing if the first things you did was putting the meat in; if you chose anything else for your first thing to do, then the second thing to do must be putting the meat in the sandwich, so you don't really have 2 choices for the second thing regardless of the third. Instead, you would have to break it up into cases: you have 2 ways of doing it if the meat happens first; and 2 ways if the meat happens second.

Here's a simpler way of doing Event B:

Since Aji must put meat in the sandwich before eating it, we know that, whethever order he does things, "put meat" goes before "eat sandwich". There are things that can happen before he puts meat in the sandwich, things that can happen after he puts meat in the sandwich but before he eats it, and things that can happen after he eats his sandwich.

So, relative to the putting-meat-and-eating-his-sandwich, there are three temporal locations for "eat his fruit" to go into:

  <location 1>  put meat  <location 2>   eat sandwich <location 3>

Once we chronologically locate the fruit relative to the sandwich-eating process, what about the juice? There are now four temporal locations for the juice: any of the two temporal locations not used by the fruit; and the same temporal location as the fruit, but either before the fruit, or after the fruit. For instance, if the fruit was eaten between putting the meat and eating the sandwich, then the juice can be had before putting the meat, or after the meat but before the fruit; or after the fruit but before the sandwich; or after the sandwich.

This gives $3\times 4 = 12$ different ways of doing Event B.

As for Event C: note that the problem states that he picks up the fishing rod and the icebox after tying the vote. That means that the first thing Aji does is tie the boat. Then he can either grab the fishing rod or the icebox (two things). Then he grabs whatever is left, then he heads home. It seems to me that there are only two ways of performing event C, not six.

Added: Event C has recently been edited to give 2 ways, in which case I agree.

Your method for the second part of the question works (it doesn't have to be in Event A or C; it could be something in Event B as well). Or you can add a thing that can either be done or not, e.g., "wear or not wear a cap."

[Math] Understanding fundamental principles of counting

The distinction is not between "independently" and "in succession". The real distinction is whether you are doing both, or you are doing just one.

The number of ways to do one of the jobs is $m+n$ (either do the first job, which can be done in $m$ ways; or do the second job, which can be done in $n$ ways; total number of ways, $m+n$).

The number of ways of doing both is $mn$, because you have $m$ ways of doing the first job, and $n$ ways of doing the second job, and you have to do both.

Say you have $5$ pants and $3$ shirts. If you are giving one piece of clothing away, then you have $5+3$ ways of deciding which piece to give away. But if you are deciding what to wear, you need to pick a pair of pants, and a shirt. That gives you $5\times 3$ possible combinations. You can make the choices simultaneously (they don't have to be "in succession"). The "independence" clause is jut that choice of shirt/pants should not restrict your choice of pants/shirt (so you don't have a plaid shirt and a pair of striped pants that cannot be worn together...). What you choose for job one does not affect what you can choose for job two.

So you have to think about what you are doing. I'm not sure if there are "keywords" that you should be looking at.

Best Answer

Related Solutions

[Math] Permutations and Combinations – How many different ways to do certain things before having to repeat

[Math] Understanding fundamental principles of counting

Related Question