Probability of consecutive floors on an elevator with more people

Question

Another user posted this question about elevator occupants, which made me curious about a harder question.

In a $t$-story building (with no basement), $n$ people get on an elevator on the first floor. Each person will uniformly at random independently wish to go to one of the higher floors and will press the corresponding button for the floor assuming it hasn't already been pressed.

What is the probability that three consecutive floors will be visited at some point during the elevator's trip carrying these passengers?

Note, I am not asking for the probability that there are only three floors visited and they all happen to be consecutive, but rather, that among the floors visited, there is a subset of them of size three that are adjacent.

My initial thoughts on the problem is that we might want to approach via "bad words" and strings, letting "+" represent that the floor was visited and "0" represent that the floor was not, we ask for the probability that the sequence of visited or not contains no substring "+++", but this doesn't account for the fact that multiple people might choose to go to the same floor, etc...

An easy approach would be simply to run simulations, but that is uninteresting so I ask if anyone has an idea on a pen+paper approach.

If someone wants specific numbers to work with, try with $n=t=10$, as that was how I mistakenly read the other user's question at first glance.

Answer 1

DISCLAIMER: Currently this post is work-in-progress. I do not have the time to think the indices and notation thorougly through right now, so I will return later and clean up my post.

Let $A(k,n),B(k,n)$ and $C(k,n)$ denote the number of "bad words" as you call them of length $n$ containing exactly $k$ visited floors "+" ending in $0,1$ and $2$ visited floors respectively. Then we can set up the system: $$ \begin{align} A(k,n)&=A(k,n-1)+B(k,n-1)+C(k,n-1)\\ B(k,n)&=A(k-1,n-1)\\ C(k,n)&=B(k-1,n-1)=A(k-2,n-2) \end{align} $$ combining these, we see that $$ A(k,n)=A(k,n-1)+A(k-1,n-2)+A(k-2,n-3) $$ which allows us to compute $A(k,n)$ recursively. Then the number $T(k,n)$ of "bad words" of length $n$ with exactly $k$ occurrences of "+" can be obtained by taking the number of "bad words" of length $n+1$ with $k$ occurrences of "+" ending with a "$0$", namely $A(k,n+1)$, and just removing the last "$0$" of each such word. We immediately have $$ T(k,n)=T(k,n-1)+T(k-1,n-2)+T(k-2,n-3) $$ where $T(0,n)=1$, $T(1,n)=n$ and $T(2,n)=\binom{n}{2}=\frac{n(n-1)}2$ for all $n\in \mathbb N$. Here is a table for $T(k,n)$ (computed using this program): $$ \begin{array}{c|cc} (k,n)&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\ \hline 0&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\ 1&0&1&2&3&4&5&6&7&8&9&10&11&12&13\\ 2&0&0&1&3&6&10&15&21&28&36&45&55&66&78\\ 3&0&0&0&0&2&7&16&30&50&77&112&156&210&275\\ 4&0&0&0&0&0&1&6&19&45&90&161&266&414&615\\ 5&0&0&0&0&0&0&0&3&16&51&126&266&504&882\\ 6&0&0&0&0&0&0&0&0&1&10&45&141&357&784\\ 7&0&0&0&0&0&0&0&0&0&0&4&30&126&393\\ 8&0&0&0&0&0&0&0&0&0&0&0&1&15&90\\ 9&0&0&0&0&0&0&0&0&0&0&0&0&0&5 \end{array} $$ We can see how each entry in this table is the sum of the neighbour to the left and then two more numbers moving diagonally left-up - like the recurrence says.

---

Given that figure, we need also to compute the number of ways $n$ people can be put into exactly $k$ bins ie. no bin is allowed to be empty, but multiple people are allowed to go into the same bin. This is the same as asking for the number of surjections $S(n,k)$ from $[n]$ to $[k]$, as Brian M. Scott so brilliantly observes in a comment below.

---

With these figures at hand, the number of unsuccesful combinations $U(t,n)$ for $n$ people and $t$ stories can be found as $$ U(t,n)=\sum_{k=1}^{t-1} T(k,t-1)\cdot S(n,k) $$ The sum did not need to go all the way up to $k=t-1$ since for most values of $t$ we have $T(k,t-1)=0$ even before $k=t-1$, but I chose the above for simplicity.