12823：場合の数…凸38角形と辺を共有しない17角形の個数...

問題12823・・・やどかりさんのブログ https://blogs.yahoo.co.jp/oka_yadokary/37640402.html#37640402 より引用 Orz～

　与えられた凸38角形の頂点のうち17個を頂点とする17角形のうち、

　もとの凸38角形と辺を共有しないものの個数は？

解答

上記サイト https://blogs.yahoo.co.jp/oka_yadokary/37654030.html より Orz～

[解答1]

　凸38角形の頂点に左回りに 0，1，2，3，……，37 と番号をつけ、

　17角形の頂点である凸38角形の頂点の番号を小さい順に、A₀，A₁，A₂，A₃，……，A₁₆ とします。

　また、a_k＝A_k+1－A_k－2≧0 (k＝0，1，2，……，15) とします。

　A₀＝0 のとき A₁₆≦36 なので、

　a₀＋a₁＋a₂＋a₃＋……＋a₁₅≦4 を満たす (a₀，a₁，a₂，a₃，……，a₁₅) の総数は、

　a₀＋a₁＋a₂＋a₃＋……＋a₁₅＋b＝4 を満たす (a₀，a₁，a₂，a₃，……，a₁₅，b) の総数と等しく、₁₇Ｈ₄ です。

　A₀＞0 のとき a＝A₀－1 とします。A₁₆≦37 なので、

　a＋a₀＋a₁＋a₂＋a₃＋……＋a₁₅≦4 を満たす (a，a₀，a₁，a₂，a₃，……，a₁₅) の総数は、

　a＋a₀＋a₁＋a₂＋a₃＋……＋a₁₅＋b＝4 を満たす (a，a₀，a₁，a₂，a₃，……，a₁₅，b) の総数と等しく、₁₈Ｈ₄ です。

　よって、求める17角形の個数は、₁₇Ｈ₄＋₁₈Ｈ₄＝4845＋5985＝10830 です。

[解答2]

　ある１点を固定し、A₀ とします。

　17角形A₀A₁A₂A₃……A₁₆ を決めるのに、

　A₀A₁，A₁A₂，A₂A₃，……，A₁₆A₀ の間の

　凸38角形の辺の本数を x₁，x₂，x₃，……，x₁₇ とすれば、

　x₁＋x₂＋x₃＋……＋x₁₇＝38 、

　(x₁－2)＋(x₂－2)＋(x₃－2)＋……＋(x₁₇－2)＝4 だから、

　(x₁，x₂，x₃，……，x₁₇) の総数は、₁₇Ｈ₄＝4845 です。

　固定する点の決め方が 38通り、同じ17角形を 17回ずつ数えることになるので、

　38･4845/17＝38･285＝10830 です。

[参考]

　n≧2m として、凸ｎ角形と頂点を共有し辺を共通しないｍ角形の個数は、

　n･_mＨ_n-2m/m＝n･_n-m-1Ｃ_n-2m/m

　＝n･(n－m－1)!/｛(m－1)!･(n－2m)!･m｝＝(n－m－1)!･n/｛m!･(n－2m)!｝です。

*もやもやが晴れましたぁ☆

[解答2]お気に入りぃ～♪

わたしゃ…以下のようないい加減なことを…^^;

*3*5 と間に最低１個ないといけないことに気づきました…
また、*4*4は回転したら2回重なる…
*3*3*3*3 は回転したら4回重なる…
so…
38=2*16+(6)・・・38通り 
=2*15+(3+5) or (4+4)・・・38*2H13+(38/2)*2H13
=2*14+(3+3+4)・・・38*3H11
=2*13+(3+3+3+3)・・・(38/4)*4H9
38*(1+14+7+13*6+3*11*5)
=38*265
=10070

わたしのでは...定点がどこなのかわからないからおかしいことになってしまうんだろうと思ってます…^^;