重複組合せ - 数学 @ ウィキ

重複組合せ

「重複組合せ」とは、同じものを、いくつかのグループに分ける方法の数のことです。

例：区別のつかない ○ を、X・Y・Z の 3 人に分ける。

基本アイデア

丸が 6 個あるとする：
○ ○ ○ ○ ○ ○

3人に分けるには 領域が 3 つ必要。
領域を作るには 仕切り | が 2 本必要。

領域の意味

左の棒より左 … X の取り分
2本の棒の間 … Y の取り分
右の棒より右 … Z の取り分

具体例

(2,2,2) の場合：○ ○ | ○ ○ | ○ ○

(4,0,2) の場合：○ ○ ○ ○ | | ○ ○

(0,0,6) の場合：| | ○ ○ ○ ○ ○ ○

どんな配り方でも「○ 6個 と ｜ 2本」の並べ方で一意に表せる。

重複組合せの個数

n個のものをrグループに分けるとき、
○ … 個
｜ … 本
全体の長さ …
になる。

同じ ○・同じ｜なので、同じものを含む順列の公式が使える：

✔ 重複組合せの公式

になる。
この系統の問題では「0個のグループが出ないように」みたいな応用？問題が多いので正直この公式ではなく考え方を覚えた方がいい。

練習問題

[1] 区別のつかない 6 個のメロンを 3 人に分ける

...

#ref error ：画像を取得できませんでした。しばらく時間を置いてから再度お試しください。

!}{6!\,2!}=28
)

[2] 5 個の飴を 4 人に配る

...

#ref error ：画像を取得できませんでした。しばらく時間を置いてから再度お試しください。

!}{5!\,3!}=56
)

[3] 10 個から重複ありで 3 個選ぶ

...

#ref error ：画像を取得できませんでした。しばらく時間を置いてから再度お試しください。

!}{3!\,9!}=220
)

まとめ

区別なし n 個
区別あり r グループ
仕切り r−1 本
同じものを含む順列で求める

公式：

おまけ

n個のものをrグループに分ける組み合わせをと書くことがあるらしい。