Combination Lock

Let a combination of $n$ buttons be a Sequence of disjoint nonempty Subsets of the Set $\{1, 2, \ldots, n\}$. If the number of possible combinations is denoted $a_n$, then $a_n$ satisfies the Recurrence Relation

$$a_n=\sum_{i=0}^{n-1}{n\choose n-i}a_i,$$ (1)

with $a_0=1$. This can also be written

$$a_n={d^n\over dx^n}\left.{\left({1\over 2-e^x}\right)}\right... ..._{x=0}={\textstyle{1\over 2}}\sum_{k=0}^\infty {k^n\over 2^k},$$ (2)

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

$$a_n=\sum_{k=1}^n A_{n,k} 2^{n-k}=\sum_{k=1}^n A_{n,k} 2^{k-1},$$ (3)

where $A_{n,k}$ are Eulerian Numbers. In terms of the Stirling Numbers of the Second Kind $s(n,k)$,

$$a_n=\sum_{k=1}^n k!s(n,k).$$ (4)

$a_n$ can also be given in closed form as

$$a_n={\textstyle{1\over 2}}\mathop{\rm Li}\nolimits _{-n}({\textstyle{1\over 2}}),$$ (5)

where $\mathop{\rm Li}\nolimits _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, ... (Sloane's A000670).

The quantity

$$b_n\equiv{a_n\over n!}$$ (6)

satisfies the inequality

$${1\over 2(\ln 2)^n}\leq b_n\leq {1\over(\ln 2)^n}.$$ (7)

References

Sloane, N. J. A. Sequence A000670/M2952 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Velleman, D. J. and Call, G. S. ``Permutations and Combination Locks.'' Math. Mag. 68, 243-253, 1995.