Irreducible Dyck Words

Description of the problem:

A sequence of equal number of 0’s and 1’s is called a Dyck word if tracing from left to right, the number of 1’s do not exceed the number of 0’s preceeding it. For example “$ 0 0 1 1 0 1 \(" is a Dyck word but "\) 0 1 1 0 1 0 $” is not.

Notice that if we concatenate two Dyck words we get another Dyck word. I will call a Dyck word reducible if it is such a concatenation of two Dyck words, otherwise I will call it irreducible. Today, I will write a lisp function that generates all irreducible Dyck words of a given length.

A simplicification

All Dyck words start with a 0 and they all end with a 1. Assume we have a Dyck word of length \(2n\) with \(n\geq 2\). If this word’s beginning 0 were to be followed by a 1, then it would be reducible since the subsequence 1 were to be preceeded by 0 it would have been irreducible. So, all such irreducible Dyck words are of the form \[ 0 0 a_1 \cdots a_k 1 1 \] where \(k\geq 0\), and “\(0 a_1 \cdots a_k 1\)” is itself is a Dyck word.

An implementation

I already have an implementation that yields the collection of all Dyck words of a given length from an earlier post.

(defun dyck-words (n &optional (a 0) (b n) (acc (list nil)))
  (labels ((insert (i xs) (mapcar (lambda (x) (cons i x)) xs)))
    (if (= a n)
        (mapcar (lambda (x) (append (loop repeat b collect 0) x)) acc)
        (union (dyck-words n (1+ a) b (insert 1 acc))
               (if (> a 0) (dyck-words (1- n) (1- a) (1- b) (insert 0 acc)))))))

DYCK-WORDS

One warning, the parameter is \(n\) but the function returns all Dyck words of length \(2n\). We just modify it:

(defun irreducible-dyck-words (n)
   (cond ((< n 1) nil)
         ((= n 1) '((0 1)))
         (t (mapcar (lambda (xs) (append '(0) xs '(1))) (dyck-words (- n 1))))))

IRREDUCIBLE-DYCK-WORDS

Let us check:

(irreducible-dyck-words 5)

((0 0 0 0 1 1 1 0 1 1) (0 0 0 1 0 1 1 0 1 1) (0 0 1 0 0 1 1 0 1 1)
 (0 0 1 0 1 0 1 0 1 1) (0 0 0 1 1 0 1 0 1 1) (0 0 0 1 1 0 0 1 1 1)
 (0 0 1 0 1 0 0 1 1 1) (0 0 1 0 0 1 0 1 1 1) (0 0 0 1 0 1 0 1 1 1)
 (0 0 0 0 1 1 0 1 1 1) (0 0 0 0 1 0 1 1 1 1) (0 0 0 1 0 0 1 1 1 1)
 (0 0 1 0 0 0 1 1 1 1) (0 0 0 0 0 1 1 1 1 1))

Let us count them too.

(mapcar #'length (loop for i from 1 to 14 collect (irreducible-dyck-words i)))

(1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900)

Unsurprisingly, these are the first 14 Catalan numbers since there is a 1-1 correspondence between Dyck words and paranthesizations of words.