A lock has n buttons labeled 1, 2, . . . , n. To open this lock we press each of the n buttons exactly once. If no two or more buttons may be pressed simultaneously, then there are n\ ways to do this. However, if one may press two or more buttons simultaneously, then there are more than n! ways to press all of the buttons. For instance, if n = 3 there are six ways to press the buttons one at a time. But if one may also press two or more buttons simultaneously, then we find 13 cases - namely,
(1) 1,2,3
(2) 1,3,2
(3) 2, 1, 3
(4) 2, 3, 1
(5) 3, 1, 2
(6) 3, 2, 1
(7) {1,2}, 3
(8) 3, {1,2}
(9) {1,3}, 2
(10) 2, {1,3}
(11) {2, 3}, 1
(12) 1, {2, 3}
(13) {1,2, 3}.
[Here, for example, case (12) indicates that one presses button 1 first and then buttons 2, 3 (together) second.] (a) How many ways are there to press the buttons when n = 4? n = 5? How many for n in general? (b) Suppose a lock has 15 buttons. To open this lock one must press 12 different buttons (one at a time, or simultaneously in sets of two or more). In how many ways can this be done?