ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (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
//

【問】
f:id:noriharu-katakura:20211101112051j:plain

【解】
(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 , D3 つの場合がすべてで排反である. このとき, A には, 3, 4, 5 が,  E には, 2, 3, 4 が常に配置できる. 最初,  A=1, B=2,  C=3, D=4,  E = 5 とおいて, その状態から置換するとすると,  A= 1 と互換できる (他の並びはひとつに決まってしまう) のは, C = 3 D = 42 通りだけである. その他の互換にならない場合を以下に求める.

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

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

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

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

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

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

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

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

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

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

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

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

 C =2 とすると,  E3 または 4 である. さらに場合分けして,  E = 3 とすると, この場合は  (A,B) = (5,4) になる.  E = 4 とすると,  B = 5 に決まるので, A= 31 つに決まる. 以上から,  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)