第2種スターリング数をO(nk/2)で求める関数

lisp

第2種スターリング数S(n,k)は、n個の区別できる要素をk個の集合(区別できない箱)にまとめる場合の組合せの数を表す。

主な注意点は以下の通り。

  • n=0のとき、0組に分ける場合が1通りで、それ以外が0通りになる。
  • n>0のとき、0組に分けられないので、k=0では0通りになる。
  • n＜kのとき、空の集合はないものとして扱うので0通りになる。

数の求め方は、

  • まず1つを取り出すと(例えばA)、残りの分け方は、1つもAと同じ組にしないか(甲)、Aと同じ組にすることを考えるか(乙)のどちらかである。
  • 甲の場合、kを1つ減らして考えられるので、残りの組合せはS(n-1,k-1)となる。
  • 乙の場合、Aを気にせずにS(n-1,k)を考えるが、Aがどのkに入るかはk通り考えられるので、組合せはkS(n-1,k)通り。
  • したがって、S(n,k)=S(n-1,k-1)+kS(n-1,k)の漸化式が得られる。

この漸化式と注意点をまとめれば求められる。詳しくは組合せ数学の教科書を参考して欲しい。


漸化式通りに第2種スターリング数を求める関数が作れ、それが1つ前の記事の関数になるが、多重再帰になっているので非常に遅い。


表にすると、数はn行目にn+1個のみ現れ、1つ上の行*1が分かれば求められるので、nの小さい列から計算すれば簡単に求められる。ということで、次の関数を書いた。

(defun stirling-2nd-kind-line (&optional lst)
  (do ((k 0 (1+ k))
       (b lst (cdr b))
       (x 0 (car b))
       (l nil (append (list (+ x (* k (car b)))) l)))
      ((null b) (append (reverse l) (list 1)))))

(defun stirling-2nd-kind (n k)
  (do ((i -1 (1+ i))
       (b nil (stirling-2nd-kind-line b)))
       ((<= n i) (or (elt b k) 0))))

計算量はO(2^n)からO(nk/2)に抑えられている(と思う)。ただ、表を作るときは同じ計算が多くなって煩わしいので、表を作る専用の関数にするか、次のような、計算コストの大きい行ごとにメモ化する関数を作るとよい(そのためにn行を求める関数を分けてある)。

(let ((tb (make-hash-table :size 47))
      (max 0))
  (defun stirling-2nd-kind-m (n k)
    (while (<= max n)
      (setf (gethash max tb)
            (stirling-2nd-kind-line (gethash (1- max) tb)))
      (incf max))
    (or (elt (gethash n tb) k) 0)))

*1:もっと細かく言えばk列まで。