Embedded Files
Figure 1. Consider the combinations of four stairs that we can make. We can choose to step on stair 1 or to step over it - same for stairs 2 and 3. The combinations of stairs that we can choose to step on, then, are{4}{1,4}{2,4}{3,4}{1,2,4}{1,3,4}{2,3,4}{1,2,3,4}which are eight in total. Using the combination formula with n = 4 and k = 1, 2, 3, and 4, we get the wrong counts: 1, 6, 6, 1. Clearly we don't have 14 combinations total as listed above. Instead, we should use n = 3 because stair 4 is always included. This gives us the correct counts with n = 3 and k = 0, 1, 2, and 3: 1, 3, 3, 1.
Page updated
Report abuse