Combination Lock

Consider a combination lock consisting of n buttons that can be pressed in any combination (including multiple buttons at once), but in such a way that each number is pressed exactly once. Then the number of possible combination locks a_n with n buttons is given by the number of lists (i.e., ordered sets) of disjoint nonempty subsets of the set {1,2,...,n} that contain each number exactly once. For example, there are three possible combination locks with two buttons: {{1,2}}, {{1},{2}}, and {{2},{1}}. Similarly there are 13 possible three-button combination locks: {{1,2,3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}}, {{1},{2},{3}}, {{1},{3},{2}}, {{2},{1},{3}}, {{2},{3},{1}}, {{3},{1},{2}}, {{3},{2},{1}}.

a_n satisfies the linear recurrence equation

 a_n=sum_(i=0)^(n-1)(n; n-i)a_i,

with a_0=1. This can also be written


where the definition 0^0=1 has been used. Furthermore,

a_n=sum_(k=1)^(n)<n; k-1>2^(n-k)
=sum_(k=1)^(n)<n; k-1>2^(k-1),

where <n; k> are Eulerian numbers. In terms of the Stirling numbers of the second kind S(n,k),


a_n can also be given in closed form as


where Li_n(z) is the polylogarithm. The first few values of a_n for n=1, 2, ... are 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... (OEIS A000670).

The quantity


satisfies the inequality


Explore with Wolfram|Alpha


Sloane, N. J. A. Sequence A000670/M2952 in "The On-Line Encyclopedia of Integer Sequences."Velleman, D. J. and Call, G. S. "Permutations and Combination Locks." Math. Mag. 68, 243-253, 1995.

Referenced on Wolfram|Alpha

Combination Lock

Cite this as:

Weisstein, Eric W. "Combination Lock." From MathWorld--A Wolfram Web Resource.

Subject classifications