複数の点を一筆書きで結ぶ場合のパターンの数

昨今、スマートフォンが流行りだしてますが、ロック解除方法に「指リスト認証」なるものがあります。
３×３個の点を一筆書きでなぞってロックを解除する方法です。
そこでふと疑問に思ったのですが、この方法においてパターンは何種類あるのかと言うことです。

《条件》

(1) (2) (3)
(4) (5) (6)
(7) (8) (9)

上記の９つの点を４点以上９点以下で、かつ一筆書きで結ぶ。
一筆書きなので１つの点は複数回通過できず１回のみ。（ex.(1)→(2)→(3)→(2)→(1)などは不可）


ロト６のパターン数などを参考に色々と考えを展開してみたのですが
「一筆書き」と言う条件をどのように応用すれば良いのか難しく解けませんでした。

どなたか解く方法をご教授いただけましたら宜しくお願いいたします。

No.2 ベストアンサー 回答者： nag0720 回答日時： 2010/12/29 16:27

これは、地道に数えるしかないでしょうね。

(a)1-2から始まる場合
(b)2-1から始まる場合
(c)2-5から始まる場合
(d)5-2から始まる場合
に分けて数えます。
それ以外から始まる場合は、上記のどれかと同じパターンなので、合計は、
(a)*8+(b)*8+(c)*4+(d)*4
となります。

通過点が４点の場合、
(a)1-2-3-4,1-2-5-4,1-2-5-8,1-2-5-6　の４通り
(b)2-1-4-5,2-1-4-7　の２通り
(c)2-5-4-1,2-5-4-7,2-5-6-3,2-5-6-9,2-5-8-7,2-5-8-9　の６通り
(d)5-2-1-4,5-2-3-6　の２通り
計4*8+2*8+6*4+2*4=80

通過点が５点以上の場合も同様に求めると、

５点：7*8+3*8+4*4+2*4=104
６点：7*8+6*8+4*4+2*4=128
７点：8*8+4*8+2*4+2*4=112
８点：6*8+6*8+2*4+2*4=112
９点：4*8+0*8+0*4+2*4=40

合計576通り

この回答へのお礼

ご回答いただきありがとうございました。
0-9までの数字で4桁から8桁までの場合と比較したく質問させていただきました。
ある程度は上記と比較しパターンが少ないとは予測していましたがここまで少ないとは意外でした。

お礼日時：2011/01/02 16:16

No.1 回答者： nag0720 回答日時： 2010/12/29 15:53

＞一筆書きなので１つの点は複数回通過できず１回のみ。

「指リスト認証」がどういうものか分かりませんが、「一筆書き」とは、同じ道を２回通らないことです。

１つの点を複数回通過できないのは、「巡回路」といいます。

例えば、
(1)→(2)→(3)→(6)→(5)→(4)→(1)や、
(2)→(5)→(8)→(9)→(6)→(5)→(4)は、
「一筆書き」ならＯＫ、「巡回路」ならＮＧです。

どっちなんでしょう？

この回答への補足

ご指摘ありがとうございます。
私の学識が不足しておりました。
「巡回路」です。

補足日時：2010/12/29 16:03