Unit interval parking functions and the $r$-Fubini numbers

Suppose that $\beta=(b_{1},\dots,b_{n})$ is a Fubini ranking. Then by our previous remark we know that any rearrangement is also a Fubini ranking. Thus consider the weakly increasing rearrangement of $\beta$ which we call $\beta^{\uparrow}=(d_{1},d_{2},\ldots,d_{n})$ which satisfies that $d_{i}\leq d_{i+1}$ for all $i\in[n-1]$. To show that $\beta\in\text{PF}_{n}$ it suffices to check that $d_{i}\leq i$ for all $i\in[n]$. By Definition 2.1, there exists $j\in[n]$ values $d_{1}=d_{2}=\ldots=d_{j}=1$, thus, values $d_{i}\leq i$ for all $i\in[j]$. Then, again by definition, the next entry is $d_{j+1}=j+1$, which satisfies $d_{j+1}\leq j+1$. Iterating this process, for $k>j+1$ if there are ties then $d_{k}<k$ or there is not tie and the value at $d_{k}$ is a new rank, hence $d_{k}=k\leq k$. Thus, $d_{i}\leq i$, for all $i\in[n]$, and $\beta\in\text{PF}_{n}$. ∎

We show that $\phi(\beta)$ is a unit interval parking function whenever $\beta$ is a Fubini ranking. To do so we induct on $m$, the number of distinct values in $\beta$.

If $m=1$, then $\beta=(1,1\ldots,1)$ and $\phi(\beta)=(1,1,2,3,4,\ldots,n-1)$. As a parking function, $\phi(\beta)$ parks the cars in order $1,2,\ldots,n$, and they all park within one spot of their preference. Thus $\phi(\beta)$ a unit interval parking function.

Suppose that if $\beta$ has $m$ distinct values, then $\phi(\beta)$ is a unit interval parking function. Now consider $\beta$ having $m+1$ distinct values.

Let $I\subseteq[n]$ be the set of indices where the smallest $m$ distinct values of $\beta$ occur, and let $J=[n]\setminus I$ be the set of indices where the max value of $\beta$ occurs. Note that by assumption, the entries in $\phi(\beta)$ indexed by $I$ park in the first $|I|$ parking spots, and they do so by parking at most one away from their preference.

Now consider the entries in $\beta$ indexed by $J$, which contain the values $\max(\beta)$. Since $\beta$ is a Fubini ranking, we know that the next available rank is $|I|+1$. Moreover note that $|I|+1=\max(\beta)$, as otherwise the rank $|I|+1$ would be unearned and $\beta$ would not have been a Fubini ranking. To finish building $\phi(\beta)$, we need only consider the values in index set $J$. By definition, those values in $\beta$ were all $\max(\beta)$ and in $\phi(\beta)$ they have now been replaced with the values $\max(\beta),\max(\beta),\max(\beta)+1,\ldots,\max(\beta)+|J|-2$, appearing in this relative order at the indices in $J$. We conclude by now noting that under $\phi(\beta)$ the cars indexed by $J$ park in spots $|I|+1,|I|+2,\ldots,n=\max(\beta),\max(\beta)+1,\ldots,n$. Thus, the cars indexed by $J$ parking under $\phi(\beta)$ are displaced at most one from their preference, as desired. ∎

To establish Part (1) we prove the following claims by inducting on the number of blocks in $\alpha^{\prime}$.

• •

  The weakly increasing rearrangement of an element $\alpha$ in $\text{UPF}_{n}$ is also in $\text{UPF}_{n}$.

• •

  If $\pi_{j}$ is a weakly increasing block of $\alpha^{\prime}$, then those elements appear in weakly increasing order in $\alpha$.

• •

  Any two blocks $\pi_{i}$ and $\pi_{j}$ are independent of each other, i.e. as sets $\pi_{i}\cap\pi_{j}=\emptyset$ for all $i\neq j$.

• •

  The formula in (2) holds.

Suppose $m=1$. Then $\alpha^{\uparrow}=(a_{1}^{\prime},\ldots,a_{n}^{\prime})$ is such that $1\leq a_{i}^{\prime}\leq a_{i+1}^{\prime}$, $a_{i}^{\prime}\leq i$ since it is a parking function, and $a_{i}^{\prime}\neq i$ for $i>1$ by assumption. Thus, $a_{1}^{\prime}=1$, which implies $a\leq a_{2}^{\prime}<2$. That is $a_{2}^{\prime}=1$ and car 2 parks in spot 2 and is displaced 1 spot from its preference. For car 3 to have displacement at most 1 we must have $2<a_{3}^{\prime}$ since spots 1 and 2 are occupied so that $2\leq a_{3}^{\prime}<3$, i.e. $a_{3}^{\prime}=2$. Continuing in this fashion establishes $\alpha^{\uparrow}=(1,1,2,3\ldots,n-1)$. Next we establish that $\alpha=\alpha^{\uparrow}$ by supposing that $\alpha$ is out of weakly increasing order to obtain a contradiction.

