重複組み合わせ（個数に制限がある場合） in Elisp

「重複組合せ」より引用：

ｎ 種のものから ｒ 個取り出す組合せ（並べ方）の総数を求めよ。
ただし、同種のもの同士に区別はなく、それぞれ a1、a2、a3、・・・、aｎ 個ずつ存在し、 ｎ＝a1＋a2＋a3＋・・・＋aｎ≧ｒ　とする。

要するに、卑近な例を挙げれば「靴下どれでも5足で1,000円。ただしどれも在庫わずか」みたいな状況における、組み合わせの数でしょうか。こういう数のことを一般的に重複組合せ（ちょうふくくみあわせ、repeated combination）と呼び、個数の制限が無い場合は _nH_m＝_m+n-1C_m = _m+n-1C_n-1 で計算することができるとのこと（数学で習ったかもしれないけど、_nH_mなんて記号は覚えていない）。

以下では、個数制限ありの場合の問題を解くプログラムを書いてみた。n種類の物が並んでいる中から、(a)先頭の物を1個取り出す場合、(b)取り出さない場合、のそれぞれについて関数を再帰的に適用して、和を取っていけばいいだけ。

;;; lat: 個数のリスト（a1, a2, ..., an）
;;; r: 取り出す数
(defun solve (lat r)
  (cond
   ((null lat) 0)                       ;リストが空なので 0
   ((zerop r) 1)                        ;最後まで取り出したので 1
   (t (+ (if (<= 1 (car lat))           ;先頭の物を取り出す場合
             (solve
              (cons (1- (car lat)) (cdr lat)) ;先頭の物を1個消費
              (1- r))                   ;あと r - 1 個取り出す必要がある
           0)                           ;在庫切れで取り出せないから 0
         (solve (cdr lat) r)))))        ;先頭の物を取り出さない場合

;;; テスト
(solve '(1) 1)
=> 1

(solve '(1 1 1) 1)
=> 3
;; 以下の3通り
;; 1 0 0 
;; 0 1 0
;; 0 0 1

(solve '(2 2 2) 3)
=> 7
;; 以下の7通り
;; 2 1 0
;; 2 0 1
;; 1 2 0
;; 1 1 1
;; 1 0 2
;; 0 2 1
;; 0 1 2

(solve '(10 10 10) 10)
=> 66

最後の 66 の信憑性に関しては、こちらのページ「重複組み合わせ」に、3種類のものが10個ずつある中から10個とる場合の数は 66 だと書いてあったので間違いないと思われる。

ここでは自然に再帰で考えたけれども、漸化式を導出して動的計画法を使うと O(n×r) で解ける。具体的な方法は「Amazon.co.jp： プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本」に書いてある。式の展開が多少面倒かもしれないが、紙と鉛筆を用意して臨めば問題ないレベルだった（数学嫌いでなければ）。