Today, I am going to work on an interesting counting problem.
A Dyck word is a sequence of 0’s and 1’s in which the number of 0’s exceed the number of 1’s in every initial segment of the sequence. The set of Dyck words and the set of balanced parantheses are bijective, and therefore, the number of Dyck words are given by Catalan numbers.
Now, I will call a sequence of 0’s and 1’s a strict Dyck word if in any contiguous subsequence that starts with 0, the number of 1’s are always less than or equal to the number of 0’s. Today, I am going to count the number of strict Dyck words.
It is clear that every strict Dyck word must start with a 0. Also, one cannot have two consecutive 1’s in a strict Dyck word: every 1 must be preceeded by at least one 0. So, if we take a finite sequence of 0’s and 1’s and replace every 1 with a “01” we get a strict Dyck word. This means \(D(n+k+1,k)\) the number of strict Dyck words of length \(n+k+1\) that contains \(k\)-many 1’s is \(\binom{n+k}{k}\), or better yet, \[ D(n,k) = \binom{n-k-1}{k} \] for every \(k=0,\ldots,n-1\). This means, the number of all strict Dyck words of length \(n\) is \[ D(n) = \sum_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} \binom{n-1-k}{k} \] Now, by an old result by Ganis that I saw at John D. Cook’s blog that number is \(F_n\), the n-th Fibonacci number.
Let us start with an implementation of the binomial:
(let ((table (make-hash-table :test #'equal)))
(defun binom (n k)
(or (gethash (list n k) table)
(setf (gethash (list n k) table)
(cond ((or (< k 0) (> k n)) 0)
((or (= k 0) (= n k)) 1)
((< (floor n 2) k) (binom n (- n k)))
(t (* (/ n k) (binom (1- n) (1- k)))))))))BINOMWe are ready to implement:
(defun strict-dyck (n &optional (k 0) (carry 0))
(if (> k (floor (1- n) 2))
carry
(strict-dyck n (1+ k) (+ carry (binom (- n k 1) k)))))STRICT-DYCKand we test:
(loop for i from 1 to 25 collect (strict-dyck i))(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711
28657 46368 75025)