お題 算数 ～羊と狼

お題　算数　～羊と狼（場合の数・道順解き）　カタラン数

ー

 

　【問題】　おおかみ４匹とヒツジが４匹います。　　　いま、これらのうち何匹かを１つの檻にいっしょに入れることを考えます。

　ただし、同数の時までは大丈夫ですが、おおかみはヒツジより数が多くなるとヒツジを食べてしまいます。

　食べられないように檻に入れる入れ方は何通りありますか。

★☆　時節項⇊画像の後に答えがあります。☆★

--　　　　　　　　　　　　　　　　　　　　　　　　　オオカミ、狼　หมาป่า　/mǎa pàa　動物 　※Weblio先生作　既出語　　　　　　　　　　　　　　　　　　　　　ヒツジ、羊　 แกะ 　/kɛ̀ʔ　※タイ語のメモ帳先生作　既出語

 

 

ーーーーーーーー　　　　　　　　　　　　　　　　　　　　　Ｍ：【カタラン数　とは　　】　　

 

「カタランの定数」とは異なります。

　初等組合わせ論におけるカタラン数（カタランすう、: Catalan number）は、★ベルギーの数学者ウジェーヌ・カタランに因んで名付けられた自然数のクラスである。

　n番目のカタラン数 C_n は

C n = 1 n + 1 ( 2 n n ) = ( 2 n ) ! ( n + 1 ) ! n ! ( n ≥ 0 )

で表される。　　　　　　　　　　　　　　　　　　　　　n = 0, 1, 2, … に対してカタラン数は

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, …（オンライン整数列大辞典の数列 A000108）となる

カタラン数の意味

カタラン数は様々な意味付けがなされている。以下に例を示す。

➊　()を正しく並べる方法

