Wolfram Research

Function Repository Resource:

DyckWords

Source Notebook

Gives all possible ways to form proper brackets

Contributed by: Wolfram Staff

ResourceFunction["DyckWords"][n]

gives all possible ways to form proper sets of n pairs of brackets.

Details and Options

Three conditions define a proper set of brackets:
1. [ ] is a proper set
2. Two proper sets can be concatenated
3. A proper set can be placed anywhere inside another proper set

Examples

Basic Examples

Here is the simplest nontrivial example, with 2 pairs of brackets:

In[1]:=
ResourceFunction["DyckWords"]@2
Out[1]=

Here are the ways to nest 3 pairs of brackets:

In[2]:=
ResourceFunction["DyckWords"]@3
Out[2]=

There are five ways to do that:

In[3]:=
Length@%
Out[3]=

Dyck words are counted by the Catalan numbers:

In[4]:=
CatalanNumber@Range@10
Out[4]=

Scope

Define the helper function:

A Dyck path of length 2n units starts at the origin, goes NE or SE one unit, and finishes on the x axis:

In[5]:=
Map[ListLinePlot@*DyckPointsFromDyckWord, ResourceFunction["DyckWords"][3]]
Out[5]=

Resource History

Source Metadata

License Information