Falling Bottles

Consider a stack of bottles of wine. There are $n$ layers in the stack with the top layer containing only one bottle and the bottom layer containing $n$ bottles. For $n=4$ the stack looks like the picture below.

The collapsing process happens every time a bottle is taken. A space is created in the stack and that space is filled according to the following recursive steps:

No bottle touching from above: nothing happens. For example, taking $F$.
One bottle touching from above: that will drop down to fill the space creating another space. For example, taking $D$.
Two bottles touching from above: one will drop down to fill the space creating another space. For example, taking $C$.

This process happens recursively; for example, taking bottle $A$ in the diagram above. Its place can be filled with either $B$ or $C$. If it is filled with $C$ then the space that $C$ creates can be filled with $D$ or $E$. So there are 3 different collapsing processes that can happen if $A$ is taken, although the final shape (in this case) is the same.

Define $f(n)$ to be the number of ways that we can take all the bottles from a stack with $n$ layers.
Two ways are considered different if at any step we took a different bottle or the collapsing process went differently.

You are given $f(1) = 1$, $f(2) = 6$ and $f(3) = 1008$.

Also define
$$S(n) = \sum_{k=1}^n f(k).$$

Find $S(10^4)$ and give your answer modulo $1\,000\,000\,033$.

If a bottle has a bottle touching from above, that one can fall into its place. Otherwise, it is “free”. And, as the collapsing process is linear (each bottle has a “predecessor” and a “successor” except for the ones at the beginning and at the end), at each step there’s basically only one decision to make: to keep the “free” bottle in place or to make it collapse. And this decision can be made for $n$ bottles (not counting the one at the beginning, and the bottle at the end is forced to collapse once no bottle is left).

So at first glance, it appears that there should be $2^n$ ways to collapse the pyramid, as at each step, we have two choices, keep the current “free” bottle, or collapse one in from above.

For $n=1$, $2^1 = 2$, but the problem said $f(1) = 1$, so the each step isn’t entirely independent. There are restrictions on the possible options.

Consider the sequence $F_n$ given by $F_n = 2^n – B_n$, where the $B_i$ are the Bell numbers given by $B_n = \sum_{k=0}^{n}{n \choose k}B_k$ with $B_0 = 1$.

This sequence produces the correct values for the problem: $F_1=1$, $F_2=6$, and $F_3=1008$.

The Bell numbers count the number of ways to partition a set. Hence, they arise naturally when each choice depends on the ones before it.

As for $S(n)$, it will be $\sum_{k=1}^n F_k$. Since $F_n = 2^n – B_n$, then you can calculate $S(n)$ directly using this formula.

As for calculating numbers modulo $1\,000\,000\,033$, note that you can take each number of a sum or product modulo $1\,000\,000\,033$ and then use these in the operations. This allows you to perform the operations with smaller numbers.

The calculation of $S(10^4)$ modulo $1,000,000,033$ is a practical computation that may need to be done in a programming environment due to the large values involved. Here’s a straightforward way of doing that in Python:

“`python
POW = 10**4
MOD = 1000000033
bell = [1] * (POW+1)
f = [0] * (POW+1)
s = [0] * (POW+1)

for n in range(1, POW+1):
bell[n] = sum((bell[j]*bell[n-j-1]) % MOD for j in range(n)) % MOD
f[n] = (pow(2, n, MOD) – bell[n]) % MOD
s[n] = (s[n-1] + f[n]) % MOD

s[POW]
“`

More Answers: