31 数学 公式&テクニック集

【公式集】§4-3.場合の数|組合せ(分ける)編

組合せとは

組合せ:いくつかのものを順序を無視して取り出したときの、1つ1つの組

C(Combination)とは

  • 異なる$n$個のものから$r$個を取り出す
    組み合わせの総数:${}_n \mathrm{ C }_r$

重複を許して取る組合せ

  • 異なる$n$個のものから重複を許して$r$個を取り出す
    組み合わせの総数:${}_{n+r-1} \mathrm{ C }_r$

順列と組合せの違い

順列は順序を考慮して1列に並べていましたが、組合せは順序を考慮しません。

例えば、ABとBAは順序が異なるので、順列の考えであれば2通りです。しかし、組合せの考えでは順序が関係ないので、AとBを取り出すという方法(その組合せ)は1通りです。

超頻出パターン3選

  • 部屋割り問題(グループ分け)
    :${}_n \mathrm{ C }_r$の積
    (区別のつかないグループ数の階乗(!)で割る)
  • 区別がつくものを区別がつくグループへ分ける
    :$n^r$
  • 区別がつかないものを区別がつくグループへ分ける
    :〇と/(区切り)の順列