2nCnー2nCn-1＝(1/n+1)2nCn (カタラン数)が直観的に理解できますか？

質問

(2n)Cnー(2n)C(n-1)＝(1/n+1)(2n)Cn (カタラン数)についてです。

式変形では成り立つことが分かるのですが、
直観的に当たり前だと思えません。

この式がなぜ成り立つのかを式変形ではなく、組合せの考え方で
日本語で説明できる方はいませんか？

よろしくお願いします。

回答No.3

kumipapa · ベストアンサー

Ｃ (2n,n) － Ｃ (2n,n-1) = (1/(n+1))Ｃ (2n,n)
ちょい間接的ですが、
Ｃ (2n,n-1) = (n / (n+1)) Ｃ(2n,n)
を言葉で説明したのでは駄目でしょうか？
2n 人から n-1 人を選ぶ組み合わせの数 Ｃ (2n,n-1) を、2n 人から n 人を選ぶ組み合わせの数 Ｃ (2n,n) から求めてみる。
2n 人から n 人を選ぶ組み合わせは Ｃ (2n,n) 組できるが、各組から誰か一人を除いて n-1 人の組にすると考えると、誰を除くかで各組で n 通り、そうしてできた n-1 人の組み合わせの重複は n + 1 通り（∵ できた n-1 人の一組を固定して考えると、その組について除かれた人が n+1 人いるので）。
∴ Ｃ (2n,n-1) = (n / (n+1)) Ｃ(2n,n)
∴Ｃ (2n,n) － Ｃ (2n,n-1) = (1/(n+1))Ｃ (2n,n)
ちょっと不完全燃焼。

お礼

どうもありがとうございます！
まさに自分の求めていた回答です！

>Ｃ (2n,n-1) = (n / (n+1)) Ｃ(2n,n)
私もこの形で考えてたんですが、思い付かなかったです。

>ちょっと不完全燃焼。
直接一発で（1/n）でＣ (2n,n）を割る説明ってことですよね。
噂ではあるらしいんですけど、まだ分かってません。

自分としてはここまでの説明でも十分満足してます。
どうもありがとうございました！

回答No.2

PRFRD

>>ANo.1
申し訳ないです，全く対応してないですね．ボケてました．
忘れてください．

補足

わざわざご訂正ありがとうございます。

また何かありましたらよろしくお願いします。

回答No.1

PRFRD

あくまで一つの解釈ですが……．
二項係数を C(n,r) などと書くことにします．

カタラン数の一つの（組み合わせ的な）定義として
「n 個の開き括弧と n 個の閉じ括弧からなる文字列のうち
　括弧の対応が正しくついているものの総数」
というものがあります．

この値を「全ての文字列の個数 - 正しくない文字列の個数」
で評価した式が，C(2n,n) - C(2n,n-1) です．

まず，C(2n,n) が全ての文字列の個数であることは，
2n 個のスペースに n 個開き括弧を置くことを考えればわかります．

次に，C(2n,n-1) が正しくない文字列の個数であることは，
少し複雑ですが，次の手順を考えれば分かります：
　1. 2n 個のスペースに n-1 個開き括弧を置く．
　2. 左詰めで閉じ括弧を一つづつ置いていく．
　3. 式が正しくなくなったら開き括弧を置く．
　4. 残りを閉じ括弧で詰める．
この方法で任意の不正確な文字列を一通りに書けるので (*)，
C(2n,n-1) が不正確な文字列の総数と等しくなります．

(*) は，一目直感的でないかもしれませんが，
色々文字列を書いてると，正しいことが分かります．

補足

詳しいご説明どうもありがとうございます。

まだ少し理解できないのですが、

「C(2n,n-1) が正しくない文字列の個数である」ことを調べる
手順１～４において

例えばn＝５として考えた時、
全部で10のスペースを左から順に(1)～(10)とします。

１つの正しくない文字列として
例えばスペース(4)(5)(8)(9)(10)に開き括弧が入った場合は・・・※※
手順１でどこのスペースに4個の開き括弧を入れた場合・・・※※※と考えればよいのでしょうか？

「※※」と「※※※」は1対1に対応しているはずだと思うのですが・・・。