パスカルの三角形の横列

パスカルの三角形があって、

0:              1
1:            1   1
2:          1   2   1
3:        1   3   3   1
4:      1   4   6   4   1
5:    1   5  10  10   5   1
6:  1   6  15  20  15   6   1

横列を求めたい。

例えば、6の横列を求めたいとする。

1はとりあえず置いといて。

6/1倍して、6
5/2倍して、15
4/3倍して、20
3/4倍して、15
2/5倍して、6
1/6倍して、1

漸化式にすると、

nC1 = 1
nCr = (n - r + 1) * nC(r-1) / r

何気なく使ってたんだけど、分解してみると凄いアルゴリズムだったんだなぁと思ってみた。

下降階乗冪と上昇階乗冪をうまく組み合わせてる訳だ。

反復と折り返しを付けて高速化してみた。反復は訳ありなんだけど。

(define (combi n r)
  (letrec ((end (- (quotient n 2)
                   (abs (- r (quotient n 2)))))
           (iter (lambda (acc i)
                   (if (> i end)
                       acc
                       (iter (/ (* (+ (- n i) 1) acc) i)
                              (+ i 1))))))
          (iter 1 1)))

絶対値を使えばifがいらない。絶対値もおもろいな。