読者です 読者をやめる 読者になる 読者になる

kkana's blog

新米コーダーの忘れそうなことメモ

読書メモ:プログラマの数学(5)

順列・組み合わせ

数えることは整数との対応づけ

  • 数えることは 数えたいものを整数に対応づけすること
  • 数えるときはもれ・ダブりに注意する
  • 数えるルールをつくるために、数えたいものがどんな構造をしているか・どんな性質を持っているか理解する。

数え上げの法則

法則自体は丸暗記するひつようはなくて、各法則がどのようにして「もれなく」「だぶりなく」を実現しているかに注目するのが大事。

植木算

植木算

  • 0のことを忘れない。
  • 数が小さいときは数えても確かめられるが、大事なのは一般的なルールとするとどうなるか、を考えること。
  • k個目はk-1

和の法則

  • 2つの集合にわかれているものを数えるときに使える
  • 和の法則が成り立つのは、集合の要素にダブりがない場合のみ
  • 素数と要素数を合わせてから、ダブった要素数を引く
  • 包含と排除の原理

積の法則

  • 「それぞれに対して」というフレーズがあるときは掛け算すると数えたい数が求まることが多い

置換

  • n個のものを順序を考えて並べることを置換という
  • たとえば・・3枚のカードの並べ方は1枚めの選び方は3通り、2枚めの選び方は1枚め以外のカード2枚から選ぶので、1枚めの選び方ぞれぞれに対して2通り、3枚めは残り1枚を1枚めと二枚めの選び方ぞれぞれに対して1通り・・なので321
  • 1こづつ減っていく掛け算を階乗という
  • 表記は n!
  • 0の階乗は1と定義されている(最初?だったけれど、1章ででてきた0の用途がこれ)

順列

  • たとえば・・・5枚のカードから3枚を選んで順番を考えて並べるとき、1枚めの選び方は5通り、そのそれぞれに対して2枚めの選び方は4通り、そのそれぞれに対して3枚めの選び方は3通りある。
  • 一般化するとn枚のカードからk枚を選んで並べるとき、k枚目の選び方はk-1までの選び方ぞれぞれに対してn-k+1通りある。→(n-0),(n-1),(n-2)・・(n-(k-1))までを全て掛け算している
  • 5枚から0枚選ぶ順列の総数(どうやって表記したらいいのかわからない・・5P0というやつ)は1と定義されている

樹形図

「3枚のカードから3枚を並べる順列」と、「3種類のカードから重複を許して3枚を並べる順列」は樹形図を書くと違いが一目瞭然。 樹形図は数えるものの性質を見抜く道具として使える。

組み合わせ

順序を考えずに選び出す

  • 数え方 順列と同様に「順序を考えて」数え、そのあとに重複してしまった分(重複度)を割り算する。
  • 重複度は順序を考えて重複してる分なので、置換の総数のこと

置換と順列と組み合わせの関係の図がめちゃわかりやすい
「3枚の置換」×「5枚から3枚を選ぶ組み合わせ」= 「5枚から3枚を選ぶ順列」

プログラマの数学

プログラマの数学