数字並べ（２）　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　下図の両端を除いた１２個のマス目には、１から１２までの数字が１つずつ入る。数字の
８ は既に入っていて、両端は数字の０である。

　隣り合う数字同士の差が、いつも ２ または ３ であるようにするには、どのように配置し
たらよいだろうか？
































（答）　以下のように配置すればよい。

（コメント）　解はこれだけ！という自信は全くありません。他にもあるかも？

　　　　　　（追記）　当ＨＰがいつもお世話になっているらすかるさんに検証していただきまし
　　　　　　　　　　　た。解は、上記のみとのことです。らすかるさんに感謝いたします。


　この問題について、当ＨＰがいつもお世話になっているＨＮ「ＦＮ」さんが問題の拡張を考え
られた。（平成２２年７月３１日付け）

　「８」が既に入っているが、入っていなくても答は左右対称を除けば１つしかない。

　そこで、１ から１２となっているのを、ｎ を自然数として、１ から ｎ に変えてみよう。

すなわち、

　　整数の列 ０，Ａ₁，Ａ₂，・・・，Ａ_n，０ において、隣り合う数同士の差は、２または３

　である。また、Ａ₁，Ａ₂，・・・，Ａ_n は、１から ｎ までの自然数ですべて異なる。即ち、

　１，２，・・・，ｎ を並び変えたものになる。

　　ｎ がどんな値のとき、このような Ａ₁，Ａ₂，・・・，Ａ_n は存在するか。また、何通り

　存在するか。ただし、左右対称なものは同じとみなすことにする。

　（１）　ｎ が８以下なら、ｎ＝４ のときを除いてこのような整数の列はない。

　（２）　ｎ が９以上１３以下であれば、このような整数の列がただ１通りある。

　（３）　ｎ が１４以上であれば、このような整数の列が２通り以上ある。

　（４）　ｎ に関する漸化式または漸化式のようなものを作ってください。即ち、すべての ｎ に
　　　ついて場合の数が求められる手順を作ってください。

　この問いかけに対して、らすかるさんが、プログラムで、ｎ＝４０まで調べて、数列サイトで
一致するものを検索したら、次のサイトが出てきたとのこと。（平成２２年７月３１日付け）

　　　　　http://www.research.att.com/~njas/sequences/A003520

　中に書いてあることはこの問題とは違うことのようだが、多分ここに書いてあるように、

　　ａ_n＝ａ_n-1＋ａ_n-5 　になるんですよね？と、らすかるさん。


　これを受けて、ＦＮさん．．．（平成２２年７月３１日付け）

　私が出した式は、　ａ_n＝ａ_n-2＋ａ_n-5＋ａ_n-6　です。ａ_n＝ａ_n-1＋ａ_n-5 からこの式は出ます。

　実際に、　ａ_n＝ａ_n-1＋ａ_n-5 に　ａ_n-1＝ａ_n-2＋ａ_n-6 を代入して、ａ_n＝ａ_n-2＋ａ_n-5＋ａ_n-6

逆はすぐには出ませんが最初の何項かが一致すれば同じ数列を定めるのは確かです。だ

から出るのでしょう。ａ_n＝ａ_n-1＋ａ_n-5 のほうが式としていいのは間違いないですから、これ

を問題にしたいと思います。

（４）’　ａ_n＝ａ_n-1＋ａ_n-5 が成り立つことを示せ。ただし、ｎ≧６　とする。

　また、ＦＮさんからのコメントです。（平成２２年８月１日付け）

　隣り合う数同士の差は２または３だから、０の隣であるＡ₁は２か３である。同様にＡ_ｎも２か
３　である。左右対称なものを同じとみなすから、Ａ₁＝２、Ａ_ｎ＝３としていいので次のように
なる。

　１から ｎ までの自然数を並び変えた数列 Ａ₁，Ａ₂，・・・，Ａ_n で次の条件をみたすも

のの個数を ａ_n とするとき、ａ_n＝ａ_n-1＋ａ_n-5 が成り立つことを示せ。

　（１）　隣り合う２項の差は、２か３である　（２）　Ａ₁＝２　、Ａ_n＝３

　ここで、両端が２と３であるのはやや不自然なので、両端を１と２にします。実は、同じ漸化
式が成り立ちます。即ち

　１から ｎ までの自然数を並び変えた数列 Ａ₁，Ａ₂，・・・，Ａ_n で次の条件をみたすも

のの個数を ｂ_n とするとき、ｂ_n＝ｂ_n-1＋ｂ_n-5 が成り立つことを示せ。

　（１）　隣り合う２項の差は、２か３である　（２）　Ａ₁＝１　、Ａ_n＝２

これの方が考えやすいと思います。あとは、ａ_n と ｂ_n の関係がどうなっているかです。


　平成２２年８月１日付けで、ＨＮ「攻略法」さんが、解を一気に書き上げられた。

ｎ ＝１〜３　については、　解はない。

ｎ ＝４　のとき、　　0 2 4 1 3 0

ｎ ＝５〜８　については、　解はない。

ｎ ＝９　のとき、　　0 2 5 8 6 9 7 4 1 3 0

ｎ ＝１０　のとき、　　　0 2 5 8 10 7 9 6 4 1 3 0

ｎ ＝１１　のとき、　　　0 2 5 7 10 8 11 9 6 4 1 3 0