Let $i$ be the smallest index such that $a_{i}>i-1$ and there exists some $k>i$ satisfying $a_{i}>a_{j}$. Let $j$ be the largest such $k$. Parking under $\alpha$, cars $1,2,3,\ldots,i-1$ park in spots $1,2,\ldots,i-1$, respectively. Car $i$ with preference $a_{i}>i-1$ parks in spot $a_{i}$ leaving spots $i,i+1,\ldots,a_{i}-1$ unoccupied after it parks. Note that of the cars numbered $i+1,i+2,\ldots,a_{i}-a_{j}+i$, those with preferences in the set $\{i,i+1,\ldots,a_{i}-1\}$ park without displacement and those with preference smaller that $a_{j}$ get displaced one unit. Also, one of the cars with preference smaller than $a_{j}$ has parked in spot $a_{j}$. Further, any car with preference larger than $a_{j}$ parks with a displacement at most one. This is implied because $\alpha$ consists of the numbers $1,1,2,3,\ldots,n-1$ so that all numbers not equal to one appear exactly once in $\alpha$. This then ensures that spots $i,i+1,\ldots a_{i}-1$ are occupied by cars arriving and parking before car $j$. Thus, the displacement of car $j$ is at best $a_{i}-a_{j}+1>1+1\geq 2$, which contradicts that $\alpha\in UPF_{n}$. Therefore, the unique unit interval parking function consisting of a single block is $(1,1,2,\ldots,n-1)$, and it is in weakly increasing order. Furthermore, there are $\binom{n}{|\pi_{1}|}=\binom{n}{n}=1$ possible rearrangements that produce a unit parking function.

Suppose that if $\alpha\in\text{UPF}_{n}$ is such that $\alpha^{\prime}$ has $m$ distinct blocks, then those blocks appear in $\alpha$ as weakly increasing strings, and there are $\binom{n}{|\pi_{1}|,\ldots,|\pi_{m}|}$, ways to reorder $\alpha$ so that the result is again in $\text{UPF}_{n}$.

Now consider $\alpha\in\text{UPF}_{n}$ having $m+1$ distinct blocks in $\alpha^{\prime}$. We may consider the block structure of $\alpha$ as the concatenation $\alpha^{\prime}=\beta^{\prime}\gamma^{\prime}$, where the block structure of $\beta$ is given by $\beta^{\prime}=\pi_{1}|\pi_{2}|\dots|\pi_{m}$, and the block structure of $\gamma$ is given by $\gamma^{\prime}=\pi_{m+1}$. As in Observation 2.8 we may now consider both $\beta$ and $\gamma$ as unit parking functions on their own, also noting that $\max(\beta)+1=\min(\gamma)$, otherwise we would not have a parking function.

By induction, $\beta\in\text{UPF}_{n-|\pi_{m+1}|}$, and there are $\binom{n-|\pi_{m+1}|}{|\pi_{1}|\ldots|\pi_{m}|}$ ways to rewrite it as a unit parking function, by induction hypothesis. Separate from this, $\gamma$ has the form of an element in $\text{UPF}_{|\pi_{m+1}|}$, and there is one way to arrange these elements. Because $\gamma$ fills parking spots $n-|\pi_{m+1}|+1,n-|\pi_{m+1}|+2,\ldots,n$, it does not interfere with $\beta$ being a unit parking function, and thus $\beta$ and $\gamma$ can be parked “without interactions.” That is, cars can be given preferences from a valid rearrangement of $\beta$ at the same time as cars are given preferences from $\gamma$. Then if $\beta$ is a unit parking function produced by rearranging $\beta$, there are

ways that we could intermix the preferences from $\beta$ and $\gamma$. By induction, there are $\binom{n-|\pi_{m+1}|}{|\pi_{1}|,\ldots,|\pi_{m}|}$ ways to rearrange $\beta$ as a unit parking function, thus there are

ways to rewrite $\alpha$ as a unit parking function, as desired.

To prove Part (2) first note that the above proof of Part (1) implies that if $\sigma$ respects the relative orders of the entries in the blocks, then $\sigma\in\text{UPF}_{n}$. It suffices to prove the reverse direction, that given $\alpha$ a unit interval parking function, then it respects the relative order of the entries in each block. To show this, note that the set of cars with preferences within a block of $\alpha$ park independently of each other. We know that every block of $\alpha$ must be a unit interval parking function in its own right, if $\alpha$ is a unit interval parking function. From the base case of Part (1), we established that a single block is a unit interval parking function if and only if its entries are in weakly increasing order. Thus, a unit interval parking function must have all of the values within its blocks appearing in weakly increasing order, as claimed. ∎

