TOPICS
Search

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,
(1)

with a_0=1. This can also be written

a_n=(d^n)/(dx^n)(1/(2-e^x))|_(x=0)
(2)
=1/2sum_(k=0)^(infty)(k^n)/(2^k),
(3)

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

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

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

 a_n=sum_(k=1)^nk!S(n,k).
(6)

a_n can also be given in closed form as

 a_n=1/2Li_(-n)(1/2),
(7)

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

 b_n=(a_n)/(n!)
(8)

satisfies the inequality

 1/(2(ln2)^n)<=b_n<=1/((ln2)^n).
(9)

Explore with Wolfram|Alpha

References

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. https://mathworld.wolfram.com/CombinationLock.html

Subject classifications