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.
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.
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-WORDSOne 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-WORDSLet 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.