重複組合せの分割

326

n人からk個取り出す組合せ総数 $n H k$ は
n人中k人~1人の中で選抜したr人からk個取り出す組合せ総数 $\sum_{r = 1}^{k} (k - 1) C (r - 1) \times n C r$ と同値です。 $(1, 2, \dots r \dots k)$ 　　

n人中k~1人から選抜したr人からk個取り出す組合せ総数

$\sum_{r = 1}^{k} (k - 1) C (r - 1) \times n C r$

n人からr人選抜した中からk個取り出す組合せ総数

$(k - 1) C (r - 1) \times n C r$

証明

n人からk人取り出す組合せ総数は $n C k$
n個をk人に余りなく配る組合せ総数は　 $(n - 1) C (k - 1)$
これらの定理を使って

まずn人からr人に絞るため $n C r$
そしてr人から1人に対してk個中何個貰えるか割合の組合せを調べる
r人からk個貰うのはk個をr人に配ると同じだから $(k - 1) C (r - 1)$
掛け合わせて
$(k - 1) C (r - 1) \times n C r$
これをr人から1人までの場合を数えると
$\sum_{r = 1}^{k} (k - 1) C (r - 1) \times n C r$
になります。
そして
$\sum_{r = 0}^{k}$ でも問題ありません。何故なら $r$ が $0$ なら $(k - 1) - (r - 1) = (k - r)$ が $k - 1$ より大きくなりその項は $0$ となり、カウントしなくていいからです。
$\begin{array}{r} (\begin{array}{cc} k - 1 \\ r - 1 \end{array}) \end{array}$
を
$\begin{array}{r} (\begin{array}{cc} k - 1 \\ k - r \end{array}) \end{array}$ と等価である事がわかる。
これにより
$\begin{array}{r} (\begin{array}{cc} k - 1 \\ k - r \end{array}) \end{array}$ × $\begin{array}{r} (\begin{array}{cc} n \\ r \end{array}) \end{array}$
として、
下降冪二項定理から始めて
$k! \begin{array}{r} (\begin{array}{cc} n + (k - 1) \\ k \end{array}) \end{array}$ $= \sum_{r = 0}^{k} \begin{array}{r} (\begin{array}{cc} k \\ r \end{array}) \end{array} (n)_{r} (k - 1)_{k} -_{r}$ $= \sum_{r = 0}^{k} \frac{k!}{r! (k - r)!} \frac{n!}{(n - r)!} \frac{(k - 1)!}{(k - 1) - (k - r)!}$
$= k! \sum_{r = 0}^{k} \frac{n!}{r! (n - r)!} \frac{(k - 1)!}{(k - r)! ((k - 1) - (k - r))!}$

$\begin{array}{r} (\begin{array}{cc} n + (k - 1) \\ k \end{array}) \end{array}$ $= \sum_{r = 0}^{k} \begin{array}{r} (\begin{array}{cc} n \\ r \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} (k - 1) \\ (k - r) \end{array}) \end{array}$
最初に示した通りに戻す $(k - 1) - (k - r) = (r - 1)$
$\begin{array}{r} (\begin{array}{cc} (k - 1) \\ (r - 1) \end{array}) \end{array}$
それにより
$\begin{array}{r} (\begin{array}{cc} n + k - 1 \\ k \end{array}) \end{array}$ = $\sum_{r = 0}^{k} \begin{array}{r} (\begin{array}{cc} n \\ r \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} k - 1 \\ r - 1 \end{array}) \end{array}$
ヴァンデルモンドの恒等式になります。

また
$k H n = n H (k - 1) n ≧ k$
$\sum_{r = 1}^{n} (n - 1) C (r - 1) \times k C r$
になります。

例題

5人中2人選び3個取り出す組合せ
答え　　(3-1)C(2-1)×5C2 =20
5人中3人から1人まで全員選んだ場合で3個取り出す組合せ
$5 H 3 = (5 + 3 - 1) C 3 = 3 Σ r = 1 (3 - 1) C (r - 1) \times 5 C r$
5H3
= (3-1)C(3-1)×5C3
+(3-1)C(2-1)×5C2
+(3-1)C(1-1)×5C1
　
5H3
=(○｜○｜○)←【●（●●●）●】
＋(○○｜○，○｜○○)←【●●（●●）●】
＋(○○○)←【●●(●)●●】
[【】の●中から選んだ()の●を、棒の間の○に入れるイメージ]

