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.

No comments:

Post a Comment