Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 DyckWords

Source Notebook

Give 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; and (3) a proper set can be placed anywhere inside another proper set.

Examples

Basic Examples (3) 

Here is the simplest nontrivial example with two pairs of brackets:

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

Here are the ways to nest three 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]:=
Length@ResourceFunction["DyckWords"][#] & /@ Range[10]
Out[4]=
In[5]:=
CatalanNumber@Range@10
Out[5]=

Scope (2) 

Define the helper function:

In[6]:=
DyckPointsFromDyckWord@word_ := Prepend[ Accumulate[ StringSplit@StringReplace[ word, {"[" -> "[ ", "]" -> "] "} ] /. {"[" -> {1, 1}, "]" -> {1, -1}} ], {0, 0} ]

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

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

Publisher

George Beck

Version History

  • 1.0.0 – 08 July 2019

License Information