ｎ ＝１２　のとき、　　　0 2 5 7 10 12 9 11 8 6 4 1 3 0

ｎ ＝１３　のとき、　　　0 2 5 7 9 12 10 13 11 8 6 4 1 3 0

ｎ ＝１４　のとき、　　　0 2 5 7 9 12 14 11 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 12 14 11 13 10 7 4 1 3 0

ｎ ＝１５　のとき、　　　0 2 5 7 9 11 14 12 15 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 14 12 15 13 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 14 12 15 13 10 7 9 6 4 1 3 0

ｎ ＝１６　のとき、　　　0 2 5 7 9 11 14 16 13 15 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 14 16 13 15 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 14 16 13 15 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 14 16 13 15 12 10 7 9 6 4 1 3 0

ｎ ＝１７　のとき、　　　0 2 5 7 9 11 13 16 14 17 15 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 13 16 14 17 15 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 13 16 14 17 15 12 9 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 13 16 14 17 15 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 13 16 14 17 15 12 10 7 9 6 4 1 3 0

ｎ ＝１８　のとき、　　　0 2 5 7 9 11 13 16 18 15 17 14 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 10 13 16 18 15 17 14 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 13 16 18 15 17 14 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 13 16 18 15 17 14 12 9 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 13 16 18 15 17 14 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 13 16 18 15 17 14 12 10 7 9 6 4 1 3 0

ｎ ＝１９　のとき、　　　0 2 5 7 9 11 13 15 18 16 19 17 14 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 10 13 15 18 16 19 17 14 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 15 18 16 19 17 14 11 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 13 15 18 16 19 17 14 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 13 15 18 16 19 17 14 12 9 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 13 15 18 16 19 17 14 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 12 15 18 16 19 17 14 11 13 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 13 15 18 16 19 17 14 12 10 7 9 6 4 1 3 0

ｎ ＝２０　のとき、　　　0 2 5 7 9 11 13 15 18 20 17 19 16 14 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 11 14 12 15 18 20 17 19 16 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 10 13 15 18 20 17 19 16 14 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 15 18 20 17 19 16 14 11 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 13 15 18 20 17 19 16 14 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 13 15 18 20 17 19 16 14 12 9 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 13 15 18 20 17 19 16 14 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 14 12 15 18 20 17 19 16 13 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 12 15 18 20 17 19 16 14 11 13 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 13 15 18 20 17 19 16 14 12 10 7 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 14 12 15 18 20 17 19 16 13 10 7 9 6 4 1 3 0

ｎ ＝２１　のとき、　　　0 2 5 7 9 11 13 15 17 20 18 21 19 16 14 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 11 14 12 15 17 20 18 21 19 16 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 11 14 17 20 18 21 19 16 13 15 12 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 10 13 15 17 20 18 21 19 16 14 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 9 12 15 17 20 18 21 19 16 14 11 13 10 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 13 15 17 20 18 21 19 16 14 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 8 11 14 17 20 18 21 19 16 13 15 12 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 7 10 13 15 17 20 18 21 19 16 14 12 9 11 8 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 13 15 17 20 18 21 19 16 14 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 14 12 15 17 20 18 21 19 16 13 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 11 14 17 20 18 21 19 16 13 15 12 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 6 9 12 15 17 20 18 21 19 16 14 11 13 10 7 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 13 15 17 20 18 21 19 16 14 12 10 7 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 14 12 15 17 20 18 21 19 16 13 10 7 9 6 4 1 3 0
　　　　　　　　　　　　　 0 2 5 8 11 14 17 20 18 21 19 16 13 15 12 10 7 9 6 4 1 3 0

（コメント）　ＦＮさんが示された場合の数の表

が、実際に具体的に求められました_ネ！攻略法さんに感謝します。

　次は、攻略法さんによる「並びの生成」である。

　ｎ の並びは、ｎ−５ の並びと ｎ−１ の並びから順々に生成される

具体的に、ｎ ＝１、２、３、４、５ の場合、

　ｎ ＝４　で、{ 0 2 4 1 3 0 }　が解、それ以外は、「解なし」となる。

ｎ ≧６　の場合、まず、ｎ＝４　の先頭の「0」を除いた並び{ 2 4 1 3 0 }を基準列とする。

ｎ−５　が奇数ならば、

　■ ｎ−５　の並びから、基準値 ｎ−４ 以上の数字を除き、数字「 ｎ-5 」の後に５個の隙間
　　を空ける。基準値 ｎ−４ に基準列の正順を加算して、ｎ−４ から ｎ までの数字を埋める。

　（例） ｎ＝１４　の場合、ｎ−５＝９　は奇数で、基準値は「10」

　　ｎ ＝９　のときの並びが、　0 2 5 8 6 9 7 4 1 3 0　で、基準値「10」より大きい数はない。

　　そこで、数字「9」の後に５個の隙間を空ける。　0 2 5 8 6 9 ＿ ＿ ＿ ＿ ＿ 7 4 1 3 0

　　基準値「10」に基準列の正順を加算して、　12 14 11 13 10　の並びを作り、空所を穴埋
　めする。

　　　　　∴　 0 2 5 8 6 9 12 14 11 13 10 7 4 1 3 0

　■ ｎ−１ の並びから、基準値 ｎ−４ 以上の数字を除き、数字「 ｎ-5 」の後に５個の隙間
　　を空ける。（実際は、削除する数列は中央に４つ存在する。）
　　基準値 ｎ−４ に基準列の正順を加算して、ｎ−４ から ｎ までの数字を埋める。

