# Multiplication in Permutation

I have a very very stupid question... But i can't get the reason.

Why do we use multiplication in permutations? For example,

Lets say we have 5 friends, A,B,C,D,E. How many ways can we pick a Gold, Silver, and Bronze medal for “Best friend in the world”?

The answer to the above problem is obviously, 5*4*3=60. Now my question is, why can't we use addition in here? like the number of options for gold silver and bronze medal should be 5+4+3=12.. Why we multiply the values?

Edit: I am making my question more clear here...

Is there any other reason for using multiplication like that we have of log .. For eg: log is used when u want to divide the inputs by some factor. We have Log4 (base 2)=2, why? because log means that we are dividing 4 by 2, two times until we get 1, which is, 4/2=2, 2/2=1 (which is two times) .. thats why we use log, to reach a point where we can't divide the input further .. now my question in here asks why we use multiplication? obviously not just because its giving us the right answer!! I hope i have made myself clear enough!!!

-

Look at gold first. Only one gets the gold, so there are 5 posibilites, $\{A,B,C,D,E\}$.

Look at silver next. One already has the gold, so for each possible choice of gold, you have four possibilities, $\{B,C,D,E\}$ for $A$, $\{A,C,D,E\}$ for $B$, $\{A,B,D,E\}$ for $C$, $\{A,B,C,E\}$ for $D$, and $\{A,B,C,D\}$ for $E$. So far we have $4+4+4+4+4=5*4=20$ possible outcomes. See the pattern emerging?

Finally look at bronze. If $A$ get gold, $B$ gets silver, bronze goes to one of $\{C,D,E\}$. If $A$ gets gold, $C$ gets silver, bronze goes to one of $\{B,D,E\}$. Keep going through all the possibilites, and you will have 20 situations, each with 3 possibilites for bronze.

So $20*3=5*4*3=60$, and you have the result.

-
yours is also just another way to see the problem. Mine solution 5*4*3 (that's a general solution in most cases) is another way. How do i get to know if to use * or + ? The problem is I can't related to your solution and how to use your solution to get to my solution :P I still have accepted ur answeR! :P – Chandeep Oct 4 '12 at 17:45
Multiplication is addition written efficiently, so you can use either, but it depends on what you're multiplying / adding. In my answer, in $4+4+4+4+4=20$, 4 is the length of each set. In $5*4=20$, 5 is an index that indicates how many sets I have, and 4 is again the length of each set. In $20*3=60$, 3 is the length of each set, and 20 is the index denoting how many sets of length 3 I have. Instead of 20 sets of 3, we can divide this up: $60=4*3+4*3+4*3+4*3+4*3$, where the 4 is an index denoting how many sets of length 3 I have for the choice of gold and silver, giving 5 terms, so $60=5*4*3$. – jlv Oct 4 '12 at 18:46
Is there any other reason for using multiplication like that we have of log .. For eg: log is used when u want to divide the inputs by some factor. We have Log4 (base 2)=2, why? because log means that we are dividing 4 by 2, two times until we get 1, which is, 4/2=2, 2/2=1 (which is two times) .. thats why we use log, to reach a point where we can't divide the input further .. now my question in here asks why we use multiplication? obviously not just because its giving us the right answer!! I hope i have made myself clear enough!!! – Chandeep Oct 7 '12 at 4:38

Just by looking at the answers and comments you have made I can see that your frustration with multiplication is a deep one. Most of the answers revolve precisely around the fact that it just works! But that's not enough.

Your question reminds me a lot of a similar question. Suppose we have a rectangle with sides $a$ and $b$. Then its area is given by $a\cdot b$ and not by $a+b$. The question might very well be, why do we use multiplication and not addition.

Here is my slightly different take on this question.

A good question might be what is multiplication really? The obvious answer is, it is derived from repeated addition. It's much neater to write $5\cdot 7$ instead of $5+5+5+5+5+5+5$. In the exact same way it's much neater to write $3^5$ to mean $3\cdot3\cdot3\cdot3\cdot3$. You get a whole sequence of mathematical operations starting from addition. Then you have multiplication which is repeated addition. Then you have exponentiation which is repeated multiplication. Next you have tetration. These are shorthands for making things easier to write out.

This still does not answer the question "why multiplication". I can answer why it's not addition. It's because addition is used in a different situation.

Suppose you have a set of 20 kids - a set $\{b_1,\dots,b_7\}$ of 7 boys, and a set $\{g_1,\dots,g_{13}\}$ of 13 girls. You can ask different questions about these sets. For example - "How many kids are there in the class?". You can answer this in the simple way 7+13 = 20. Can we do something with the sets themselves to get the same answer? We'll have to combine them with a "set operation". It's called "disjoint union". This is just putting the two sets next to each other and making a new set: $\{g_1,\dots,g_{13},b_1,\dots,b_7\}$. Taking the size of this set gives us 20.

Now suppose that they are all taking a dance class together. A question we can ask is this "How many different couples can we make out of the two sets of kids?". The answer is $7\cdot 13 = 91$ different couples. This corresponds to a different set operation. You are taking the two sets and combining them in a different way - a set "product". Each girl can dance with each boy, so to each girl corresponds a whole set of boys. Putting the sets together gives us something like $\{(g_1,b_1),\dots,(g_1,b_7),\dots,(g_{13},b_7)\}$. A good way to think about this is putting the sets perpendicular to each other and making a table, where each entry is the given pair.

$\begin{bmatrix}(g_1,b_1)& (g_1,b_2)& \cdots & (g_1,b_7)\\ (g_2,b_1)& (g_2,b_2)& \cdots & (g_2,b_7) \\ \vdots& \vdots& \ddots & \vdots\\ (g_{13},b_1)& (g_{13},b_2)& \cdots & (g_{13},b_7)\end{bmatrix}$

You may complain that my reasoning is circular and it is. It's just a different angle on the same problem.

-
Thank you very much for trying to explain to a dumb A** like me :P .. you know what, multiplication is repetitive addition and i completely agree with that fact .. Still i am not able to convince my self .. I guess one of the other point i am trying to keep is, why people directly multiply in permutations, like that of in my example.. whenever v see a question on permutation most of us(Atleast me) just straight away multiply without even thinking y! So i just simply wanted to know where do we get the * from! that's it.. still.. i haven't made myself a lot clear but this helped! Thanks – Chandeep Oct 7 '12 at 10:15

Think of it as a tree. The first choice, you have 5 branches. Each one of those branches has 4 branches coming off of it, assuming you can't give two prizes to the same person. Each one of those branches has 3 branches, again, only one prize per person. So level one has 5 branches, and each of those branches has 4 branches, giving 20 total branches at level two. The third level, every one of those 20 branches splits into three, give 60 branches total.

EDIT: I'm not quite sure if I understand where you're getting 18 from. I would have thought you would try 5+4+3. Could you explain where the 6 and 7 come from? That may help clear up some confusion.

-
my bad.. it should 5+4+3 .. i was too much into multiplication and addition and lost track of numbers! :P .. I am still trying to understand ur solution ;) – Chandeep Oct 4 '12 at 17:09
thats a good explanation .. but still my question remains.. why we use multiplication not addition ? – Chandeep Oct 4 '12 at 17:30
We need to multiply because we aren't just adding 4 branches at the second level, we're adding 4 branches to each of the original 5 branches. That gives us 4*5=20 branches at the second level, not just 9. – Michael Dyrud Oct 4 '12 at 21:30