$5 H (3 - 1) = (5 - 1) C (3 - 1) \times 3 C 3 + (5 - 1) C (3 - 2) \times 3 C 2 + (5 - 1) C (3 - 3) \times 3 C 1$

$5 H (3 - 1) = (○ │ ○ │ ○ ○ ○, ○ │ ○ ○ │ ○ ○, ○ │ ○ ○ ○ │ ○, ○ ○ │ ○ │ ○ ○, ○ ○ │ ○ ○ │ ○, ○ ○ ○ │ ○ │ ○) \times 【 (● ● ●) 】 + (○ │ ○ ○ ○ ○, ○ ○ │ ○ ○ ○, ○ ○ ○ │ ○ ○, ○ ○ ○ ○ │ ○) \times 【 (● ●) ● 】 + (○ ○ ○ ○ ○) \times 【 ● (●) ● 】$
[【】の●の中から選んだ()の●を、棒の間の○に入れるイメージ]

この問題は「ヴァンデルモンドの畳み込み」の特殊な場合です。

$5 H 3 = 2 C 0 \times 5 C 3 + 2 C 1 \times 5 C 2 + 2 C 2 \times 5 C 1$
$(5 + 3 - 1) C 3 = (5 + 2) C 3 = \sum_{r = 0}^{3} 2 C r \times 5 C (n - r)$

今回示した式は、他の二項係数を応用した確率分布にもまた違った解釈を与える。

超幾何分布

超幾何分布 $\frac{\frac{K!}{k! K - k!} \frac{N - K!}{n - k! N - K - n - k!}}{\frac{N!}{n! N - n!}}$
赤玉 $K$ 個、白玉 $N - K$ 個の計 $N$ 個の玉を壺の中から、 $n$ 個取り出すとき、赤玉がちょうど $k$ 個の確率

これを今回の公式で応用すると

$\frac{\frac{k - 1!}{r - 1! k - 1 - r - 1!} \frac{n!}{r! n - r!}}{\frac{n + k - 1!}{n! k - 1!}}$
これを使って $n$ 人から $k$ 個貰える時、
$n$ 人から $r$ 人選抜した確率が分かる。

負の二項分布

負の二項分布 $\begin{array}{r} (\begin{array}{cc} n + k - 1 \\ n \end{array}) \end{array} p^{n} (1 - p)^{k}$
$n$ 回の失敗までに $k$ 回の成功が起こる確率。これは、最初の $n + k - 1$ 回のうち $k - 1$ 回と、 $n + k$ 回目の試行が失敗することを意味します。

$\begin{array}{r} (\begin{array}{cc} k - 1 \\ r - 1 \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} n \\ r \end{array}) \end{array}$ $p^{n} (1 - p)^{k}$
これは $n$ 回の成功するまでに $k$ 回失敗する中で
連敗が $r$ 回の場合を示す。

まず最初に示した証明に分割数を使った新たな解釈を与える

分割数による公式2の別解釈

$k - 1 C r - 1$ = $\begin{array}{r} (\begin{array}{cc} k - 1 \\ r - 1 \end{array}) \end{array}$
= $\frac{k - 1!}{r - 1! (k - 1) - (r - 1)!} = \frac{k - 1!}{r - 1! k - r!} = \frac{r + (k - r) - 1!}{r - 1! k - r!}$ = $r H k - r$
$r$ 個の分割する足場となる $1$ を作り、残りの $k - r$ をその上に重ねるイメージ
重ねた後 $\begin{array}{r} (\begin{array}{cc} n \\ r \end{array}) \end{array}$ を使い $n$ カ所から $r$ 個の足場の数の組合せを数える。
例
$\begin{array}{r} (\begin{array}{cc} 5 - 1 \\ 3 - 1 \end{array}) \end{array}$ = $3 H 5 - 3$
= $(1 + 1 + 1) の$ 1 $の上に (5 - 3) を重ねる。$
$(2 + 2 + 1), (2 + 1 + 2), (1 + 2 + 2), (1 + 1 + 3), (1 + 3 + 1), (3 + 1 + 1)$
さらに(1+1+1)となる $1 \times 3 と 0 \times 0$ の組合せ
$\begin{array}{r} (\begin{array}{cc} 3 \\ 3 \end{array}) \end{array}$ を掛けるがこの場合 $3$ か所に $1$ が埋まっているため変わらない。なので $6$ 通り。
$2 H 5 - 2 ならば (1 + 1 + 0) に (5 - 2)$ を重ねて、
$(3 + 2), (2 + 3), (4 + 1), (1 + 4)$
さらに $(1 + 1 + 0)$ による $0 \times 1 と 1 \times 2$ の組合せ $\begin{array}{r} (\begin{array}{cc} 3 \\ 2 \end{array}) \end{array}$ を掛けて
$(3 + 2 + 0), (3 + 0 + 2), (0 + 3 + 2), (2 + 3 + 0), (2 + 0 + 3), (0 + 2 + 3)$
$(4 + 1 + 0), (4 + 0 + 1), (0 + 4 + 1), (1 + 4 + 0), (1 + 0 + 4), (0 + 1 + 4)$
の $12$ 通り
$1 H 5 - 1 ならば (1 + 0 + 0) に (5 - 1)$ を重ねて、
$(5)$
さらに $1 + 0 + 0$ による $0 \times 2 と 1 \times 1$ の組合せ $\begin{array}{r} (\begin{array}{cc} 3 \\ 1 \end{array}) \end{array}$
$(5 + 0 + 0), (0 + 5 + 0), (0 + 0 + 5)$
の $3$ 通り

