Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

組み合わせの種類まとめ

どれが使えるのか混乱することがあるため、考え方を自分なりにまとめることとした。

数え上げ系は頻繁に出てくるので、この本をいつか読んで理解を深めたい。

nCk: 組み合わせ

n個の中からk個を選ぶ。

これはn個のマスが並んでいて、そこにTFをつけていき、Tの合計がkの場合の数である。

つまり、(T,F,T)と(T,T,F)は違う。

nPk: 順列

nCkは選び方だけに着目しているが、nPkは選んだ順番が違う場合も違う場合も別カウントをする。

つまり、nPk = nCk * k!

nCkからnPkを考える方が楽だと思う。

nHk: 繰り返しあり組み合わせ

重複ありという言葉はわかりにくい。

x1+x2+x3+...xn = k, xi>=0

となるような(x1,x2,...xn)の数

nSk: スターリング数

n個のマスが並んでいて、

ここに適当に1からkまでの数字を書く場合の数。ただし、

  • 全部の数字は使う必要がある
  • 数字を入れ替えても同じものは同一と数える

例えば、5S2であれば、

12222,21222,22122,22212,22221,11222,12122,12212,12221,21122,21212,21221,22112,22121,22211

の15通り。

分割数: P(n,m)

nHkのうち、数字を入れ替えて同じものは同一と数える場合

例えば、1+4+1と1+1+4は同じものと数える。

カタラン数: Cn

カタラン数についてはこちらで話した。

www.rustforbeginners.com