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.