# Factorial – Intro to Computer Science

For the next quiz, you are going to define a procedure that can help solve the problem of figuring out how many different ways there are to order objects. Here is the problem we want to solve. Suppose we have four blocks. We have a red block. We have a blue block. We have a purple block and we have a green block. We have a baby who wants to play with the blocks, and we want to know how long can the baby play with the blocks without getting bored. What the baby wants to do is try all the different ways of arranging the blocks. The baby will stack the blocks in a tower. The baby might pick the red block firstÃ¢Â€Â”put that on the ground. Then put the blue block on top. Then put the the purple block on top of that, and then put the green block on top. When she’s made one tower, she is going to knock it down and make another one. She’s going to keep doing this as long as she can make different color combinations. If she has to make the same tower twiceÃ¢Â€Â”well, that’s pretty boring. Maybe the next one she’ll pick the purple block first, then she’ll pick the red block, then she’ll pick the blue block, and then she’ll pick the green block. These two are different. The question we want to answer is, how many different towers can she build? Given that she has four blocks, we want to know how many different towers could you build with four blocks, but maybe she gets some more blocks. What we really want to know isÃ¢Â€Â”given that she has “n” blocksÃ¢Â€Â”whatever number “n” isÃ¢Â€Â”how many different towers could you build where the color combinations are all different? The way to solve that is to think about combinatorics. The way to pick the first blockÃ¢Â€Â”well, it could be any one of these four. We have four choices. Let’s sayÃ¢Â€Â”for our exampleÃ¢Â€Â”she chooses the red block first. Now it’s time to choose the second block. Well, she can’t use the red block again. She has already used it, so she can either use the purple, the blue, or the green block. She has three choices now. She can use the purple block, the blue block, or the green block. Let’s say she chooses the green block, so she is going to have the red block and then the green block. She had three choices. She could have chosen any of the other two, but now that she has chosen the red and the green, she only has two choices left for the third block. She can either use the purple one or she could use the blue oneÃ¢Â€Â”those are the only two that are left. Let’s say she uses the purple one. Now for the final blockÃ¢Â€Â”well, she’s used the red one, she’s used the green one, and she’s used the purple one. The only one that’s left is the blue one, so she has no choice but to use the blue block. That means for the fourth block, there was only one choice. So, for each of these choices, she could choose any of the four for the first one, any of the three remaining ones for the second oneÃ¢Â€Â”regardless of what she picked for the first one. If she picked red, she could pick either purple, blue, or green, but if she’d pickedÃ¢Â€Â”sayÃ¢Â€Â”blue for the first one, then what she’d have left is purple, red, and green. She always has three choices for the second one. After that, there’s only two choices leftÃ¢Â€Â”there’s only two blocks left and she can choose either one. The pattern here is every time she chooses a block there’s one less because she’s used the block in the previous choice. For the total number of choices, what we want to do is multiply all these numbers. To figure out the total number of choices, what we need to do is multiply the number of choices for the first block, and then we multiply that by the number of choices for the second and we keep going for however many choices there areÃ¢Â€Â”in this case there are only fourÃ¢Â€Â”until we get down to one. Each time we make a choice, we have one fewer items left to use for the next choice. So the function that we are computing here is mathematically called factorial, and it’s sometimes written with an exclamation point. A way to define factorial isÃ¢Â€Â”for any value n, we can compute the factorial, which is the number of ways of arranging “n” items. We can compute that by multiplying “n”Ã¢Â€Â”which is the number of choices for the first itemÃ¢Â€Â”times “n” minus oneÃ¢Â€Â”that’s the number of choices we have left for the second itemÃ¢Â€Â”times “n” minus twoÃ¢Â€Â”that’s the number of choices for the third item and so fourth, all the way until we get down to one. So, your goal for this quiz is to define a procedure named “factorial” that takes one number as its inputÃ¢Â€Â”that’s the number “n” hereÃ¢Â€Â”and outputs the factorial of that number, which we can compute by multiplying “n” times “n” minus one all the way down to one.