### John Baez

Shared publicly -**My 14 favorite mountains**

This picture actually shows the 14 Dyck words of length 8. A

**Dyck word**is a well-formed string of left and right parentheses, like these:

(((())))

((()()))

((())()) (()(()))

((()))() (()()()) ()((()))

(()())() (())(()) ()(()())

(())()() ()(())() ()()(())

()()()()

These are, in fact, all 14 Dyck words of length 8.

What makes these strings of parentheses 'well-formed'? Something like this is not well-formed:

)())))((

A string of parentheses is

**well-formed**if when we read it from left to right, there is at each stage at least as many left parentheses as right ones, with an equal number by the time we reach the end.

In the picture below, a left parenthesis is shown as upward-slanting line segment and a right parenthesis as a downward-slanting one. The condition of being well-formed then translates into the fact that the resulting ‘mountain range’ starts and ends at ground level, and never goes below ground. So, we get nice pictures of mountain ranges!

More importantly, this gives a was to say when one Dyck word is 'taller' than another. We say w≥w′ when the mountain range corresponding to w is at least as high at all points as the mountain range corresponding to w′.

The black lines help you see when one Dyck word is taller than another! The mountain on top is taller than all the rest.

There are at least 3 other interesting ways to define a notion of ≥ for Dyck words. I wish I understood them all a bit better.

The set of all Dyck words is called the

**Dyck language**. This plays a fundamental role in computer science. We can also define Dyck languages with more than one kind of parentheses; for example,

([])(([])[]))

is a Dyck word on two kinds of parentheses. The

**Chomsky–Schützenberger representation theorem**characterizes context-free languages - also important in computer science - in terms of the Dyck language on two parentheses.

Returning to the Dyck language with just one kind of parenthesis, the number of Dyck words of length 2n is the nth

**Catalan number**. The Catalan numbers go like this:

1, 1, 2, 5, 14, 42, ...

and if you ever learn an interesting mathematical fact about the numbers 14 or 42, it's likely to be true because of this! You see, there are lots of things counted by Catalan numbers. And this is why there are several different ways of defining a notion of ≥ for Dyck words.

To dig deeper into these various notions of ≥ for Dyck words, check out my article on the

*Visual Insight*blog:

http://blogs.ams.org/visualinsight/2015/07/15/dyck-words/

The picture here was drawn by Tilman Piesk, and he put it on Wikicommons:

https://commons.wikimedia.org/wiki/File:Dyck_lattice_D4.svg

80

13

38 comments

John Baez

+

1

2

1

2

1

+Michael Nelson wrote: "The number of faces of all dimensions for a polyhedra is an ordered Bell number."

You meant to write "permutahedron", not "polyhedra". But thanks - that's the best explanation of ordered Bell numbers for me!

The n-dimensional associahedron is the space of (n+1)-ary operations of the

http://ncatlab.org/nlab/show/A-infinity-space

In fact this example came before operad theory and was key to the development of operads by Boardmann and Vogt and May.

Permutahedra are also spaces of operations of an operad!

https://books.google.com.sg/books?id=Rqh8ZgUEAmMC&pg=PA97&lpg=PA97&dq=permutahedron+operad&source=bl&ots=XLF3qrWOYZ&sig=eX7DslGk-y9ANMNn-j-tM8vEVP0&hl=en&sa=X&ved=0CB0Q6AEwAGoVChMIsPX90pf6xgIVAwiOCh2GZQ2K#v=onepage&q=permutahedron%20operad&f=false

This book is great to read but beware - the definition of operad in this book has a mistake in it.

You meant to write "permutahedron", not "polyhedra". But thanks - that's the best explanation of ordered Bell numbers for me!

The n-dimensional associahedron is the space of (n+1)-ary operations of the

**A_infinity operad**. This is a topological operad introduced by Stasheff whose algebras are spaces with a binary operation that's associative 'up to coherent homotopy'.http://ncatlab.org/nlab/show/A-infinity-space

In fact this example came before operad theory and was key to the development of operads by Boardmann and Vogt and May.

Permutahedra are also spaces of operations of an operad!

https://books.google.com.sg/books?id=Rqh8ZgUEAmMC&pg=PA97&lpg=PA97&dq=permutahedron+operad&source=bl&ots=XLF3qrWOYZ&sig=eX7DslGk-y9ANMNn-j-tM8vEVP0&hl=en&sa=X&ved=0CB0Q6AEwAGoVChMIsPX90pf6xgIVAwiOCh2GZQ2K#v=onepage&q=permutahedron%20operad&f=false

This book is great to read but beware - the definition of operad in this book has a mistake in it.

Add a comment...