## Friday, May 13, 2011

### Factorials and triangular numbers

These two functions are:

$$T_n = \sum_{i=1}^n {i}$$
$$n! = \prod_{i=1}^n {i}$$

There are also raising and falling versions of the factorial:

$$x^{\overline n} = \prod_{i=0}^n {x+i}$$
$$x^{\underline n} = \prod_{i=0}^n {x-i}$$

Here is the corresponding code:

(def triangular-number
(let [sum (partial apply +)]
(comp sum range inc)))

(def factorial
(let [product (partial apply *)
upto (comp (partial map inc) range)]
(comp product upto)))

(defn rising-factorial
[x n]
(apply * (map (partial + x) (range 0 n))))

(defn falling-factorial
[x n]
(apply * (map (partial - x) (range 0 n))))

(defn choose
[n k]
(/ (falling-factorial n k)
(factorial k)))

(defn multichoose
[n k]
(/ (rising-factorial n k)
(factorial k)))


The multichoose function is incredibly important because all polytopic numbers, including triangular-numbers and tetrahedral numbers can be expressed with it.

(def triangular-number
#(multichoose % 2))

(def tetrahedral-number
#(multichoose % 3))

(def pentatope-number
#(multichoose % 4))


This is the relationship between factorials and triangular-numbers. Triangular-numbers can be expressed in terms of factorials probably because the higher hyper operator, multiplication, encodes more information then addition.