Navy bunk locker code combinations problem

Question

In the Navy we had bunk beds with a locker and lock both built in. You could gain access with a combination lock on the side that you could reprogram the code for. The lock was nothing more than several push buttons. Ive wondered for a long time now how many possible combinations there were. I believe the lock had $n=4$ buttons, but I would like to generalize to all $n\in\Bbb N$.

The system is easy enough to understand. Here are the rules:

• there are $n$ push buttons
• each button can be pressed no more than once, and clearly you needn't push any button at all.
• the locker combination can comprise of any number of distinct pressings.
• order of pressing is relevant, so its a permutation problem
• any grouping of buttons can be pressed simultaneously (wherein concurrently pressed buttons have no order).

So, for example, if there are $n=3$ buttons and we are pressing all three buttons then $(1)(2)(3)$ is a viable combination, which is distinct from $(2)(1)(3)$ and from $(3)(2)(1)$, et. cetera, totaling 6 possible permutations when pressed separately. These are three button, three pressing combinations.

But those combinations are also distinct from three button, two pressing combinations such as $(1)(23)$ and $(12)(3)$ and three button, one pressing combinations like $(123)$. These were an additional three when (some) pressings are done concurrently, but since the order of the pressings are relevant then $(3)(12)$ and $(23)(1)$ are two more. Note that $(12)=(21)$ since concurrently pressed buttons have no order. But $(1)(23)\ne (23)(1)$ since the non-concurrently pressed groups $(1)$ and $(23)$ are ordered with respect to one another.

Naturally, one can press but two of the three, one of the three, or none of the three, for a multitude of additional possible combinations.

Id like to solve this problem, but in particular for the $n=4$ case but also in the general case.

This is a problem Ive been trying to solve for a decade.

For three buttons $1,2,3$ the combinations are $(), (1), (2), (3), (12), (13), (23), (123), (1)(2), (2)(1), (1)(3), (3)(1), (2)(3), (3)(2), (1)(23), (23)(1), (13)(2), (2)(13), (12)(3), (3)(12), (1)(2)(3), (1)(3)(2), (2)(1)(3), (2)(3)(1), (3)(1)(2), (3)(2)(1)$

26 combinations unless I missed some.

I shouldnt have to specify that there is no explicit limit on the number of pressings a combination can comprise, but you are implicitly restricted by the number of buttons and the fact that each can be pressed no more than once.

Answer 1

There are $\dbinom{n}{k}$ ways to choose k objects from a set of $n$ buttons, and there are $S(k,j)$ (Stirling numbers of the second kind) ways to partition these $k$ labeled objects into $j$ different (unlabeled) sets, and $j!$ ways to order these sets. In total, that makes

$$\sum_{k=0}^{n}\left[\dbinom{n}{k} \sum_{j=0}^{k} S(k,j) \: j!\right]$$

ways. Letting $a_{k}$ denoting the $k$th ordered Bell Number, there are

$$\sum_{k=0}^n\dbinom{n}{k} a_{k}$$

different combinations.

Answer 2

UPDATE: I have since learned (thanks to N. Shales in the comment section and the other answer in part) that $f(n,k)$ are called Stirling numbers of the second kind. Furthermore $$ a_n=\sum_{k=1}^n f(n,k)k! $$ is called the $n^{th}$ ordered Bell number, and so my answer simply reduces to: $$ 2 a_n $$ Here follows my original post:

---

Fantastic! Only 12 days after answering a similar/related question, I can make use of the overkill I performed there:

In how many ways can $n$ elements be divided into $k$ distinct groups?

The answer turns out to be described by the recurrence relation: $$ f(n,k) = k\cdot f(n-1,k)+f(n-1,k-1) $$ where $f(n,0)=0$ and $f(n,1)=1$. As stated there, this is reflected in the following table: $$ \begin{array}{|r|rrrrr|} \hline &1&2&3&4&5\\ \hline 1&1&1&1&1&1\\ 2&&1&3&7&15\\ 3&&&1&6&25\\ 4&&&&1&10\\ 5&&&&&1\\ \hline \end{array} $$ and according to The On-Line Encyclopedia of Integer Sequences, this has no closed form yet.

---

From this we can construct the figure you are after, namely we have one of two situations:

1. We push all buttons during the combination. This corresponds to dividing the $n$ buttons into $k$ groups and pushing them in one of the $k!$ possible orders.
2. We push all but some set of buttons during the combination. This corresponds to dividing the $n$ buttons into $k$ groups, shuffling them to one of the $k!$ possible orders and leaving out the first group.

Hence the answer becomes: $$ 2\sum_{k=1}^{n} f(n,k)\cdot k! $$ if I am not mistaken. For $n=4$ in particular, it then must be: $$ 2(1\cdot 1!+7\cdot 2!+6\cdot3!+1\cdot 4!)=150 $$ and for $n=3$ the figure agrees with your suggested figure, namely: $$ 2(1\cdot 1!+3\cdot 2!+1\cdot 3!)=26 $$

---

I have checked the cases $n=0,1,2,3,4,5,6$ by using a little programming, and they all match the theoretical figures $1,2,6,26,150,1082,9366$ I found by the above method. Another search in The On-Line Encyclopedia of Integer Sequences showed that those figures are actually in there too.