Navy bunk locker code combinations problem 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.
 A: 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.
A: 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:


*

*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.

*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.