Let $\alpha=(a_{1},a_{2},\ldots,a_{n})\in\text{UPF}_{n}$ and let $\alpha^{\uparrow}=(a_{1}^{\prime},a_{2}^{\prime},\ldots,a_{n}^{\prime})$ be the weakly increasing rearrangement of $\alpha$.

Let $I\subseteq[n]$ be the set of indices satisfying $a_{i}^{\prime}=i$ and let $m=|I|$. Then the block structure of $\alpha$ can be partitioned as the concatenation $\alpha^{\prime}=\pi_{1}|\pi_{2}|\dots|\pi_{m}$, where a new block $\pi_{j}$ begins at (and includes) each $a^{\prime}_{i}$ satisfying $a^{\prime}_{i}=i$.

Because $\alpha$ is a unit interval parking function, and thus $\alpha\uparrow$ is a parking function, we note that $a^{\prime}_{h}\leq h$ for all $h\in[n]$. This means that if $a^{\prime}_{h}=h$, and is the minimum element of a new block, this is the first occurrence of the number $h$ in $\alpha^{\uparrow}$. Therefore, there are $h-1$ elements in $\alpha^{\uparrow}$ less than $h$, all appearing in the blocks before whichever block contains $h$. Let $a^{\prime}_{h}=h\in\pi_{j}$. This integer, $h$, may then be partitioned as follows:

Therefore, in general, we have that

We also note that the elements $\min(\pi_{j})$ and $\min(\pi_{j+1})$ then have the relationship $\min(\pi_{j})+|\pi_{j}|=\min(\pi_{j+1})$. Moreover, by definition of $b_{i}$, there are exactly $|\pi_{j}|$ copies of the value $\min(\pi_{j})$ in $\psi(\alpha)$. Also, note that by definition $\alpha^{\uparrow}$ begins with 1, and so $\min(\pi_{1})=1$, and hence there exists a $b_{j}=1$ in $\psi(\alpha)$. These facts together imply that $\psi(\alpha)$ is a Fubini ranking. ∎

We count the number of Fubini rankings with $k$ blocks ($1\leq k\leq n$), where blocks are defined as in Definition 2.7. From Theorem 2.9, we know that, for each composition $(c_{1},c_{2},\ldots,c_{k})$ of $n$, the number of Fubini rankings with $c_{i}$ elements in the $i$th block is given by the multinomial $\binom{n}{c_{1},c_{2},\ldots,c_{k}}$. ∎

It suffices to show that $\phi$ and $\psi$ are inverses of each other.

First, we prove that for every $\beta\in\text{FR}_{n}$, $\psi(\phi(\beta))=\beta$. Suppose $\beta$ has $m$ distinct values, $x_{1}<x_{2}<\cdots<x_{m}$.

For each $i\in[m]$, let $I(x_{i}):=\{j\in[n]:b_{j}=x_{i}\}$ be the set of indices containing the value $x_{i}$ in $\beta$. Since $\beta$ is a Fubini ranking, we have that $1+\sum_{j=1}^{i-1}|I(x_{j})|=x_{i}$ for all $i\in[m]$. (In particular, $x_{1}=1$.) For each $i\in[m]$, $\phi$ takes the values $x_{i}$ at index set $I(x_{i})$ in $\beta$ and replaces them by the values $x_{i},x_{i},x_{i}+1,x_{i}+2,\ldots,x_{i}+|I(x_{i})|-2$ at index set $I(x_{i})$ (in that relative order) in $\phi(\beta)$.

To apply $\psi$ to $\phi(\beta)$, we first rearrange $\phi(\beta)$ into weakly increasing order, which is given by

To partition the block structure of $\phi(\beta)$ we begin by noting that, for all $j\in[m]$, since $x_{j}=1+\sum_{k=1}^{j-1}|I(x_{k})|$ and the first $x_{j}$ appears in index $1+\sum_{k=1}^{j-1}|I(x_{k})|$, the first instance of $x_{j}$ begins a new block. Thus

where, for all $i\in[m]$, we have that

Now observe that the entries in $\psi(\phi(\beta))$ are defined by

Claim: $c_{i}=b_{i}$ for all $i\in[n]$.

