One day I received electronic mail from our director of campus security [Gilbraith 1993]:
"I have a puzzle for you that has practical applications for me. I need to know how many different combinations there are for our combination locks. A lock has 5 buttons. In setting the combination you can use only 1button or as many as 5. Buttons may be pressed simultaneously and / or successively, but the same button cannot be used more than once in the same combination.
I had a student (obviously not a math major) email me that there are only 120 possibilities, but even I know this is only if you press all five buttons one at a time. It doesn't take into account 1-23-4-5, for instance. My question to you is how many combinations exist, and is it enough to keep our buildings adequately protected?"
To clarify, combinations like 1-25-4 (which is the same as 1-52-4 but different from 4-25-1) and 1-2-5-43 are legal, whereas 13-35 is illegal because the number 3 is used twice.
I gave this problem to the students in my discrete mathematics class as a bonus exercise. Most arrived at the (correct) answer of 1081 or 1082 by breaking the problem into oodles of cases, but this would not have been a convenient method if the locks contained 10 buttons instead of 5. I use this problem as an excuse to demonstrate the power of generating functions by solving the n-button problem. Most students are amazed that the problem is essentially solved by the function ex /(2 - ex), which leads to a surprisingly accurate approximation of n!/(ln 2)n+1.
© 1996 Consortium for Mathematics and Its Applications (COMAP, Inc.)
Benjamin, A.T. (1996). Combinatorics and campus security. Journal for Undergraduate Mathematics and its Applications, 17(2): 111-116.
First published in the Journal for Undergraduate Mathematics and its Applications, vol. 17, no. 2 (Summer 1996), pg. 111-116, by the Consortium for Mathematics and Its Applications.