なんか最近教育とか採用の話がよく舞い降りてきて勉強できておりません。あめんばーです。
はてな、Markdownその他書けたんっすね。前回途中まで「見たまま編集」でやってましたわ。
っていうかノリで黄入記事書いてマトモにブログの外観も整理してないので、はてなブログ周辺ちゃんと整理していきたいですね。
今日は前に気になったとある等式のお話。
証明の経緯
帰納法で示せます。パスカルの三角形をなんやかんやいじっても成り立ちそうな気がする。知ってると計算量がだいぶ狭まりますね。おわり。
…という証明の流れがあまり好きでないのでちょっと考えた。
「ここまでくると感覚的な証明が絶対在る」と思いもやっとしてた。
感覚的な証明ってなんやねんってお話については自分の中でも定かじゃないのでそのうち。
格子点移動の落とし込み
と言えば「i×jの格子点マスに対して、端から端まで移動するのは何通りか」の式である。
i回縦に移動して、j回横に移動すれば到着するので、i+j回分の移動をどのタイミングで縦に、どのタイミングで横に移動するかを選べばいいので、コンビネーションである。
元々この式を見つけた時に解いた問題も格子点の問題だったはず。
左辺はまさにその式そのままで、右辺はいかにもそれを縦と横に1マスずつ増やしてくださいって感じの数式してますので増やしましょう。
スタート側かゴール側かと言いますとどっちでも無い側です。
最初は赤いエリアに入ってます。
ここで
- どのタイミングで赤いエリアから脱出するかm+1通り
- どのタイミングで赤いエリアに戻るかがn+1通り
あることがわかる。 しかもどこで出てどこで戻るかの(n+1)(m+1)通りを決めてしまえば、n以下×m以下の格子点がそのまま出てきてくれてしまうのである
なのでこの拡張した格子によるコンビネーションを求めるだけで、総和が出てきてしまう。
ただし一匹だけ例外がいますね。
出なきゃいい。なのでマイナス1。
わたしはこういう感じの話がとっても好きです。
