Can You Make Room For Goats?

A goat tower has $10$ floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor.

One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower.

What is the probability that all $10$ goats will have their own floor, meaning no goat is left stranded on the roof of the tower?

Solution

This is exactly the classical parking function problem: $n$ cars (goats) each have a preferred spot (floor) in $\{1,\dots,n\}$, drive forward (climb up) until they find an empty spot, and fail if they run off the end (the roof). A preference list $(a_1,\dots,a_n)\in\{1,\dots,n\}^n$ lets every car park if and only if it is a parking function, and a theorem of Konheim and Weiss says the number of parking functions of length $n$ is exactly $$(n+1)^{\,n-1}.$$ There are $n^n$ equally likely preference lists in all, so the probability that every goat finds a floor is $$\frac{(n+1)^{\,n-1}}{n^{\,n}} = \frac{11^{9}}{10^{10}} = \frac{2357947691}{10000000000} \approx \boxed{0.2358}.$$

The computation

Evaluate the closed form, and cross-check it by simulating the tower: send each goat to its preferred floor, climb to the next empty one, and count the runs in which no goat ends up on the roof.

from fractions import Fraction as F
import numpy as np
n = 10
exact = F((n+1)**(n-1), n**n)
rng = np.random.default_rng(0); runs = 1_000_000; success = 0
for _ in range(runs):
    floors = [False]*n; ok = True
    for pref in rng.integers(0, n, n):       # each goat's preferred floor
        k = pref
        while k < n and floors[k]: k += 1    # climb to the next empty floor
        if k == n: ok = False; break         # ran off the top onto the roof
        floors[k] = True
    success += ok
print(float(exact), success/runs)            # 0.2357947691  ~0.2358