The Distribution on Permutations Induced by a Random Parking Function
A parking function on [n] creates a permutation in S_n via the order in which the n cars appear in the n parking spaces. Placing the uniform probability measure on the set of parking functions on [n] induces a probability measure on S_n. We initiate a study of some properties of this distribution. Let P_n^park denote this distribution on S_n and let P_n denote the uniform distribution on S_n. In particular, we obtain an explicit formula for P_n^park (σ) for all σS_n. Then we show that for all but an asymptotically P_n-negligible set of permutations, one has P_n^park (σ)((2-ε)^n(n+1)^n-1 ,(2+ε)^n(n+1)^n-1 ). However, this accounts for only an exponentially small part of the P_n^park -probability. We also obtain an explicit formula for P_n^park (σ^-1_n-j+1=i_1,σ^-1_n-j+2=i_2,…, σ^-1_n=i_j), the probability that the last j cars park in positions i_1,…, i_j respectively, and show that the j-dimensional random vector (n+1-σ^-1_n-j+l, n+1-σ^-1_n-j+2,…, n+1-σ^-1_n) under P_n^park converges in distribution to a random vector (_r=1^jX_r,_r=2^j X_r,…, X_j-1+X_j,X_j), where {X_r}_r=1^j are IID with the Borel distribution. We then show that in fact for j_n=o(n^16), the final j_n cars will park in increasing order with probability approaching 1 as n→∞. We also obtain an explicit formula for the expected value of the left-to-right maximum statistic X_n^LR-max , the statistic that counts the total number of lleft-to-right maxima in a permutation, and show that E_n^park X_n^LR-max grows approximately on the order n^12. In terms of car parking, the left-to-right maximum statistic counts the number of cars that park in the first available space. , number=1, journal=The Electronic Journal of Combinatorics, author=Pinsky, Ross, year=2026, month=Mar., pages=#P1.50