I was working on a problem in a coding competition and I began to wonder about the analytical (mathematical) solution to this problem. I am not even sure how to go about counting this. Any ideas will be helpful.
Link to the problem: http://www.acmgnyr.org/year2006/d.pdf
I am pasting the problem here, in case you don't want to click the link. Sorry about the length! The question says write a code, but I am just curious about how to do it mathematically without writing code.
A push button door lock consists of a number of push buttons B. The lock is opened by pressing the correct sequence of button combinations and then turning the doorknob. If the sequence of presses is correct, the door magically opens. A combination consists of 1 or more buttons being pressed simultaneously. A sequence consists of a series of combinations. A sequence must have at least one combination. Once a button has been used in a combination,it may not be used again in the same sequence. In addition, it is not necessary to use all the buttons in a sequence. For example, for
B=8:
(1-2-3)(4)(7-8)
is a valid sequence with 3 combinations (1-2-3), (4), and (7-8). Note that buttons 5 and 6 are not used in this sequence. (1-2-3)(2-4)(5-6)
is not a valid sequence, since button 2 appears in 2 combinations (1-2-3) and (2-4). Write a program that determines the number of valid sequences possible for given values of B.
When $B=3$ there are 25 sequences and when $B=4$, there are 149 sequences.
Best Answer
Let $B'=B\cup\{\infty\}$, where $\infty$ isn't a button. If you partition $B'$ into $k>1$ sets, that determines $k-1$ combinations - the partition with $\infty$ isn't counted - and there are $(k-1)!$ ways to order those combinations into a sequence. So $$\sum_{k=2}^{|B|+1} (k-1)!p_k(B')$$ is the count required, where $p_k(X)$ is the number of ways of partitioning a set $X$ into $k$ non-empty sets.
Now $p_n(X)=S(|X|,k)$ is the Stirling number of the second kind. So if $n=|B|$ then $|B'|=n+1$ and we get the numbers:
$$\sum_{k=2}^{n+1} (k-1)!S(n+1,k)$$
Using data from Wikipedia, we have $S(4,2)=7,S(4,3)=6,S(4,4)=1$. That yields, for $|B|=3$, the formulation:
$$1!\cdot 7 + 2!\cdot 6 + 3!\cdot 1 = 25$$
which is the value posted by user paw in comments, and disagrees with your 45.
For $n=1,2,3$ we get $1,5,25$, which is interesting.
For $|B|=4$, though, we get:
$$1!\cdot 15+2!\cdot 25 +3!\cdot 10 + 4!\cdot 1 = 149$$
Wikipedia's formula for $S(n,k)$ might be useful:
$$S(n,k) =\frac{1}{k!}\sum_{j=0}^k (-1)^{k-j}\binom{k}{j}j^n$$
Yielding:
$$\sum_{k=2}^{n+1}\frac{1}{k}\sum_{j=0}^k(-1)^{k-j} \binom{k}{j}j^{n+1}$$
A slightly different counting approach gives:
$$1+2\sum_{k=2}^n k!S(n,k)$$
For example, when $n=4$ this is $$1+2\left( 2!\cdot S(4,2)+3!\cdot S(4,3)+4!\cdot S(4,4)\right)=1+2\cdot 74=149$$
(The counting argument is as follows. We take a partition of $B$ into $k$ parts. We can use either all $k$ parts as combinations, in any order, or, when $k>1$, we can also use only $k-1$ parts. That gives us $2k!$ answers contributed by this partition.)
This formula might be better because Wikipedia says that:
$$a_n=\sum_{k=0}^{n} k!\cdot S(n,k)$$ is something called the $n$th "ordered Bell number," and the count we are looking for, for $n>0$, is thus equal to $2a_n-1$. Ordered Bell numbers (or Fubini numbers) are listed on the OEIS page as sequence number A000670.