例えば3組の () を正しく（つまり「開き」と「閉じ」が一対一に対応するように）並べる方法は、「((()))」「()(())」「()()()」「(())()」「(()())」の5通りある。これが C₃ = 5 に対応している。())()) や )(()() といった形は () を正しく並べていないのでカウントしない。

➋　二分木

　C_n は、n個の分岐を持つ（n + 1枚の葉を持つ）二分木の総数である。　　　　　　　　　　　　　　　　　　　　　　上記の図は C₃ = 5 の場合に対応している。

➌　格子状の経路数え上げ

C_n は、縦横 nマスずつの格子において、次の図のように対角線を跨がずに格子点を通って、向かい合った点を最短距離で繋ぐ道順の総数と説明できる。

　上記の図は C₄ = 14 の場合に対応している。

➍　多角形の三角形分割

n + 2個の辺からなる凸多角形を、頂点どうしを結ぶ線を互いに交差しないように引いて、n個の三角形に切り分けることを考える。この分け方の場合の数は、カタラン数 C_n である。以下の図は n = 4 の場合である。

詳細は「多角形の三角形分割」を参照

➎　平面グラフの交差

2n人が円になって手を交差させないで握手をする場合の数はカタラン数 C_n である。

➏　非交差分割

集合 {1, 2, …, n} の非交差分割の数はカタラン数 C_n である。

性質

カタラン数は

C n = ( 2 n n ) − ( 2 n n − 1 )  for  n ≥ 1

と表せる。

漸化式では

C 0 = 1 , C 1 = 1 , C n + 1 = 2 ( 2 n + 1 ) n + 2 C n = ∑ i = 0 n C i C n − i = C 0 C n + C 1 C n − 1 + C 2 C n − 2 + ⋯ + C n C 0

となる。

母関数は

1 − 1 − 4 x 2 x = ∑ n = 0 ∞ ( 2 n n ) x n n + 1

となる。

n が十分大きいとき、次の式でカタラン数を近似することができる（なおこれは★ウォリスの公式から証明できる）：

C n ∼ 4 n n 3 / 2 π .

n = 2^k − 1（★メルセンヌ数）のときのみ C_n は奇数となり、それ以外の n における C_n は偶数となる。

(Wiki)

 

 

ーーー　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　初版20240111　　昨日の東京都心大手町最低気温１．７℃　最高気温１２．３℃　どうりで。外に居ると寒い気がした、、

ー時節項追記前日深夜未明迄　※10水の内容が中心　　　　①▷　　　【①能登地震関連】　　▷能登地震　津波の最大浸水高　５．１ｍか 21:45　　＞　高くなった　　　　▷マジンガーZも被害　能登観光　打撃 16:49　　＞　永井豪記念館も被災に遭ったということか、、　　　▷志賀原発　一部で想定超の揺れ　確認 23:01　　　　▷町戻り　唖然　波打つ道路に肩落とす 19:10　　　　▷水も薬もない　悪条件重なる　避難所 20:23　　　　▷124h振り　救出　地道な聞き取り端緒 21:16　　　　▷使えないゴミ　一方的な支援に　怒り 22:44　　　　▷二次避難所　６０００人分　確保 15:19　　　　▷被災者に公営住宅　提供　準備進む 18:52　　　　▷１１木朝　能登は氷点下　寒さ対策を 18:33　　　　▷被災地　停電・通信障害の復旧　難航 19:42火　　　　▷「大丈夫」被災地で我慢する　子供 6:37　　　　▷被災日深刻　トイレトレーラー　続々 7:48　　　　▷復興復旧　新年度予備費　倍増検討 22:44　　　　▷能登先端へ自衛隊　地理的　制約も 8:34　　　　▷石川　５６の小中学校　学校の見通したず 7:25　　　　▷日本航空石川　学校ごと　一時避難 7:25　　＞　山梨甲斐の日本航空高校山梨シャンパス敷地内に仮校舎や寄宿舎を造り、4月から全校生徒600人が一時拠点を移す、と発表　　　　▷北陸　少しの雨でも土砂災害　警戒 6:54　　　　　　　➊▶　　　　　　　②　　　▷政治刷新本部　安倍派が最多　１０人 21:48　　＞　何のための会？　　　　▷西村氏ら安倍派幹部　再聴取　特捜 6:24　　　　　　　➋　　　▶台湾総統選前　圧力強める　中国 9:04　　　　▶中国　台湾問題　絶対妥協せず 17:24　　　　▶報復　露・ウで民間人死者　１００人規模 9:12　　　　▶ヒズボラ司令官殺害　専科　拡大も 18:04　　　　▶仏　新首相に３４歳ガブリアエル・アタル氏　同国最年少 21:59火　　　　　　　③　　　▷建築業　倒産急増　地域経済に懸念 19:05　　　　▷近鉄　特急列車の喫煙室　廃止へ 16:37　　＞　未だあったんだ　　　　▷東京株　年内に史上最高値　超えるか？ 19:53　　＞　年内？　　　▷Ｔポイント　4･22　名称消滅 21:16火　　＞　三井住友と、青と黄色の「Ｖポイント」カードに統合するとのこと。。　　　　▷BS配信問題　「冤罪」前田晃伸前NHK会長　稲葉現会長「残念」 8:14　　　　▷ホンダ　新型EV「０シリーズ」　公開 8:33　　　　▷経団連会長　万博の延期　否定 23:59火　　　　　　　➌　　　▶Ｘ　年内にも個人間　送金開始 18:33　　　　　　　　　　　④▷➍▶　　　　　　　⑤▷　　　　　　　➎　　　▶単年で大谷超え　エムバペ獲得へサウジが年棒１１００億円　ギガオファー準備 20:11火　　　　　　　⑥　　　▷辺野古　着手　玉城氏「誠に遺憾」21:27　　　　　　　➏　　　　　　▶米ボーイング事故　CEO　ミス認める 13:18　　　　　　　　　⑦▷➐▶　　　　　　　　⑧　　　▷ガキ使　２８日以降　松本抜きに 22:01　　　　▷映画　ガンダムSEED　１８年経て完成 23:16　　　　▷昔は一家に一冊　「家庭の医学」の今 16:57　　　　▷福男選び　一番福に　１９歳大学生 7:21　　　　　　　　➑　　　▶大規模太陽フレア　発生も　影響は 19:49　　　　　　　⑨　　　▷去年の福男・JR西、植本亮太さん　目指す　プロ野球 17:54　　＞　２４年が解禁対象だとか、、　　　　▷札幌ドーム　命名権　募集 21:53火　　＞　でも、開催ないし、、　　　⑨【主な契約更改情報】　　▷　　　　　　　➒　　　▶今永　カブスと正式契約　22億円と米報道 11:48　　＞　カブスにまた日本人コンビ　誠也＆今永 10:09　因みにマイナーには昨季Deのエスコバー、前阪神・ブルワーも居るとの事　　　　▶ポスティング　残すは上沢直之　レイズとオリオールズ興味か 10:33　　　　▶ほぼ大谷　中日・柳のユニ　売り切れ 18:44　　　　　　　⑩　　　▷細川たかし　７３歳　再婚していた 19:27　　　　　　　➓▶　　　　　　　⑪【Ｊ関連】　　▷嵐５名連名　被災地へ６７５０万円　寄付 0:53

 

ー　　　　　　　　　　　　　　　　　　　　　　　　（画像・　1）　羊イメージ。。　　／アメブロ

　

（画像・）／　（画像・）／

 

ー

☆★　こたえ　☆★　⇊　　　　　　　　　　　　　　　　　答え；　１９（通り）　　　　　　　　　　　　　　　　　考え方；　秀逸な動画サイトがありましたのでご紹介⇊

https://youtu.be/l_HnnJetRpY?list=PL--P-5-AQqHmehG9hYupnXwgtuEHx_CZw

 

【類題】　ヒツジとオオカミ｜中学受験家庭教師　2015-03-07 12:26:59　テーマ：テクニック

　オオカミが３匹、ヒツジが６匹います。これら９匹を１つのおりの中に１匹ずつ順に入れることにしました。この時入れる順番について、次の問いに答えなさい。

（１）入れる順番は全部で何通りありますか。

（２）おりの中のヒツジの数が、いつもオオカミの数より多くなっているような順番は何通りありますか。

　　　　　　　　　（四谷大塚のテキストより）

 

解説

（１）オオカミ３匹とヒツジ６匹の間で区別することはできません。したがって組み合わせです。

　　９から３を取る組み合わせですから、

　　（９×８×７）／（１×２×３）＝８４　　　　　　　　　答え８４通り

 

（２）いま縦にヒツジの数を、横にオオカミの数をとった図を考えます。

　　

 

１→→→５→→１４→→２８　　

p;quot;; mso-fareast-theme-font: minor-fareast; mso-hansi-mso-hansi-theme-font: minor-latin">↑　　　↑　　　↑　　　↑

↑　　　↑　　　↑　　　↑

１→→→４→→→９→→１４

↑　　　↑　　　↑　　　↑

↑　　　↑　　　↑　　　↑

１→→→３→→→５→→→５

↑　　　↑　　　↑　　　

↑　　　↑　　　↑　　　

１→→→２Ｄ→→２　　　×

↑　　　↑

↑　　　↑　　

１Ｃ→→１　　　×　　　×

↑　　　

↑　　　

１Ｂ　　×　　　×　　　×

↑　　　　　　

↑　　　

Ａ　　　×　　　×　　　×

この図において上に行くほどヒツジをおりに入れていった事を、右に行くほどオオカミをおりに入れていった事を表します。Ａ点から出発します。ヒツジの数がいつもオオカミの数より多いわけですから、まずはヒツジを入れなければなりません。したがってＡ点からは右には行けず、上に行きます。これが１通りです。そうするとＢ点につきます。ここでオオカミを入れると、ヒツジとオオカミの数が同じになってしまいます。したがってＢ点からは上にしか行けず、右には行けません。Ｃ点まで来るとオオカミを１匹入れてもヒツジの方が多いのでかまいませんし、またヒツジを入れることもできます。Ｃ点からはオオカミ，ヒツジという順番で入れてもよいし、ヒツジ，オオカミという順番で入れても構いません。したがってＤ点までの入れ方は２通りあるということです。このように横に４つ、縦に７つの表のようなものを作り、そこに横より縦の方が多くなるように注意しながら、縦と横の和を書き込んでいきます。ちょうど通る道順を数えるようなやり方です。これによって簡単に問題を解くことができます。この方法は高レベルの入試問題としては見かける問題ですが、問題文を読んだだけではこのやり方で解けるということに気が付かないほど応用されたものもあります。難関校を目指す人はこのような代表的な問題でテクニックを叩き込んでおいて、難問を見たときに「あれだ！」とひらめくような訓練を積んでおく必要があります。

 

答え２８通り

ー