・ ある順列 Ｓ．Ｈ氏
つれづれなるままに、数字の１から９までの９個の数字を次のように並べてみた。
３ ６ ９ ２ ５ ８ １ ４ ７
この順列は、隣り合うどんな２数を選んでも、その差は、３以上ある。もっとも、これは、３
で割った余りで分類した数を配列しているので、その境目だけを注意して見れば納得され
る。
さらにこの順列は驚くべき性質を持っている。自分自身と一つ置いた数との差も常に３以
上なのである。（たとえば、９−３＝６、９−５＝４）
果たして、このような２つの性質を持つ順列は、上記以外ないのだろうか？
もし、ないとすれば、この順列の特殊性に感嘆させられる。
（追記） 平成２２年６月５日付け
ＦＮさんより、「上記の性質を持つ順列は左右対称を除いて１つしかない。」旨、ご教示頂
いた。比較的きれいに証明できるそうである。
（ＦＮさんによる証明 平成２２年６月１０日付け）
条件を満たす順列を左から３個ずつのグループに分ける。１つのグループ内の数は
互いに３以上の差があるから、１、２、３ は異なるグループに属する。
１、２、３ が属するグループをそれぞれ Ｇ1、Ｇ2、Ｇ3 とする。
４は、Ｇ2、Ｇ3 には入れないから、Ｇ1 に入る。そうすると、５は、Ｇ1、Ｇ3 に入れないか
ら、Ｇ2 に入る。
同様にして、６は、Ｇ3 に入る。同様にして、７、８、９ はそれぞれ、Ｇ1、Ｇ2、Ｇ3 に入る。
よって、 Ｇ1＝｛１，４，７｝ 、Ｇ2＝｛２，５，８｝ 、Ｇ3＝｛３，６，９｝
次に、Ｇ1 と Ｇ2 が隣り合うとする。Ｇ2 のすぐ隣にくる Ｇ1 の元は、Ｇ2 の元で距離が
３以上であるものが２つ以上ないといけない。
４は８だけ、７は２だけ、１は５と８だから、１だけ Ｇ2 のすぐ隣にくることができる。
同様に、Ｇ1 のすぐ隣にくる Ｇ2 の元は８しかない。
すなわち、Ｇ1 と Ｇ2 が隣り合うとすれば、直接隣り合うのは、１と８
.
同様にして、Ｇ1 と Ｇ3 が隣り合うとすれば、直接隣り合うのは、１と９
Ｇ2 と Ｇ3 が隣り合うとすれば、直接隣り合うのは、２と９
このうちの２つが成り立つが、１が Ｇ2、Ｇ3 と直接隣り合うことになるので、最初の２
つは両立しない。同様に最後の２つも両立しない。
従って、１つ目と３つ目が成り立つことになり、左右対称なものは１つと見るので、
Ｇ1Ｇ2Ｇ3と並ぶものと考えてよい。
ａ ｂ １ ８ ｃ ２ ９ ｄ ｅ となるが、ｃ＝５ である。また、ａ＝７、ｂ＝４ である。
同様に、ｄ＝６、ｅ＝３ である。
故に、 ７ ４ １ ８ ５ ２ ９ ６ ３ あるいは、左右逆にして ３
６ ９ ２ ５ ８ １ ４ ７
である。 （証終）
また、１から ｎ までの ｎ個（ただし、ｎ≦８）の数字については、条件を満たす順列はない
とのこと。
（ＦＮさんによる証明 平成２２年６月１０日付け）
ｎ＝２ のとき存在しないことは明らか。
ｎ≧３ とする。条件を満たす順列が存在するとして、左から３個ずつのグループに
分ける。（２つ目、３つ目は要素が２個や１個であったり空集合である可能性はある。）
１、２、３ は異なるグループに属するから、３つ目は空集合ではない。
従って、１つ目、２つ目は３個の要素をもつとしてよいので、ｎ≧７ でなければならな
い。上と同様に、Ｇ1、Ｇ2、Ｇ3 とすると、
Ｇ1＝｛１，４，７｝ 、Ｇ2＝｛２，５｝ 、Ｇ3＝｛３，６｝
となる。Ｇ2、Ｇ3 は他の元をもつかもしれない。
３つ目も、２個の要素を持つから、ｎ≧８ でなければならない。
このとき、Ｇ2＝｛２，５，８｝ で、 Ｇ3 は、Ｇ1 か Ｇ2 と隣り合うことになるが、３ も ６
も Ｇ1、Ｇ2 とは隣り合うことはできない。 （証終）
らすかるさんによれば、各 ｎ の値に対して、下表のように順列の数があるそうである。
| ｎ |
９ |
１０ |
１１ |
１２ |
１３ |
１４ |
１５ |
１６ |
| 順列の数 |
１ |
２０ |
３９６ |
７６８７ |
１４０７１７ |
２５４４５３０ |
４６５４１２６６ |
８７１８００５３８ |
この場合の数は、ｎ を大きくすると、大体 ｎ！/（２ｅ8） ぐらいだという。
さらに、ＦＮさんによれば、１から ｎ までの ｎ 個の整数で、
隣り合う２数の差は４以上、１つおいた数との差も４以上、２つおいた数との差も４以上
という条件を満たす順列は、ｎ＝１６ のとき、左右対称を除いて１つしかないそうである。
らすかるさんによれば、各 ｎ の値に対して、下表のように順列の数があるそうである。
| ｎ |
１６ |
１７ |
１８ |
１９ |
２０ |
２１ |
| 順列の数 |
１ |
３７ |
１２１２ |
４６７１２ |
２１９７１９３ |
１００６７７７４０ |
この場合の数は、ｎ を大きくすると、大体 ｎ！/（２ｅ18） ぐらいだという。
ｎ＝１６ のとき、１通りしかないと聞いて、求めてみた。次の順列が求めるものになるの
であろう。
１３ ９ ５ １ １４ １０ ６ ２ １５ １１ ７ ３ １６ １２ ８ ４
ところで、らすかるさんによれば、解の構造は、冒頭の並びと同様とのことで、
４ ８ １２ １６ ３ ７ １１ １５ ２ ６ １０ １４ １ ５ ９ １３
でいいらしい。（平成２２年６月６日付け）
（コメント） 私自身、ＧＡＩ さんと同様に「２つおいた数との差も４以上」という部分に苦労し
て、その結果として上記の解を得たのですが、らすかるさんによれば、単に、
（４で割った余り ０）（４で割った余り ３）（４で割った余り ２）（４で割った余り １）
と並べればよかったということですね！私の得た解とらすかるさんの解は、ちょうど
左右対称になっています。
ＧＡＩ さんは、この問題と同様にして、１から ｎ までの ｎ 個の整数で、
隣り合う２数の差は５以上、１つおいた数との差も５以上、
２つおいた数との差も５以上、３つおいた数との差も５以上
という条件を満たす順列は、ｎ＝２５ のとき、左右対称を除いて唯１通り存在する
という問題に拡張されうるのかと問われたが、答えは「Ｙｅｓ！」らしい。
らすかるさんによれば、解の構造は、全く同じで、
5 10 15 20 25 4 9 14 19 24 3 8 13 18 23 2 7 12 17 22 1 6 11 16 21
が唯一の解とのことである。
また、ＦＮさんは、次のような問題を新たに提起された。（平成２２年６月６日付け）
１から ｎ までの ｎ 個の整数で、
隣り合う２数の差が２以上
という条件を満たす順列は、何通りあるだろうか？
これはひょっとしたら、ｎ の式で書けるだろうか。あるいは漸化式のようなものが作れる
だろうか。
この件に関して、らすかるさんからの情報で、次のページに漸化式が書かれているそう
である。
http://www.research.att.com/~njas/sequences/A002464
