・不変な大小関係                         GAI 氏

 2×2行列に、1〜4を下図のように配置する。(これを順序配列行列と呼び、Aと記す。)

[3 4]
[1 2]

 次に、2×3行列に、1〜6を一個ずつ配置されたものの中で、

[4 5 6]
[1 2 3]
  または   [3 5 6]
  [1 2 4]

と配置した時は、どちらの行列も、1,2列;2,3列で分離したもの、例えば、

<上の例の上部で説明すれば>

 [4 5] | [5 6]
 [1 2] | [2 3]

のそれぞれ2×2行列の数字の大小に関する配置の法則は、元のAと同型と見なせる。

 そこで、2×4行列に、1〜8を一個ずつ配置する中で、1,2列 | 2,3列 | 3,4列で分離した時
それぞれに含まれる数字の大小での配列がAと同型になれるものは、8!通りの中で何通
り可能か?

 また、2×5行列なら何通りか?
(1〜10を配置する10!通りの中で、1,2列 | 2,3列 |3,4列 | 4,5列での分離がすべてAと同型に
なりえるパターン数)

 これを、2×10行列まで調べてほしい。


 らすかるさんからのコメントです。(平成30年11月26日付け)

 条件の解釈が正しければ、多分、2×n 行列のとき、

 「(1,0)から(n,n-1)まで右か上に1ずつ、y=xに触れないように行く場合の数」

に等しいので、(2n-2)C(n-1)/n通り。

 よって、n=4〜10の具体値は、5、14、42、132、429、1430、4862


 ハンニバル・フォーチュンさんからのコメントです。(平成30年11月26日付け)

 脊髄反射ですが、これは二次元のカタラン数ではないのですかね…。


 GAI さんからのコメントです。(平成30年11月26日付け)

 脊髄反射と言うんですか。

 n=4 なら、次の5タイプ

[5 6 7 8]
[1 2 3 4]
  [4 6 7 8]
[1 2 3 4]
  [4 5 7 8]
[1 2 3 6]
  [3 6 7 8]
[1 2 4 5]
  [3 5 7 8]
[1 2 4 6]

 n=5 なら、次の14タイプ

[6 7 8 9 10]
[1 2 3 4  5]
  [5 7 8 9 10]
[1 2 3 4  6]
  [5 6 8 9 10]
[1 2 3 4  7]
  [5 6 7 9 10]
[1 2 3 4  8]
  [4 7 8 9 10]
[1 2 3 5  6]
  [4 6 8 9 10]
[1 2 3 5  7]
  
[4 6 7 9 10]
[1 2 3 5  8]
[4 5 8 9 10]
[1 2 3 6  7]
[4 5 7 9 10]
[1 2 3 6  8]
[3 7 8 9 10]
[1 2 4 5  6]
[3 6 8 9 10]
[1 2 4 5  7]
[3 6 7 9 10]
[1 2 4 5  8]
 
[3 5 8 9 10]
[1 2 4 6  7]
[3 5 7 9 10]
[1 2 4 6  8]

 以降、らすかるさんが示される数列が並び、これは正にカタラン数になっていきます。


 ハンニバル・フォーチュンさんからのコメントです。(平成30年11月27日付け)

 さて、Aは、

[3 4]
[1 2]

でした。Aの他に、Åとして

[2 4]
[1 3]

を定義したとします。

 もとの行列から任意に二行二列を切り出したときに、それがいつでもAまたはÅと同型と
なる、そのような(もとの行列)は何通りあるのかについて、数えあげるという問題も考えら
れます。

 3×4の行列に、1〜12を一個ずつ配置されたものの中で数えますと、462通りあるようです。

  (5 * 5) + (16 * 16) + (10 * 5) + (5 * 10) + (9 * 9) = 462


 ハンニバル・フォーチュンさんからのコメントです。(平成30年11月30日付け)

 「A060855」にありました。



                         投稿一覧に戻る