2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ @raychou The formula that you have just edited into your deleted answer is exactly what I have just written into my notebook ,,, I just need a few more minutes to convince myself that it is correct, $\endgroup$ – Donald Splutterwit May 13 '18 at 23:47
  • $\begingroup$ oeis.org/… There are $148$ ways to do it with $4$ buttons. $\endgroup$ – Donald Splutterwit May 13 '18 at 23:54
  • $\begingroup$ These locks are called "simplex locks". You might google "simplex lock problem".. $\endgroup$ – awkward May 14 '18 at 13:14
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Im not saying youre wrong but your answer means nothing to me. You dont have conceptual explanation and you didnt develop anything. Copy paste from wikipedia for all I know. Youve left me with no real means of computing a value. Immediately jumped into Stirling numbers without explanation. No proof provided that this actually answers the question either. Is this what passes for an answer on MSE? $\endgroup$ – CogitoErgoCogitoSum May 13 '18 at 23:51
  • $\begingroup$ The Stirling numbers of the second kind count the number of ways to partition a set of $n$ labeled objects into $k$ unlabeled sets; I can reproduce the formula if you wish, but it's kind of hideous. It's done using the Inclusion-Exclusion principle. At this moment I cannot think of a prettier answer, but will certainly edit mine if I find one. $\endgroup$ – Ray Chou May 13 '18 at 23:54
  • $\begingroup$ $S(k,j)$ is a name given to "the number of way to take $k$ items and divide them into $j$ distinct piles." In your case, for $k = 3$, you might pick $j = 1$ or $2$ or $3$, hence the sum over $j$. Ray is then using a theorem that $\sum S(k,j) j!$ is known to be the $k$th "ordered Bell number" (whose definition you can look up on Wikipedia) to simplify things somewhat. $\endgroup$ – John Hughes May 13 '18 at 23:55
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ This looks to be about the nicest formula. Note to the reader: $f(n,k)$ here are (as linked in the answer) the Stirling numbers of the second kind and are quite well known by that name in combinatorics. Good work btw! $\endgroup$ – N. Shales May 14 '18 at 23:58
  • $\begingroup$ @N.Shales: Thank you! I can see that I need to associate myself with the concept of Stirling numbers instead of repeating all the groundwork all the time :). This simplifies my formula to two times the $n^{th}$ ordered Bell number, I guess. $\endgroup$ – String May 15 '18 at 9:07
  • 1
    $\begingroup$ @N.Shales: I made an update where I added that insight and acknowledged you for making me aware of it. The other answer pointed to most of it as well, but you made the connection explicit. Thank you! $\endgroup$ – String May 15 '18 at 10:05
  • $\begingroup$ Now it looks really simple: $2a_n$. :) I already upvoted your answer so I can only leave this comment in appreciation. The nearest closed form representation of Stirling numbers of the second kind is the alternating sum found in the Wikipedia reference. Usually it is derived by inclusion-exclusion but it can also be done with exponential generating functions. Thanks for the mention, I just thought you'd like to be aware of the importance of $f(n,k)$ in combinatorics. Well done deriving this without prior knowledge, that's impressive! $\endgroup$ – N. Shales May 15 '18 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.