　（例） ｎ＝１０　の場合、ｎ−５＝５　は奇数で、基準値は「6」

　　ｎ ＝９　のときの並びが、　0 2 5 8 6 9 7 4 1 3 0　で、基準値「6」以上の数字を除き、数

　　字「5」の後に５個の隙間を空ける。

　　　　　0 2 5 ＿ ＿ ＿ ＿ ＿ 4 1 3 0

　　基準値「6」に基準列の正順を加算して、　8 10 7 9 6　の並びを作り、空所を穴埋めする。

　　　　　∴　 0 2 5 8 10 7 9 6 4 1 3 0

ｎ−５　が偶数ならば、

　■ ｎ−５　の並びから、基準値 ｎ−４ 以上の数字を除き、数字「 ｎ-5 」の前に５個の隙間
　　を空ける。基準値 ｎ−４ に基準列の逆順を加算して、ｎ−４ から ｎ までの数字を埋める。

　（例） ｎ＝１５　の場合、ｎ−５＝１０　は偶数で、基準値は「11」

　　ｎ ＝１０　のときの並びが、　0 2 5 8 10 7 9 6 4 1 3 0　で、数字「10」の前に５個の隙間

　　を空ける。　　　0 2 5 8 ＿ ＿ ＿ ＿ ＿ 10 7 9 6 4 1 3 0

　　基準値「11」に基準列の逆順を加算して、　11 14 12 15 13　の並びを作り、空所を穴埋

　めする。

　　　　　∴　 0 2 5 8 11 14 12 15 13 10 7 9 6 4 1 3 0

　■ ｎ−１ の並びから、基準値 ｎ−４ 以上の数字を除き、数字「 ｎ-5 」の前に５個の隙間
　　を空ける。基準値 ｎ−４ に基準列の逆順を加算して、ｎ−４ から ｎ までの数字を埋め
　　る。

　（例） ｎ＝１５　の場合、ｎ−５＝１０　は偶数で、基準値は「11」

　　ｎ ＝１４　のときの並びが、　0 2 5 7 9 12 14 11 13 10 8 6 4 1 3 0　・・・（１）

　　　　　　　　　　　　　　　　　　　　0 2 5 8 6 9 12 14 11 13 10 7 4 1 3 0　・・・（２）

　で、基準値「11」以上の数字を除き、数字「10」の前に５個の隙間を空ける。

　　（１）は、　　　0 2 5 7 9 ＿ ＿ ＿ ＿ ＿ 10 8 6 4 1 3 0

　　（２）は、　　　0 2 5 8 6 9 ＿ ＿ ＿ ＿ ＿ 10 7 4 1 3 0

　　基準値「11」に基準列の逆順を加算して、　11 14 12 15 13　の並びを作り、空所を穴埋

　めする。

　　このとき、　（１）は、　　　0 2 5 7 9 11 14 12 15 13 10 8 6 4 1 3 0

　　　　　　　　　（２）は、　　　0 2 5 8 6 9 11 14 12 15 13 10 7 4 1 3 0

　となる。

　ところで、ｎ＝９　の場合は、ｎ−５＝４　（偶数）なので、ｎ−５＝４　の並び　0 2 4 1 3 0

において、基準値「5」以上の数字を除き、「4」の前に５つ隙間を空ける。

　　　　　0 2 ＿ ＿ ＿ ＿ ＿ 4 1 3 0

　そこで、基準値「5」に基準列の逆順を加算して、　5　8　6　9　7　の並びを作り、空所を穴
埋めする。

　　　　　∴　 0 2 5 8 6 9 7 4 1 3 0

　また、ｎ−１＝８　の並びはないので、解なし。

したがって、ｎ＝９　の並びは、　0 2 5 8 6 9 7 4 1 3 0　の１個となる。

　同様に、ｎ＝１０　の場合は、

　ｎ−５＝５　の並びはないので、解なし。

　ｎ−１＝９　の並び 　0 2 5 8 6 9 7 4 1 3 0　 から基準値「6」以上の数字を除き、「5」の後

に５つ隙間を空ける。　　　0 2 5 ＿ ＿ ＿ ＿ ＿ 4 1 3 0

　ｎ−５＝５　は奇数なので、基準値「6」に基準列の正順を加算して　8 10 7 9 6　の並びを

作り、空所を穴埋めする。

　　　　　∴　 0 2 5 8 10 7 9 6 4 1 3 0

したがって、ｎ＝１０　の並びは、　0 2 5 8 10 7 9 6 4 1 3 0　の１個となる。

　次に、ｎ＝２１　の場合の並びを求めてみよう。

　ｎ−５＝１６　（偶数）の並びは、

　　（１）　　0 2 5 7 9 11 14 16 13 15 12 10 8 6 4 1 3 0

　　（２）　　0 2 5 7 10 8 11 14 16 13 15 12 9 6 4 1 3 0

　　（３）　　0 2 5 8 6 9 11 14 16 13 15 12 10 7 4 1 3 0

　　（４）　　0 2 5 8 11 14 16 13 15 12 10 7 9 6 4 1 3 0

　から、基準値「17」以上の数字列を除き、「16」の前に５つ隙間を空ける。