例題

$\begin{array}{r} (\begin{array}{cc} 5 - 1 \\ 3 - 1 \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} 3 \\ 3 \end{array}) \end{array}$ $= (212) (\times ○ │ ○ │ \times ○), (221) (\times ○ │ \times ○ │ ○), (122) (○ │ \times ○ │ \times ○), (131) (○ │ \times \times ○ │ ○), (113) (○ │ ○ │ \times \times ○), (311) (\times \times ○ │ ○ │ ○)$
これは左から右に見るように、失敗(×)しても成功(○)したあと次の壁に進むことを表します最後は必ず成功で終わるので右はすべてに○です。
壁に到達したら〇になり、到到達前の成功を×にして同じ順番で表すと
$(\times \times 〇 \times 〇 \times ○), (\times 〇 \times \times 〇 \times ○), (\times 〇 \times 〇 \times \times ○), (\times 〇 \times \times \times 〇 \times ○), (\times 〇 \times 〇 \times \times \times ○), (\times \times \times 〇 \times 〇 \times ○)$
連敗が3回発生してるのが見えます。

$\begin{array}{r} (\begin{array}{cc} 5 - 1 \\ 2 - 1 \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} 3 \\ 2 \end{array}) \end{array}$
= $(320) (\times \times ○ │ \times ○ │) (302) (\times \times ○ │ │ \times ○) (032) (│ \times \times ○ │ \times ○) (230) (\times ○ │ \times \times ○ │) (203) (\times ○ │ │ \times \times ○) (023) (│ \times ○ │ \times \times ○)$
$(140) (○ │ \times \times \times ○ │) (104) (○ │ │ \times \times \times ○) (014) (│ 〇 │ \times \times \times ○) (410) (\times \times \times ○ │ ○ │) (401) (\times \times \times ○ │ │ ○) (041) (│ \times \times \times ○ │ ○)$
これを上と同じように変換して同じ順番です。
$(\times \times \times ○ \times \times ○ ○) (\times \times \times ○ ○ \times \times ○) (〇 \times \times \times ○ \times \times ○) (\times \times ○ \times \times \times ○ ○) (\times \times ○ ○ \times \times \times ○) (〇 \times \times 〇 \times \times \times ○)$
$(\times ○ \times \times \times \times ○ ○) (\times ○ 〇 \times \times \times \times ○) (〇 \times 〇 \times \times \times \times ○) (\times \times \times \times ○ \times ○ ○) (\times \times \times \times ○ ○ \times ○) (〇 \times \times \times \times ○ \times ○)$
連敗が二回起きる。
$\begin{array}{r} (\begin{array}{cc} 5 - 1 \\ 1 - 1 \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} 3 \\ 1 \end{array}) \end{array}$
$= (500) (\times \times \times \times ○ │ │) (050) (│ \times \times \times \times ○ │) (005) (│ │ \times \times \times \times ○)$
$(\times \times \times \times \times ○ ○ ○) (〇 \times \times \times \times \times ○ ○) (○ ○ \times \times \times \times \times ○)$
連敗が一回となることが見てわかる。