Another approach:

Ultimately the reason why we can't use addition is that it doesn't work. In your example $5+4+3=12$ is the wrong answer -- not because it's been computed in a different way than the teacher says we must, but because there are actually more than 12 different ways to do the assignment. We can write them down explicitly:

ABC  ABD  ABE  ACB  ACD  ACE  ADB  ADC  ADE  AEB  AEC  AED
BAC  BAD  BAE  BCA  BCD  BCE  BDA ...


Here are already 19 different arrangements (you can easily check that they are all different), and since 19 is more than 12, it is not true that the number of possible choices is 12. So 12 is a wrong answer -- adding does not work in this case.

On the other hand, multiplying does work.

-

We will make a three-letter "word" using three distinct letters chosen from A, B, C, D, E. For example, the word BEA means B gets the gold, E the silver, A the bronze. There are just as many ways to decide how to hand out the medals as there are ways to make the $3$-letter words.

Let's count the words, maybe by listing. First count the words that begin with the letter A. Imagine listing them all, alphabetically. First would come ABC, then ABD, then ABE, $3$ words. Then we would count the ones that start with AC, $3$ more. Then the ones that start with AD, $3$ again, and finally the ones that start with AE, $3$ again. So there are $(4)(3)$ words that start with A.

But exactly the same number of words start with B, with C, with D, with E. So our dictionary listing will have $(5)(4)(3)$ items.

-

Consider there were only two friends $A,B$. Then obviously there is no way to pick Gold, Silver, and Bronze at all. That is what multiplication gives: $2$ choices for Gold, $1$ choice for Silver, $0$ choices for Bronze, for a tota; of $2\times1\times0=0$ possibilities. But addition would give you $2+1+0=3$ possibilities, which is clearly wrong.

If you propose a formula (addition in your case), you should try to at least formulate a reason (maybe not quite a proof) why that formula describes the answer, and you didn't even do that.

I'll add an argument why this situation calls for multiplication, although other answers already do that quite well and seem to have failed to convince OP. We are in the situation of wanting to count configurations that involve separately fixing several attributes (concretely attributions of medals). A simple example of such a situation is choosing a square on a chessboard: that involves choosing a row and a column (the rank and file of chess), and these two independent choices fix the choice of a square uniquely. I think you must be able to see why in this case the number of squares is obtained by multiplying the numbers or rows and of columns, and not by adding them. And then if you have $20$ chessboards in a tournament (adding one more attribute, the choice of a board, to the problem), that multiplies the total number of squares by $20$, it does not just add $20$ squares...

-
so u are proving that multiplication gives u the right answer and that is the only reason we use multiplication instead of any other operation ? Ain't there any other reason like that we have of log .. For eg: log is used when u want to divide the inputs by some facotr. We have Log4 (base 2)=2, why? because log means that we are dividing 4 by 2, two times until we get 1, which is, 4/2=2, 2/2=1 .. thats why we use log .. now my question in here asks why we use multiplication? obviously not just because its giving us the right answer!! I hope i have made myself clear enough!!! – Chandeep Oct 7 '12 at 4:33
I was answering to "Now my question is, why can't we use addition in here?". And yes I'm sorry for you, but the first and foremost reason for choosing a formula to use is that it gives the right answer. A formula that gives a very wrong answer is useless for your problem, no matter how much you like it, or how much reasons you can find that it should be the formula to use. Your argument about log is confused but in the end, one uses log because it "does" what is required. And for counting possibilities with indepenent choices (say a pizza from 3 sizes and 7 kinds) multiplication does that. – Marc van Leeuwen Oct 7 '12 at 5:54
yeah, might be i am confused right now .. anyways thanks for helping! :) – Chandeep Oct 7 '12 at 6:52