Function Repository Resource:

ParkingFunctionQ

Determine whether a list of positive integers is a valid parking function

Contributed by: Shenghui Yang

ResourceFunction["ParkingFunctionQ"][l]

returns True if a given list of nonnegative integers l satisfies the defining condition of a parking function, and False otherwise.

Details

Let α=(a₁,a₂,a₃,…,a_n-1,a_n). Let b₁<=b₂<=b₃<=…<=b_n-1<=b_n be the increasing rearrangement of α. Then α is a parking function if and only if b_i<=i.

Every permutation of the entries of a parking function is also a parking function.

Parking functions represent preferences for parking spots wherein each car can successfully park in its preferred spot or later.

Let f(n) be the number of parking functions of length n. Then f(n)=(n+1)^n-1.

The parking functions can also be placed in bijection with the spanning trees on a complete graph with n+1 vertices, one of which is designated as the root.

Examples

Basic Examples (2)

Test if a list is a valid parking function:

In[1]:=

Out[2]=

The following list is not a valid parking function because the second car parks at the third spot so there is no valid spot for the last car:

In[3]:=

Out[4]=

Scope (3)

Enumerate all parking functions with length three:

In[5]:=

Out[6]=

Verify the result with the length formula:

In[7]:=

Out[7]=

Show which tuples are not valid parking functions:

In[8]:=

Out[8]=

Applications (6)

The code below takes a parking function and returns the actual order in which the cars will park:

In[9]:=

$carPerm[l_?ResourceFunction["ParkingFunctionQ"]] := Module[{used = {}}, AppendTo[ used, # + First@Complement[Range[0, Length[l] - #], used - #]] & /@ l; Ordering@used]$

Give preferred parking spots for cars labelled from 1 to 7:

In[10]:=

Calculate where the cars actually park, starting with car number one in the sixth spot:

In[11]:=

Out[11]=

Find the permutation after all cars have parked (spot 6 is taken by car 1, spot 1 by car 2, etc.):

In[12]:=

Out[12]=

The jump list shows that car 1 through 4 parked in their preferred spots, car 5 had to jump one space further, car 6 had to jump 3 spots and car 7 had to jump two spots:

In[13]:=