「場合の数」ってやつだとおもいます

質問

数学とくに場合の数が得意な方、下記問題の回答方法をおしえてください。
よろしくお願いします。

[問題]
１から９の九つの点を３×３で並べ、一筆書きで４個以上の点を通る書き方は何通りあるか？
スタートやゴールはどこからでもオッケーです。また１－２－３－４と４－３－２－１は違う書き方です
また４個以上の点なので１－２－３－４－５も当然オッケーです。

どなたか数学に強い方そしてわかりやすく説明していただける方、よろしくお願いします！！

回答No.3

nag0720 · ベストアンサー

＞点から点の進み方は縦横斜めいずれもオッケーです。

斜めは、どこまでの斜めなんでしょう？
９個の数字を
１２３
４５６
７８９
と並べたとき、
１－５はいいとしても、１－６の斜めは？

縦横だけだったら簡単ですが、斜めもＯＫとなると格段に難しくなります。

１－６の斜めはＮＧとした場合の数え方としては、
４個の場合は、９個中４個の数字の選び方の形をパターン化し、
パターンごとに、経路の数とそのパターンになる数とを掛けて合計すれば答えが出てきます。

４つを選ぶパターンは次の５通りあります。
パターンＡ：１２４５、２３５６など
パターンＢ：１２３５、１２５６など
パターンＣ：１２３６、１２５７など
パターンＤ：１２６８、１２６９など
パターンＥ：２４８６
それぞれのパターンの経路の数とそのパターンになる数を掛けると、
パターンＡ：２４×４＝９６
パターンＢ：１２×１６＝１９２
パターンＣ：４×４４＝１７６
パターンＤ：２×１２＝２４
パターンＥ：８×１＝８
合計４９６通り

５個の場合も同じようにパターンで考えれば計算できますが、
６個以上になると、別の工夫が必要になってくるでしょう。

１－６の斜めもＯＫの場合は、
１－３、１－７、１－９、２－４、３－７、３－９、４－６、７－９だけがＮＧなので、
９個の数字から４個以上選んで並べた順列の数から、隣どうしが上記の並びになっていないものだけ数えたほうが早いかもしれません。

いづれにしろこういう問題は、問題を出すのは簡単ですが、答えはそう簡単には出てきません。

ちなみに、パソコンを使って総当たりで調べると、
１－６がＮＧの場合の総数は、１００９６通り、
１－６がＯＫの場合の総数は、１３９８８０通りです。

お礼

1-6の斜めはＮＧの前提で質問しました。

それにしても１－６がＯＫの場合までご回答いただきありがとうございました。

説明も非常にわかりやすく勉強になりました。

ありがとうございました！！

回答No.2

hrsmmhr

角は一筆書きの途中では選択肢がありません。最初の時は二つ選択できます
辺は真ん中を通るまで選択肢が２つです
それ以降は選択肢がありません
中心は一筆書きで通った辺を除いた個数分だけ選択肢があります

最初が角なら
一筆書きはL-+-L-L-L, L-L-+-L-L, L-L-L-+-L, L-L-L-L-+です
9-8,8-8,7-12,6-14,5-14,4-8ｘ４
256通り
最初が辺なら
一筆書きは-+-L-L-L, -L-+-L-L, -L-L-+-L, -L-L-L-+ -L-L-L-Lです
8-14,7-12,6-12,5-12,4-10ｘ４
240通り
最初が真ん中なら
一筆書きは+-L-L-L-Lです
9-8,8-8,7-8,6-8,5-8,4-8
64通り
全部で560通り

回答No.1

nag0720

点から点への進み方は、縦横だけ？斜めはＯK？

一筆書きという場合は、点から点への経路を１回だけ通る場合です。
なので、１－２－３－４－１　という場合も一筆書きといいます。
それでいいんでしょうか？
それとも、同じ点は１回しか通れないという条件なのでしょうか？
（このような経路はハミルトン路といいます）

補足

前提条件が不足してましてすいません。

点から点の進み方は縦横斜めいずれもオッケーです。

また１－２－３－４－１といった同じ点を二度通ることは認められません。

よろしくお願いします。