(1)は、　　0 2 5 7 9 11 14 ＿ ＿ ＿ ＿ ＿ 16 13 15 12 10 8 6 4 1 3 0

　　基準値「17」に基準列の逆順を加算して　17 20 18 21 19　の並びを作り、空所を穴埋め

　する。　　0 2 5 7 9 11 14 17 20 18 21 19 16 13 15 12 10 8 6 4 1 3 0

　同様にして、（２）は、　0 2 5 7 10 8 11 14 17 20 18 21 19 16 13 15 12 9 6 4 1 3 0

　　　　　　　　　（３）は、　0 2 5 8 6 9 11 14 17 20 18 21 19 16 13 15 12 10 7 4 1 3 0

　　　　　　　　　（４）は、　0 2 5 8 11 14 17 20 18 21 19 16 13 15 12 10 7 9 6 4 1 3 0

　ｎ−１＝２０　の並びから、

　　（５）　　0 2 5 7 9 11 13 15 18 20 17 19 16 14 12 10 8 6 4 1 3 0

　　（６）　　0 2 5 7 9 11 14 12 15 18 20 17 19 16 13 10 8 6 4 1 3 0

　　（７）　　0 2 5 7 9 12 10 13 15 18 20 17 19 16 14 11 8 6 4 1 3 0

　　（８）　　0 2 5 7 9 12 15 18 20 17 19 16 14 11 13 10 8 6 4 1 3 0

　　（９）　　0 2 5 7 10 8 11 13 15 18 20 17 19 16 14 12 9 6 4 1 3 0

　（１０）　　0 2 5 7 10 13 15 18 20 17 19 16 14 12 9 11 8 6 4 1 3 0

　（１１）　　0 2 5 8 6 9 11 13 15 18 20 17 19 16 14 12 10 7 4 1 3 0

　（１２）　　0 2 5 8 6 9 11 14 12 15 18 20 17 19 16 13 10 7 4 1 3 0

　（１３）　　0 2 5 8 6 9 12 15 18 20 17 19 16 14 11 13 10 7 4 1 3 0

　（１４）　　0 2 5 8 11 13 15 18 20 17 19 16 14 12 10 7 9 6 4 1 3 0

　（１５）　　0 2 5 8 11 14 12 15 18 20 17 19 16 13 10 7 9 6 4 1 3 0

　から、基準値「17」以上の数字列を除き、「16」の前に５つ隙間を空ける。

（５）は、　　0 2 5 7 9 11 13 15 ＿ ＿ ＿ ＿ ＿ 16 14 12 10 8 6 4 1 3 0

　　基準値「17」に基準列の逆順を加算して　17 20 18 21 19　の並びを作り、空所を穴埋め

　する。

　　　　　∴　 0 2 5 7 9 11 13 15 17 20 18 21 19 16 14 12 10 8 6 4 1 3 0

　同様にして、（６）は、　0 2 5 7 9 11 14 12 15 17 20 18 21 19 16 13 10 8 6 4 1 3 0

　　　　　　　　　（７）は、　0 2 5 7 9 12 10 13 15 17 20 18 21 19 16 14 11 8 6 4 1 3 0

　　　　　　　　　（８）は、　0 2 5 7 9 12 15 17 20 18 21 19 16 14 11 13 10 8 6 4 1 3 0

　　　　　　　　　（９）は、　0 2 5 7 10 8 11 13 15 17 20 18 21 19 16 14 12 9 6 4 1 3 0

　　　　　　　　（１０）は、　0 2 5 7 10 13 15 17 20 18 21 19 16 14 12 9 11 8 6 4 1 3 0

　　　　　　　　（１１）は、　0 2 5 8 6 9 11 13 15 17 20 18 21 19 16 14 12 10 7 4 1 3 0

　　　　　　　　（１２）は、　0 2 5 8 6 9 11 14 12 15 17 20 18 21 19 16 13 10 7 4 1 3 0

　　　　　　　　（１３）は、　0 2 5 8 6 9 12 15 17 20 18 21 19 16 14 11 13 10 7 4 1 3 0

　　　　　　　　（１４）は、　0 2 5 8 11 13 15 17 20 18 21 19 16 14 12 10 7 9 6 4 1 3 0

　　　　　　　　（１５）は、　0 2 5 8 11 14 12 15 17 20 18 21 19 16 13 10 7 9 6 4 1 3 0

　したがって、ｎ＝２１　の場合の並びは、１５個となる。

（コメント）　攻略法さん、ありがとうございます。「並びの生成」を少し整理しました。基準列
　　　　　　から帰納的に順次求められるという発想に感動しました。


　ＦＮさんからのコメントです。（平成２２年８月１４日付け）

　１から ｎ までの自然数を並び変えた数列 A₁，A₂，A₃，････，A_n で条件

(1)　隣り合う２項の差は、２か３である
(2)　A₁＝２、A_n＝３

を満たすものの個数 ａ_n は次の漸化式で決定される。

