続 atsushifxの七転八倒

ウツ、発達障害の闘病記とIT関係のつれずれを書いていきます

「プログラマの数学 第5章 順列・組み合わせ」まとめ

プログラマの数学、5章 順列・組み合わせを読んだのでまとめ

5章は、場合の数を数える方法についてです。まずは数え方の基本から入り、順列・組み合わせについて学びます。
まずは数え方の基本


  • 場合の数を数えるとは、場合を数と対応付けてグループに分けることである

  • 場合わけでは集合論における和の法則、積の法則が使える

  • 和の法則:グループA,Bがある場合、は|A∪B|=|A|+|B|-|A∩B|

  • 積の法則:グループA,Bの組み合わせの数は|A|*|B|

次は順列と組み合わせ


  • 場合分けは、要素を順に並べるという考え方で数を数える。これを順列という

  • 単に要素を抜き出すだけの場合は、順列で要素の順番を問わない場合を考える。これを組み合わせという

  • n個の要素を並べる順列はnの階乗となる。nの階乗はn!であらわす

  • 順列はn個の要素からk個を並べる場合と一般化できる。n個からk個を並べる順列は、nPkとあらわす

  • 要素を抜き出す場合(組み合わせ)は要素の順番に寄らないため、重複した組み合わせが存在する。重複して数えた数を重複度と呼ぶ

  • n個の要素からk個の要素を抜き出す組み合わせをnCkであらわす。nCk=nPk/kPk


ポイントは、問題からこの公式が使えるパターンを見出すことです