Perverse Sequences

Description of the problem

For a future paper, I was looking at Haefliger’s Introduction to piecewise linear intersection homology. There he calls a sequence of 0’s and 1’s \((x_n)\) perverse if

1. it starts with two zeros, and
2. every 1 is preceeded by at least one 0.

Today, I am going to write an algorithm to count all perverse sequences of a specific length.

The algorithm

Consider any sequence of \(0\)’s and \(1\)’s. Now, put a zero at the beginning, and replace each \(1\) with \(01\). If we let \(Per(n,k)\) the number of perverse sequences of length \(n\) that contains \(k\)-many \(1\)’s, we get \[ Per(n+k+1,k) = \binom{n}{k} \] In other words, \[ Per(n,k) = \binom{n-1-k}{k} \] This means \(Per(n)\) the number of perverse sequences of length \(n\) is \[ Per(n) = \sum_{k=0}^n Per(n,k) = \sum_{k=0}^{\lfloor (n-1)/2\rfloor} \binom{n-1-k}{k} \]

The implementation

Here is a lisp implementation:

(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)))))))))

(defun perverse-2 (n k)
   (binom (- n k 1) k))

(defun perverse (n &optional (k 0) (carry 0))
   (if (> k (floor (1- n) 2))
       carry
       (perverse n (1+ k) (+ carry (perverse-2 n k)))))

BINOM
PERVERSE-2
PERVERSE

Let us test:

(loop for i from 2 to 25 collect (perverse i))

(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711
 28657 46368 75025)

Did you notice something? These are the Fibonacci Numbers.