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
Today, I am going to write an algorithm to count all perverse sequences of a specific length.
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} \]
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
PERVERSELet 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.