How are partial permutations counted when only some items are selected?

"Sometimes we want to count the permutations of a set, but only want to choose some of the items each time, not all of them. For example, consider a golf tournament in which the top ten finishers (out of 45) all receive prize money, with the first place winner receiving the most, the second place finisher a lesser amount, and so on down to tenth place, who receives a nominal prize. How many different finishes are possible to the tournament? In this case, we want to know how many different orderings of golfers there are, but it turns out that past tenth place, we don’t care what order they finished in. All that matters is the first ten places. If the top ten are 1. Tiger, 2. Phil, 3. Lee, 4. Rory, . . . , and 10. Bubba, then it doesn’t matter whether Jason finished 11th or 45th. It’s easy to see that there are 45 possible winners, then for each winner there are 44 possible second-placers, etc., so that this total turns out to be: 45 × 44 × 43 × 42 × 41 × 40 × 39 × 38 × 37 × 36 = 11,576,551,623,436,800 finishes.\n\nEach of the finishes is called a partial permutation. It’s a permutation of k items chosen from n total, and is denoted pₙ,ₖ. The number of such permutations works out to n × (n − 1) × (n − 2) × · · · × (n − k + 1). The “n − k + 1” bit can be confusing, so take your time and think it through. For the golf tournament case, our highest term was 45 and our lowest term was 36. This is because n was 45 and k was 10, and so we only wanted to carry out the multiplication to 36 (not 35), and 36 is 45 − 10 + 1. This can be expressed more compactly in a few different ways: n × (n − 1) × (n − 2) × · · · × (n − k + 1) = n!/(n − k)! = ∏ᵢ₌₀ᵏ⁻¹(n − i). Finally, as with (non-partial) permutations, this comes up so much that the professionals have invented a special notation for it. It looks like a power, but has an underline under the exponent: n × (n − 1) × (n − 2) × · · · × (n − k + 1) = nᵏ. This is pronounced “n-to-the-k-falling,” and was invented by one of the most brilliant computer scientists in history, Donald Knuth. To keep straight what nᵏ means, think of it as the same as plain exponentiation, except that the product diminishes instead of staying the same. For example, “17-to-the-6th” is 17⁶ = 17 · 17 · 17 · 17 · 17 · 17, but “17-to-the-6th-falling” is 17⁶ = 17 · 16 · 15 · 14 · 13 · 12.\n\nPartial permutations abound in practice. A late night movie channel might show four classic films back to back every evening. If there are 500 films in the studio’s library, how many nightly TV schedules are possible? Answer: 500⁴, since there are 500 choices of what to show at 7pm, then 499 choices for 9pm, 498 for 11pm, and 497 for the 1am late show. The fastest 41 auto racers will qualify for Sunday’s race, and will be placed from Pole Position on down depending on their qualifying time. If 60 cars participate in the qualifying heat, then there are 60⁴¹ different possible starting configurations for Sunday. Middle schoolers entering sixth grade will be assigned a semester schedule that consists of five “blocks” (periods), each of which will have one of thirteen classes (science, math, orchestra, study hall, etc.). How many schedules are possible? You guessed it, 13⁵. Notice that this is the correct answer only because no repeats are allowed: we don’t want to schedule any student for American History more than once. If a student could take the same class more than once in a day, then there would be 13⁵ (not “falling”) different possible schedules."