Question

💓✨🐢

数学A 順列　カタラン数

写真の赤ペンを引いたところがわかりません。
なぜ→3、↑5の場合のみを考えるのでしょうか？→4、↑4でも波線部分を通る場合もあるのにそれについては考えないのですか？
教えてくださると嬉しいです🙏

質問わかりにくくてすいません。質問についてわからないところがあったら教えてください。

参考事項 カタラン数
an個, bn個の計2個を1列に並べるとき, a よりも多くの6が先に並ばない
ような並べ方の総数を カタラン数(*1) という。この数について考えてみよう。
例えば,n=1のときabの1通り; n=2のとき aabb, abab の2通り;
つまり, n番目のカタラン数を C とすると
n=3のとき aaabbb, aababb, aabbab, abaabb, abababの5通り
[図1]
C=1, C2=2,C3=5
しかし, n=4のとき,同じように列を書き出して調べるのは大変。
そこで,αを, b を ↑に対応させると, カタラン数は, [図1] のA
からBに行く最短経路の数と同じになる。(*2)
この数は, 前ページの検討でも説明したように, 各交差点を通過す
る経路の数 ([図1] の数字) を書き込むことによって, 求めることが
できる。 →図から14通り
2
55
12
13
A 111
[図2]
B'
... ①
1
I
また, 練習 30 の検討 (解答編 .265) のように考えてみると,
[図2] のような破線部分の経路があるものと仮定したとき, Aから
Bに行く最短経路は4個 14個の順列と考えて 8C4
更に, A から B' に行く最短経路は3個 15個の順列と考えて
8C3
②
ゆえに、 ①②から
*****
8C4-8C3-70-56=14
証明は省略するが, 同様に考えることにより, Cn=2Cn-2Cn-1 であ
ると推測できる。
ここで
(2n)!
(n-1)!{2n-(n-1)}!
(2n)!
2nCn-2nCn-1=
n!(2n-n)!
(2n)!{(n+1)-n} (2n)!
1
=
=
n!(n+1)!
n!(n+1)! n+1 n!n!
よって, カタラン数 C は次のように表される。
==
A
(2n)!
2n Con
=
n+1
123456
14 B
6
4
7
8
Cn=2nCn-2nCn-1=
2nCn
n+1
カタミンの
n
カタラン数
Cn
12 5 14 42 132429 1430

順列 カタラン数

Answer 1

✨ ベストアンサー ✨

kk08

本問では最短経路を問われているからでは無いでしょうか？

💓✨🐢

回答ありがとうございます！どうして8c3を8c4からひくんですか？