The factorial function

For our first example of recursion, let's look at how to compute the factorial function. We indicate the factorial of nn by n!n!. It's just the product of the integers 11 through nn. For example, 5!5! equals 123451⋅2⋅3⋅4⋅5, or 120120. (Note: Wherever we're talking about the factorial function, all exclamation points refer to the factorial function and are not for emphasis.)

You might wonder why we would possibly care about the factorial function. It's very useful for when we're trying to count how many different orders there are for things or how many different ways we can combine things. For example, how many different ways can we arrange nn things? We have nn choices for the first thing. For each of these nn choices, we are left with n1n-1 choices for the second thing, so that we have n(n1)n⋅(n−1) choices for the first two things, in order. Now, for each of these first two choices, we have n2n−2 choices for the third thing, giving us n(n1)(n2)n⋅(n−1)⋅(n−2) choices for the first three things, in order. And so on, until we get down to just two things remaining, and then just one thing remaining. Altogether, we have n(n1)(n2)21n⋅(n−1)⋅(n−2)⋯2⋅1 ways that we can order nn things. And that product is just n!n! (nn factorial), but with the product written going from nn down to 11 rather than from 11 up to nn.

Another use for the factorial function is to count how many ways you can choose things from a collection of things. For example, suppose you are going on a trip and you want to choose which T-shirts to take. Let's say that you own nn T-shirts but you have room to pack only kk of them. How many different ways can you choose kk T-shirts from a collection of nn T-shirts? The answer (which we won't try to justify here) turns out to be

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy