D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
が解説を見てもさっぱりわからなかくて数日頭を悩ませているので、理解できたものから少しずつまとめていこうと思います。
まず、初っ端につまづいたのが次の一文
頂点集合 S をトポロジカルソートするとき，頂点 v ∈ S が最も右に置かれるた めの必要十分条件を考えてみます．
さっぱりわかりません。まずなんで「頂点 v ∈ S が最も右に置かれる」こと考えてるんだろ？？？な状態でした。
これについては普通の順列の個数を求めることを考えることで理解できました。
４つの要素{A, B, C, D}からなる順列について上記の意味を考えます。
上の説明の通り、{A, B, C, D}について、要素Dが一番右にくる組み合わせの個数を考えると、残りの３つの要素{A, B, C}からなる順列の組み合わせの個数と同じになります。
まぁちょっと考えればすぐわかる当たり前のことなのですが、４つの要素からなる順列のうち、３つまでの要素が決定されていたら残りの選択肢は１つしかないですもんね。
同じように、さらに要素を減らしながら個数を数えていけば順列の全ての組み合わせの個数が求まります。
以上から、要素数nの順列を求める方法を漸化式で表すと以下になります。
要素nの中から１つの要素を取り除いてできる順列の個数を、要素数n回分足しあわせたもの ということですね。要素数が４つであれば
とすればもとまるわけです。これは順列の組み合わせを求める式 n!にも一致します。
ということで、順列のこの法則に乗せるために、一番右（最後）に来る要素について考える必要があるわけですね。
なるほど〜。
今回はここまで。
