Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 ParkingFunctionToDyckWords

Source Notebook

Convert a valid parking function into its corresponding Dyck word

Contributed by: Shenghui Yang

ResourceFunction["ParkingFunctionToDyckWords"][pf]

converts a valid parking function pf into its corresponding Dyck word.

Details

Let α=(a1,a2,a3,…,an-1,an) be a sequence of n positive integers. Let b1<=b2<=b3<=…<=bn-1<=bn be the weakly increasing rearrangement of α. Then α is a parking function if and only if bi<=i.
A Dyck word is a sequence of open ("[") and close symbols ("]") such that every close symbol has a corresponding open symbol preceding it.
Every permutation of the entries of a parking function is also a parking function.
This function establishes a bijection between parking functions of length n, considered up to permutation, and the corresponding Dyck words of length 2n.
The number of distinct parking functions of length n, considered up to permutation, is given by CatalanNumber[n].

Examples

Basic Examples (1) 

Find the Dyck words for the given parking function:

In[1]:=
pf = {6, 1, 5, 2, 2, 1, 5}; dyckWords = ResourceFunction["ParkingFunctionToDyckWords"][pf]
Out[2]=

Scope (1) 

The Dyck words is invariant for a parking function under permutation:

In[3]:=
pf1 = {2, 1, 6, 2, 2, 1, 5}; pf2 = {5, 1, 6, 2, 2, 1, 2}; ResourceFunction["ParkingFunctionToDyckWords"][pf1] === ResourceFunction["ParkingFunctionToDyckWords"][pf2]
Out[4]=

Properties and Relations (2) 

Visualize a parking function as a Dyck path that stays on or above the diagonal and does not cross it:

In[5]:=
pf = {6, 1, 5, 2, 2, 1, 5}; dyckWords = ResourceFunction["ParkingFunctionToDyckWords"][pf]
Out[6]=

Use "[" to denote a north step and "]" to denote an east step:

In[7]:=
pts = Accumulate[ Prepend[StringSplit[dyckWords, ""] /. {"[" -> {0, 1}, "]" -> {1, 0}}, {0, 0}]]; With[{bd = Length[pf]}, Graphics[{ Line[{{0, 0}, {bd, bd}}], {StandardOrange, Thick, Line[pts]}, {PointSize[0.02], StandardBlue, Point[pts]}}, GridLines -> {Range[bd], Range[bd]}, GridLinesStyle -> Directive[Gray, Dashed], Axes -> True]]
Out[8]=

Possible Issues (1) 

The input must be a valid parking function. Otherwise the function returns unevaluated:

In[9]:=
ResourceFunction["ParkingFunctionToDyckWords"][{3, 4, 1, \[Pi]}]
Out[9]=
In[10]:=
ResourceFunction["ParkingFunctionToDyckWords"][{30, 4, 1, 1}]
Out[10]=

Publisher

Shenghui Yang

Version History

  • 1.0.0 – 28 January 2026

Source Metadata

  • Citation:
    • J. Mori, "What is a Parking Function?", https://doi.org/10.48550/arXiv.2404.15372
    • Weisstein, Eric W. Dyck Language. From MathWorld--A Wolfram Resource.

Related Resources

Author Notes

For the relationship between parking functions, rooted forests, non-crossing partitions of set,and Dyck paths, see the referenced note by R. Stanley.

License Information