　　　ａ_n＝ａ_n-1＋ａ_n-5　（n≧６）　、ａ_n＝０　(n＝１、２、３、５）　、ａ₄＝１

上記で、(2)を、A₁＝１、A_n＝２ に変えたもの個数を ｂ_n とすると、ｂ_n は次の漸化式で決まる。

　　　ｂ_n＝ｂ_n-1＋ｂ_n-5　（n≧７）　、ｂ_n＝０　(n＝１、２、３、４、５）　、ｂ₆＝１

また、(2)を、A₁＝１、A_n＝３ に変えたものの個数を ｃ_n とすると、ｃ_n は次の漸化式で決まる。

　　　ｃ_n＝ｃ_n-1＋ｃ_n-5　（n≧６）　、ｃ_n＝０　(n＝１、２、３、４）　、ｃ₅＝１

ａ_n 、ｂ_n 、ｃ_n が同じ漸化式を満たす所が面白いが次の関係が成り立つ。

　　　ａ_n ＝ｂ_n-3＝ｃ_n+1

　従って、この３つは多少ずれて同じものになる。

ｃ_n＝ｂ_n-4 は、１、･･･、３　が　１、４、２、５、・・・、６、３　しかないことから確認できる。

ここで条件(2)を取り去ったものを考えよう。即ち

　１から ｎ までの自然数を並び変えた数列 A₁，A₂，A₃，････，A_n で隣り合う２項の
差が、２か３であるものの個数を求めよ。

　境界条件がなくなれば自由度がかなり高くなり場合の数は多そうである。相当難しいと思
われる。この形で見れば「隣り合う２項の差が２か３」はやや不自然に見える。「隣り合う２項
の差が１か２」のほうが自然である。そしてこのほうが易しそうです。

　１から ｎ までの自然数を並び変えた数列 A₁，A₂，A₃，････，A_n で隣り合う２項の
差が、１か２であるものの個数を求めよ。

　これを考えたいのですが、これでもやはり難しそうです。境界条件をつけると、ほとんど解
がなくなます。初期条件をつけましょう。

　１から ｎ までの自然数を並び変えた数列 A₁，A₂，A₃，････，A_n で隣り合う２項の
差が、１か２であるもので、A₁＝１ であるものの個数 ｆ_ｎ を求めよ。

上の ａ_n のような形で答えてください。即ち漸化式と ｎ が小さいときの値。

　この問いかけに対して、攻略法さんが考察された。（平成２２年８月１７日付け）

　ｆ_ｎ＝ｆ_ｎ-1＋ｆ_ｎ-3＋１　（ｎ≧４）　、ｆ₁＝１　、ｆ₂＝１　、ｆ₃＝２　が予想される。

　並びについて、

ｎ＝１　のとき、　1　のみ　　　ｎ＝２　のとき、　1 2　のみ

ｎ＝３　のとき、　1： 1 2 3　と　2： 1 3 2　の２通り

ｎ＝４　のとき、　1： 1 2 3 4　、2： 1 2 4 3　、3： 1 3 2 4　、4： 1 3 4 2　の４通り

ｎ＝５　のとき、　1： 1 2 3 4 5　、2： 1 2 3 5 4　、3： 1 2 4 3 5　、
　　　　　　　　　　4： 1 2 4 5 3　、5： 1 3 2 4 5　、6： 1 3 5 4 2　の６通り

ｎ＝６　のとき、　1： 1 2 3 4 5 6　、2： 1 2 3 4 6 5　、3： 1 2 3 5 4 6　、4： 1 2 3 5 6 4
　　　　　　　　　　5： 1 2 4 3 5 6　、6： 1 2 4 6 5 3　、7： 1 3 2 4 5 6　、8： 1 3 2 4 6 5
　　　　　　　　　　9： 1 3 5 6 4 2　の９通り

ｎ＝７　のとき、　1： 1 2 3 4 5 6 7　、 2： 1 2 3 4 5 7 6　、 3： 1 2 3 4 6 5 7　 、 4： 1 2 3 4 6 7 5
　　　　　　　　　　5： 1 2 3 5 4 6 7　、 6： 1 2 3 5 7 6 4　、 7： 1 2 4 3 5 6 7　 、 8： 1 2 4 3 5 7 6
　　　　　　　　　　9： 1 2 4 6 7 5 3　、10： 1 3 2 4 5 6 7　、11： 1 3 2 4 5 7 6　、12： 1 3 2 4 6 5 7
　　　　　　　　　13： 1 3 2 4 6 7 5　、14： 1 3 5 7 6 4 2　の１４通り

ｎ＝８　のとき、　　1： 1 2 3 4 5 6 7 8　、 2： 1 2 3 4 5 6 8 7　、 3： 1 2 3 4 5 7 6 8
　　　　　　　　　　　4： 1 2 3 4 5 7 8 6　、 5： 1 2 3 4 6 5 7 8　、 6： 1 2 3 4 6 8 7 5
　　　　　　　　　　　7： 1 2 3 5 4 6 7 8　、 8： 1 2 3 5 4 6 8 7　、 9： 1 2 3 5 7 8 6 4
　　　　　　　　　　10： 1 2 4 3 5 6 7 8　、11： 1 2 4 3 5 6 8 7　、12： 1 2 4 3 5 7 6 8
　　　　　　　　　　13： 1 2 4 3 5 7 8 6　、14： 1 2 4 6 8 7 5 3　、15： 1 3 2 4 5 6 7 8
　　　　　　　　　　16： 1 3 2 4 5 6 8 7　、17： 1 3 2 4 5 7 6 8　、18： 1 3 2 4 5 7 8 6
　　　　　　　　　　19： 1 3 2 4 6 5 7 8　、20： 1 3 2 4 6 8 7 5　、21： 1 3 5 7 8 6 4 2　の２１通り

ｎ＝９　のとき、　　1： 1 2 3 4 5 6 7 8 9　、 2： 1 2 3 4 5 6 7 9 8　 、 3： 1 2 3 4 5 6 8 7 9
　　　　　　　　　　　4： 1 2 3 4 5 6 8 9 7　、 5： 1 2 3 4 5 7 6 8 9　、 6： 1 2 3 4 5 7 9 8 6
　　　　　　　　　　　7： 1 2 3 4 6 5 7 8 9　、 8： 1 2 3 4 6 5 7 9 8　、 9： 1 2 3 4 6 8 9 7 5
　　　　　　　　　　10： 1 2 3 5 4 6 7 8 9　、11： 1 2 3 5 4 6 7 9 8　、12： 1 2 3 5 4 6 8 7 9
　　　　　　　　　　13： 1 2 3 5 4 6 8 9 7　、14： 1 2 3 5 7 9 8 6 4　、15： 1 2 4 3 5 6 7 8 9
　　　　　　　　　　16： 1 2 4 3 5 6 7 9 8　、17： 1 2 4 3 5 6 8 7 9　、18： 1 2 4 3 5 6 8 9 7
　　　　　　　　　　19： 1 2 4 3 5 7 6 8 9　、20： 1 2 4 3 5 7 9 8 6　、21： 1 2 4 6 8 9 7 5 3
　　　　　　　　　　22： 1 3 2 4 5 6 7 8 9　、23： 1 3 2 4 5 6 7 9 8　、24： 1 3 2 4 5 6 8 7 9
　　　　　　　　　　25： 1 3 2 4 5 6 8 9 7　、26： 1 3 2 4 5 7 6 8 9　、27： 1 3 2 4 5 7 9 8 6
　　　　　　　　　　28： 1 3 2 4 6 5 7 8 9　、29： 1 3 2 4 6 5 7 9 8　、30： 1 3 2 4 6 8 9 7 5
　　　　　　　　　　31： 1 3 5 7 9 8 6 4 2　の３１通り

ｎ＝１０　のとき、　1： 1 2 3 4 5 6 7 8 9 10　、 2： 1 2 3 4 5 6 7 8 10 9　、　3： 1 2 3 4 5 6 7 9 8 10
　　　　　　　　　　　4： 1 2 3 4 5 6 7 9 10 8　、 5： 1 2 3 4 5 6 8 7 9 10　、　6： 1 2 3 4 5 6 8 10 9 7
　　　　　　　　　　　7： 1 2 3 4 5 7 6 8 9 10　、 8： 1 2 3 4 5 7 6 8 10 9　、　9： 1 2 3 4 5 7 9 10 8 6
　　　　　　　　　　10： 1 2 3 4 6 5 7 8 9 10　、11： 1 2 3 4 6 5 7 8 10 9　、12： 1 2 3 4 6 5 7 9 8 10
　　　　　　　　　　13： 1 2 3 4 6 5 7 9 10 8　、14： 1 2 3 4 6 8 10 9 7 5　、15： 1 2 3 5 4 6 7 8 9 10
　　　　　　　　　　16： 1 2 3 5 4 6 7 8 10 9　、17： 1 2 3 5 4 6 7 9 8 10　、18： 1 2 3 5 4 6 7 9 10 8
　　　　　　　　　　19： 1 2 3 5 4 6 8 7 9 10　、20： 1 2 3 5 4 6 8 10 9 7　、21： 1 2 3 5 7 9 10 8 6 4
　　　　　　　　　　22： 1 2 4 3 5 6 7 8 9 10　、23： 1 2 4 3 5 6 7 8 10 9　、24： 1 2 4 3 5 6 7 9 8 10
　　　　　　　　　　25： 1 2 4 3 5 6 7 9 10 8　、26： 1 2 4 3 5 6 8 7 9 10　、27： 1 2 4 3 5 6 8 10 9 7
　　　　　　　　　　28： 1 2 4 3 5 7 6 8 9 10　、29： 1 2 4 3 5 7 6 8 10 9　、30： 1 2 4 3 5 7 9 10 8 6
　　　　　　　　　　31： 1 2 4 6 8 10 9 7 5 3　、32： 1 3 2 4 5 6 7 8 9 10　、33： 1 3 2 4 5 6 7 8 10 9
　　　　　　　　　　34： 1 3 2 4 5 6 7 9 8 10　、35： 1 3 2 4 5 6 7 9 10 8　、36： 1 3 2 4 5 6 8 7 9 10
　　　　　　　　　　37： 1 3 2 4 5 6 8 10 9 7　、38： 1 3 2 4 5 7 6 8 9 10　、39： 1 3 2 4 5 7 6 8 10 9
　　　　　　　　　　40： 1 3 2 4 5 7 9 10 8 6　、41： 1 3 2 4 6 5 7 8 9 10　、42： 1 3 2 4 6 5 7 8 10 9
　　　　　　　　　　43： 1 3 2 4 6 5 7 9 8 10　、44： 1 3 2 4 6 5 7 9 10 8　、45： 1 3 2 4 6 8 10 9 7 5
　　　　　　　　　　46： 1 3 5 7 9 10 8 6 4 2　の４６通り

並びの生成・・・次の条件を満たせば、ｎ−１　の並びに、ｎ を追加できる。

　したがって、N=1の並び{1}から順々に生成することが可能である。

・終端が {1 … n-1} または {1 … n-2} のとき、新たな終端として追加できる。

　　　∴　{1 … n-1 n} または {1 … n-2 n}

・途中が {1 … n-2 n-1 …} または {1 … n-1 n-2 …} のとき、その間に追加できる。

　　　∴　{1 … n-2 n n-1 …} または {1 … n-1 n n-2 …}


　ＦＮさんの心配「境界条件をつけるとほとんど解がなくなます。」については、{1 … 2}　より、
上記並びの各最後の部分のみが該当する。

　　∴　　{ {奇数の昇順列} {偶数の降順列} }

（コメント）　攻略法さんに感謝します。


　攻略法さんの示された漸化式

　ｆ_ｎ＝ｆ_ｎ-1＋ｆ_ｎ-3＋１　（ｎ≧４）　、ｆ₁＝１　、ｆ₂＝１　、ｆ₃＝２

について、ＦＮさんが証明された。（平成２２年８月１７日付け）

（証明）　ｎ≧４　とする。

　１の隣りは、２か３だから、　１２・・・　または　１３・・・　である。

　　（イ）　１２･･･　は、２、３、・・・、ｎ　を　２･･･　と並べることになるから、それぞれから １ を

　　　　　引けば、

　　　　　１、２、･･･、ｎ−１　を、１･･･　と並べることだから、　ｆ_ｎ-1 通り。

　　（ロ）　１３･･･　は、次のどれかである。

　　　　(ａ)　１３２･･･
　　　　(ｂ)　１３４･･･
　　　　(ｃ)　１３５･･･　　もちろん、(ｃ)は、ｎ≧５　のとき。

　　(a)は、１３２４･･･しかない。これは、１２･･･の場合と同様に考えて、ｆ_ｎ-3 通り。

　　(ｂ)は、n≧５ のときはありえない。２の隣は、１、３、４のどれかであるが、いずれも使わ
　れており、４の隣に置くしかないがその隣に置くものがない。ｎ＝４ のときは、１３４２　の
　１通り。

　　(ｃ)　２の隣は、１、３、４のどれかであるが、１、３は使われているから、４しかなく、従っ
　て、２は右端しかない。１３５･･･２となる。２の隣は４で、１３５･･･４２。４の隣は６しかなく、
　１３５･･･６４２。５の隣は７しかないので、１３５７･･･６４２。以下同様で、すべて確定し、１
　通り。ただし、ｎ＝４のときはなし。

　以上より、漸化式 ｆ_ｎ＝ｆ_ｎ-1＋ｆ_ｎ-3＋１　（ｎ≧４）により、ｆ_ｎ は確定する。　（証終）

（コメント）　なるほど、合点がいきました。ＦＮさんに感謝します。

　また、ＦＮさんからの情報によれば、ｆ_ｎ は、オンライン整数列大辞典にあるそうである。
（→　参考：「A038718」）

　次に、初期条件A₁＝1を取り去った場合を考える。

　１から ｎ までの自然数を並び変えた数列 A₁，A₂，A₃，････，A_n で隣り合う２項の
差が、１か２であるものの個数

を、g_ｎ とおいて、g_ｎ を ｆ_ｎ で表してください。ただし、左右を逆向きにしたものは同じとみな
す。

　上記の問題は、下のようなグラフにおけるハミルトン路(すべての点を通る経路）の数を
求める問題になります。（平成２２年８月１７日付け）

図は、ｎ＝１０　のときのもの。

　１ー３ー５ー７ー９
　 ＼／＼／＼／＼／＼
　　２ー４ー６ー８ー10

　f(n) は１からスタートするものの個数で、g(n) は全体の個数である。この形に表現したから
求めやすくなるとは思えませんが．．．。でも多少考えやすいかもしれません。例えば前の投
稿で(ｂ)として扱ったケース　134･･･　が解を持たないこととかは明らかです。

パズルならこの形で、ｎ＝10 前後で出すのが適当かもしれません。ハミルトン閉路（ハミルト
ン路で閉じたもの）が1つしかないことは明らかでしょう。もともとの問題（隣り合う２項の差が
２か３で両端に０がありｎ＝12）はハミルトン閉路の問題になりますが、平面グラフとしては書
けそうにありません。

　攻略法さんからのコメントです。（平成２２年８月１９日付け）

並びの生成　　ｎ=１０　の場合の並び (1 … )　　４６通り

　以下の説明で使用するので、各 ｎ の並び(1 … )の場合の数を示しておく。（算出済み）

　2、3、4、… から始まる並びは、左側から順々に、辺を切り離していくことで調べられる。

●並び (2 … )
　
　並び(2 3 … )は、平面が２つに分断されるので、存在しない。

　並び(2 4 … 3 1)は、並び(1 3 … 4 2)と対称である。

　したがって、平面グラフ
　　　　　　　　　　２─１─３─５─７─９
　　　　　　　　　　　　　　│／│／│／│
　　　　　　　　　　　　　　４─６─８─10
を考えればよい。

　右側部分に着目すると、ｎ＝８　の平面グラフである。

　　３─５─７─９　　　１─３─５─７
　　│／│／│／│　→　│／│／│／│
　　４─６─８─10　　　２─４─６─８

　よって、ｎ＝８　の場合の並び(1 … )の数だけ、並びが存在する。これは、２１通り。

●並び (3 … )
　並び(3 2 … )や(3 4 … )は、平面が２つに分断されるので、存在しない。
　並び(3 5 … 6 4 2 1)は、並び(1 2 4 6 … 5 3)と対称である。したがって、
　平面グラフ
　　　　　　　　３─１─２─４─５─７─９
　　　　　　　　　　　　　　　＼│／│／│
　　　　　　　　　　　　　　　　６─８─10
　となる。
　まず、５への並び
　　　　　　　　　　　　３─１─２─４─５─７─９
　　　　　　　　　　　　　　　　　　　　│／│／│
　　　　　　　　　　　　　　　　　　　　６─８─10

　は、ｎ＝６　の場合の並びなので、９通り。

　次に、６への並び
　　　　　　　　　　　　　３─１─２─４　５─７─９
　　　　　　　　　　　　　　　　　　　　＼│／│／│
　　　　　　　　　　　　　　　　　　　　　６─８─10
　は、さらに分離して
　　　　　　　　　　　　　　３─１─２─４　５─７─９
　　　　　　　　　　　　　　　　　　　　　＼│　│／│
　　　　　　　　　　　　　　　　　　　　　　６　８─10　ｎ=4の場合の並びなので、４通り。
　と
　　　　３─１─２─４　５─７─９
　　　　　　　　　　　＼　　│／│
　　　　　　　　　　　　６─８─10　( … 6 8 10 9 7 5)となる１通りのみ。
　になる。

●並び (4 … )
　平面グラフ
　　　　　　　　４─２─１─３─５─７─９
　　　　　　　　　　　　　　　　│／│／│
　　　　　　　　　　　　　　　　６─８─10

　ｎ＝６　の場合の並びなので、９通り。

●並び (5 … )
　平面グラフ
　　　　　　　　５─３─１─２─４─６─７─９
　　　　　　　　　　　　　　　　　　　＼│／│
　　　　　　　　　　　　　　　　　　　　８─10
　まず、
　　　　　５─３─１─２─４─６─７─９
　　　　　　　　　　　　　　　　　│／│
　　　　　　　　　　　　　　　　　８─10

　ｎ＝４　の場合の並びなので、４通り。

　次に、
　　　　　　５─３─１─２─４─６　７─９
　　　　　　　　　　　　　　　　　＼│／│
　　　　　　　　　　　　　　　　　　８─10
　は、さらに分離して
　　　　　　　　　　　　　　５─３─１─２─４─６　７─９
　　　　　　　　　　　　　　　　　　　　　　　　　＼│　│
　　　　　　　　　　　　　　　　　　　　　　　　　　８　10　　１通り。
　と
　　　　５─３─１─２─４─６　７─９
　　　　　　　　　　　　　　　＼　　│
　　　　　　　　　　　　　　　　８─10　　１通り。
　になる。

●並び (6 … )
　平面グラフ
　　　　　　　　６─４─２─１─３─５─７─９
　　　　　　　　　　　　　　　　　　　　│／│
　　　　　　　　　　　　　　　　　　　　８─10

　ｎ＝４　の場合の並びなので、４通り。

●並び (7 … )
　平面グラフ
　　　　　　　　　７─５─３─１─２─４─６─８─９
　　　　　　　　　　　　　　　　　　　　　　　　＼│
　　　　　　　　　　　　　　　　　　　　　　　　　10　　２通り。

●並び (8 … )
　平面グラフ
　　　　　　　　　８─６─４─２─１─３─５─７─９─10　　１通り。

●並び (9 … )
　平面グラフ
　　　　　　　　　９─７─５─３─１─２─４─６─８─10　　１通り。


以上より、46＋21＋(9＋4＋1)＋9＋(4＋1＋1)＋4＋2＋1＋1＝104通り。


同様にして、求めていくと、

（コメント）　攻略法さんに感謝します。


　ＦＮさんからのコメントです。（平成２２年８月１９日付け）

　求める場合の数 g(n) を f(n) で表して欲しかったのですが。書かれたN=12までの数は正し
いと思いますので事実上出しておられるのかも知れませんが、それを式として明示してほし
い所でした。次のようになるはずです。

　　　　　g(n)＝f(n)＋f(n-2)＋f(n-3)＋･･･＋f(2)＋f(1)

　この式を用いると、上記の計算

　　　　46＋21＋(9＋4＋1)＋9＋(4＋1＋1)＋4＋2＋1＋1＝104

は、f(10)＋f(8)＋f(7)＋･･･＋f(2)＋f(1)　になっています。


g(n)=f(n)+f(n-2)+f(n-3)+･･･+f(2)+f(1)の証明(説明)

（証明）　1が一番左にあるのは、f(n)通り

　1が左から2番目にあるとき、  213･･･　または　312･･･で、前者は、f(n-2)通り。後者は

　3124･･･で、f(n-3)通り。

　1が左から3番目にあるとき、　42135･･･　または　53124･･･で、前者は、f(n-4)通り。後者

は、531246･･･で、f(n-5)通り。以下同様。　（証終）


　もう少しきちんと書く方がいいですが、そして最後がどこまでかも書くべきでしょうが、大体
ということにしておきます。これもオンライン整数列大辞典にあります。（→参考：「A069241」）

　次のように書いてありますから正しそうです。

Number of Hamiltonian paths in the graph on n vertices {1,...,n}, with i adjacent to j iff |i-j|<=2



　　　以下、工事中