陥没地帯 (268) - ノリの悪い日記

$2020$ 年宮崎大の問題. それぞれの場合分けごとに, 繊細な差異が生じていることに気がついて, 楽しめる一題. 撹乱順列 (完全順列 / モンモールの問題) よりもさらに条件が複雑である.

※ この問題は, その後, Ménage numbers and ladies-first solutions そのもので, 組合せ論では非常に有名なものだということがわかり, とても勉強になった. なお大人 $6$ 人, 子ども $6$ 人のときの子どもの並べ方は, やはり $80$ 通りだった. 数列は, $1, 2, 13, 80, 579, 4738, 43387, 439792 \cdots$ とある.

Ménage problem - Wikipedia
//

【問】

【解】
$(1)$ 大人を配置する円順列は, $2$ 通り. $1A2B3C1$ として, $A$ , $B$ , $C$ に子どもを配置するのは, $A=3$ , $B= 2$ , $C=1$ のときしかない. したがって $T(3) =2$ である.

$(2)$ 大人を配置する円順列は, $6$ 通り. $1A2B3C4D1$ として, 背番号 $1$ の子どもを配置できるのは, $B$ または $C$ である.

$B = 1$ のとき:
$C = 2$ に決まるので, $D=3$ , したがって $A=4$ である.

$C = 1$ のとき:
$B = 4$ に決まるので, $A=3$ , したがって $D=2$ である.

以上より, $T(4) =12$ である.

$(3)$ 大人を配置する円順列は, $(5-1)! = 24$ 通り. $1A2B3C4D5E1$ として, 背番号 $1$ の子どもを配置できるのは, $B$ , $C$ , $D$ の $3$ つの場合がすべてで排反である. このとき, $A$ には, $3$ , $4$ , $5$ が, $E$ には, $2$ , $3$ , $4$ が常に配置できる. 最初, $A=1$ , $B=2$ , $C=3$ , $D=4$ , $E = 5$ とおいて, その状態から置換するとすると, $A= 1$ と互換できる (他の並びはひとつに決まってしまう) のは, $C = 3$ と $D = 4$ の $2$ 通りだけである. その他の互換にならない場合を以下に求める.

【 $B = 1$ のとき】
$C$ には, $2$ と $5$ , $D$ には, $2$ と $3$ の子どもが配置できる.

$2$ がおけるのは $C$ , $D$ , $E$ がすべてである.

$C= 2$ とすると, $D = 3$ , したがって, $E =4$ , $A =5$ と $1$ つに決まる.

$D =2$ とすると, $C=5$ で,この場合 $(A,E) = (3,4),(4,3)$ の $2$ 通りがある.

$E = 2$ とすると, $C = 5$ , $D =3$ に決まるので, $A= 4$ と $1$ つに決まる. 以上から, $B=1$ の場合, $4$ 通りある.

【 $C = 1$ のとき】
$B$ には, $4$ と $5$ , $D$ には, $2$ と $3$ の子どもが配置できる. $A$ は互換の場合を除くので, $4$ と $5$ が配置できる.

$2$ がおけるのは $D$ , $E$ がすべてである.

$E= 2$ とすると, $D = 3$ , したがって, この場合, $(A,B) = (4, 5),(5,4)$ の $2$ 通りがある.

$D= 2$ とすると, $E$ は $3$ だけが許される. この場合, $(A,B) = (4, 5),(5,4)$ の $2$ 通りがある. 以上から, $C=1$ の場合, $4$ 通りある.

【 $D = 1$ のとき】
$B$ には, $4$ と $5$ , $C$ には, $2$ と $5$ の子どもが配置できる. $A$ は互換の場合を除くので, $3$ と $5$ が配置できる.

$2$ がおけるのは $C$ , $E$ がすべてである.

$E= 2$ とすると, $C = 5$ , したがって, $B =4$ , $A =3$ と $1$ つに決まる.

$C =2$ とすると, $E$ は $3$ または $4$ である. さらに場合分けして, $E = 3$ とすると, この場合は $(A,B) = (5,4)$ になる. $E = 4$ とすると, $B = 5$ に決まるので, $A= 3$ と $1$ つに決まる. 以上から, $D=1$ の場合, $3$ 通りある.

以上から, 大人の配置ひとつあたり, 子どもの配置の仕方は $2+ 4 + 4 + 3 = 13$ 通りある.

したがって,

$T(5) = 24 \times 13 = 312$

である.//

※ 大人 $6$ 人, 子ども $6$ 人のときの子どもの並べ方は $80$ 通りだと思う. $n$ が偶数のときと, 奇数のときで場合分けが必要な気がする.

※ 問 $(3)$ の子どもの順列は, 以下の $13$ 通りである. すべての要素を動かすのだから $n = 5$ のとき, 置換の型が $2^13^1$ と $5^1$ しかないのは当然である. 互換は隣接する要素の間では生じないので, $5^1$ は $5$ つしかない.

$31524$ $(1,3,5,4,2)$
$34512$ $(1,3,5,2,4)$
$35124$ $(1,3)(2,5,4)$
$35214$ $(1,3,2,5,4)$
$41523$ $(1,4,2)(3,5)$
$41532$ $(1,4,3,5,2)$
$45123$ $(1,4,2,5,3)$
$45132$ $(1,4,3)(2,5)$
$45213$ $(1,4)(2,5,3)$
$51234$ $(1,4,5,3,2)$
$54123$ $(1,5,3)(2,4)$
$54132$ $(1,5,2,4,3)$
$54213$ $(1,5,3,2,4)$