19040：場合の数...格子路を同じ点を通らずに最短距離で往復するルート...

問題19040・・・https://sansu-seijin.jp/most/1578/ より引用 Orz～

解答

デジャヴー？

・わたしの...

地道に...^^;

四角い積み木をくっつけることを考える...

その周囲が求める閉路...

右下の3x3から、連続して除いていく...

0個取る...1

以下はこの2倍...

1個...1

2個...2

3個...3

4個...4

5個...4

6個...3

7個...2

8個...1

9個...1

so...((1+2+3+4)*2+1)*2+1=43

になるはずね ^^

↑

だめだこりゃ ^^; Orz...

↓

・鍵コメT様からのもの Orz～

スモークマンさんの考えだと，
・右下，左上の両方から取る場合が考察されていないように見えます．・・・でしたわ ^^;
・例えば「4個…4」はどういう4通りなのか，意味がとれません．

・・・あれ...以下のような3通りでした...^^;

問題18564に，一般式が書かれています．

(https://blogs.yahoo.co.jp/crazy_tombo/folder/931624.html?m=lc&sv=18564&sk=0 参照)

2*(m+n-3)!(m+n-4)!/((m-1)!(m-2)!(n-1)!(n-2)!)
にm=n=5を代入して，
2*7!*6!/(4!3!4!3!)=2*5040*720/(24*6*24*6)=350(通り)ですね．

改めて解いてみます．
Aの上の点をC，Aの右の点をD，Bの左の点をE，Bの下の点をFとしましょう．

反時計回りA→D→F→B→E→C→Aの経路数を求めて2倍すれば，
求める道順の数が得られます．
D→Fの経路数は，「右」「上」を3回ずつ行うから，6!/(3!3!)=20(通り)．
E→Cの経路数も同じく20通りであり，
その組合せは20*20=400(通り)考えられます．

このうち，D→FとE→Cが同じ点を通る場合は禁止されます．
同じ点を通る場合，通る同じ点のうち最もAに近い点をPとして，
「D→P→FとE←P←C」を「D→P→EとC→P→F」に対応させると，
このような経路の組合せは，D→EとC→Fの経路の組合せと対応し，
D→Eは，「右」2回と「上」4回を行うので，6!/(4!2!)=15(通り)，
C→Fも同数となって，この組合せは15*15=225(通り)です．

以上より，求める数は，
(400-225)*2=350(通り)
となります．

*難しいものね...^^;...