To prove the claim we consider the values in the index set $I(x_{i})$. In $\beta$, these are $x_{i}$’s. In $\phi(\beta)$, these are the values in $\pi_{i}$ which are $x_{i},x_{i},x_{i}+1,\ldots,x_{i}+|I(x_{i})|-2$ (still occurring at the indices $I(x_{i})$). In $\psi(\phi(\beta))$ for any $i\in I(x_{i})$, the value is $\min\{a\in\pi_{i}:a_{i}\in\pi_{i}\}=x_{i}$. So for every $i\in I(x_{i})$, $\psi(\phi(\beta))=x_{i}$ which is precisely the value of $\beta$ at every $i\in I(x_{i})$. Since this holds for all $i\in[m]$ and since $\cup_{i=1}^{m}I(x_{i})=[n]$, we have established that $\psi(\phi(\beta))_{i}=b_{i}$ (showing the lists agree at every entry). Hence $\psi(\phi(\beta))=\beta$.

For the reverse composition, we begin with a unit interval parking function $\alpha=(a_{1},a_{2},\ldots,a_{n})\in\text{UPF}_{n}$ and let $\alpha^{\uparrow}=(a_{1}^{\prime},a_{2}^{\prime},\ldots,a_{n}^{\prime})$ be the weakly increasing rearrangement of $\alpha$ and we partition the block structure of $\alpha$ as

where a new block $\pi_{j}$ begins and includes each $a_{i}^{\prime}$ satisfying $a_{i}^{\prime}=i$. For each $i\in[m]$, let $I(\pi_{j})=\{i\in[n]:a_{i}\in\pi_{j}\}$. Then use Lemma 2.11 to find $\psi(\alpha)=(b_{1},b_{2},\ldots,b_{n})$ where $b_{i}=\min\{a\in\pi_{j}:a_{i}\in\pi_{j}\}$. Note $\psi(\alpha)$ is a Fubini ranking. Now consider $\phi(\psi(\alpha))=(c_{1},c_{2},\ldots,c_{n})$.

Claim: $c_{i}=a_{i}$ for all $i\in[n]$.

To prove the claim we consider the values $c_{i}$ and $a_{i}$ where $i\in I(\pi_{j})$ for an arbitrary $j\in[m]$. Fix $j\in[m]$ and let $I(\pi_{j})=\{k_{1}<k_{2}<\ldots<k_{\ell}\}$ where $\ell=|I(\pi_{j})|$. Let $\psi(\alpha)|_{I(\pi_{j})}=\pi_{j,k_{1}}\pi_{j,k_{2}}\cdots\pi_{j,k_{\ell}}$ denote the substring of $\psi(\alpha)$ made up of the values at the indices in $I(\pi_{j})$. Note that by definition of $\psi$, $\pi_{j,k_{b}}=\min(\pi_{j})$ for all $1\leq b\leq\ell$. Let $\phi(\psi(\alpha))|_{I(\pi_{j})}=c_{k_{1}}c_{k_{2}}\cdots c_{k_{\ell}}$ denote the substring of $\phi(\psi(\alpha))$ made up of the values at the indices in $I(\pi_{j})$. By definition of $\phi$,

By construction/definition $a_{k_{1}}^{\prime}a_{k_{2}}^{\prime}\cdots a_{k_{\ell}}^{\prime}=\pi_{j}$ and $a_{k_{i}}^{\prime}=c_{k_{i}}$ for all $i\in[\ell]$. By Theorem 2.9, these values appear in $\alpha$ in the exact same relative order. Thus, $a_{k_{i}}=c_{k_{i}}$ for all $i\in[\ell]$. ∎

Given a $\text{UPF}_{m}$ in which the first $r$ values are distinct, we use the bijection in Theorem 2.5 to find a unique $\text{FR}_{m}$. We know that each of the first $r$ cars will park in its preferred spot, so each of those values will be starting a new $\pi$ block and will thus be mapped to itself in the Fubini ranking. So the Fubini ranking will start with the same $r$ distinct values as the unit interval parking function. Thus, $|\text{UPF}^{r}_{m}|=|\text{FR}^{r}_{n}|$. ∎

Let $\alpha=(a_{1},a_{2},\ldots,a_{r},a_{r+1},\ldots,a_{n+r})\in\text{UPF}^{r}_{n+r}$ be weakly increasing. As $\text{UPF}^{r}_{n+r}\subset\text{UPF}_{n+r}$, by Theorem 2.9 we know the structure of $\alpha$, meaning that there exists $r+k$, with $k\in[n]$, indices of $\alpha$ such that $a_{i}=i$. These values always begin a block $\pi_{i}$. By Theorem 2.9, we know that we can construct all elements of $\text{UPF}^{r}_{n+r}$ by permuting the blocks while keeping the relative order of the elements of each block. The number of ways to do this, for a fixed $k\in[n]$, is given by