info prev up next book cdrom email home

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

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

with $a_0=1$. This can also be written
\begin{displaymath}
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},
\end{displaymath} (2)

where the definition $0^0=1$ has been used. Furthermore,
\begin{displaymath}
a_n=\sum_{k=1}^n A_{n,k} 2^{n-k}=\sum_{k=1}^n A_{n,k} 2^{k-1},
\end{displaymath} (3)

where $A_{n,k}$ are Eulerian Numbers. In terms of the Stirling Numbers of the Second Kind $s(n,k)$,
\begin{displaymath}
a_n=\sum_{k=1}^n k!s(n,k).
\end{displaymath} (4)

$a_n$ can also be given in closed form as
\begin{displaymath}
a_n={\textstyle{1\over 2}}\mathop{\rm Li}\nolimits _{-n}({\textstyle{1\over 2}}),
\end{displaymath} (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

\begin{displaymath}
b_n\equiv{a_n\over n!}
\end{displaymath} (6)

satisfies the inequality
\begin{displaymath}
{1\over 2(\ln 2)^n}\leq b_n\leq {1\over(\ln 2)^n}.
\end{displaymath} (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.




© 1996-9 Eric W. Weisstein
1999-05-26