『今週の問題』第152回　解答

◆広島県　清川　育男 さんからの解答

【問題１−１】

猪，兎，牛
兎，牛，猪
牛，猪，兎
【問題１−２】

１２通り。

【問題２−１】

猪，兎，牛，猫
兎，牛，猫，猪
牛，猫，猪，兎
猫，猪，兎，牛
【問題２−２】

５７６通り。

【おまけ】

１０８７７６０３２４５９０８２９５６８００通り。

1,2,12,576,161280,812851200,
61479419904000,108776032459082956800,
5524751496156892842531225600,
9982437658213039871725064756920320000

◆千葉県　なのはな子 さんからの解答

【問題１−１】

牛，猪，兎
兎，牛，猪
猪，兎，牛
【問題２−１】
猫，牛，猪，兎
猪，兎，猫，牛
牛，猫，兎，猪
兎，猪，牛，猫
【問題１−２】と【問題２−２】

ラテン方陣って初めて知りました。おもしろいものですね。

◆愛知県　Y.M.Ojisan さんからの解答

【問題１−１】

猪，兎，牛
牛，猪，兎
兎，牛，猪
【問題１−２】

１２とおり

∵　ラテン方陣成立状態に対して３匹の任意の置換はラテン方陣である。
よって、第一行を固定し結果を３！倍＝６倍してよい。

６個の置換のうち、恒等置換１個と互換３個を除くと２個の巡環置換が残り、２行目は各２通り可能である。
３行目は選択の余地なしである。
よって全部で６×２＝１２とおりである。

【問題２−１】

猪，兎，牛，猫
猫，猪，兎，牛
牛，猫，猪，兎
兎，牛，猫，猪
【問題２−２】

５７６とおり

∵　ラテン方陣成立状態に対して４匹の任意の置換はラテン方陣である。
よって、第一行を固定（猪，兎，牛，猫）し
結果を４！倍＝２４倍してよい。

第２行において（猪）の置き先は２，３，４列目の３通りあるが対称であるから、２列目に固定して結果を３倍してよい。

　兎の置き先は（１）１列目　（２）３または４列目の２タイプである。

（１）の場合、２行目は（兎、猪、猫、牛）に限られる。
よって３行目は、１、２列目が猫と牛、３、４列目が兎と猪が自由にえらべて都合４通りである。

（２）の場合２行目は３列４列の対称性から（猫、猪、兎、牛）に限って２倍すればよい。
この時３行目は（牛、猫、猪、兎）（兎、牛、猫、猪、）の２とおりだけ可能である。

４行目は選択の余地なしである。

よって　２４×３×（４＋２×２）＝５７６

【おまけ１】

【準備１】

ｎ個のものの置換の数T(n)は　　T(n)＝n!

∵周知

【準備２】

ｎ個のものの置換で移動しないものが無いものの数D(n)は次の漸化式を満たす｡
なお、D(1)=0 であり、D(0)=1　とする。

D(n)=T(n)-nC1*D(n-1)-nC2*D(n-2) ...- nCn-1 *D(1)-D(0)

∵上式は単純に全置換から、１個だけ一致するもの、２個だけ一致するもの、...、全部一致するもの（１個）を引いているだけである。

【準備３】

ｎ個のものの置換で特定の１個を除き移動しないものが無いものの数D(n,1)は次の漸化式を満たす｡
なお、D(1,1)=1 である。

D(n,1)=D(n-1)+(n-1)*D(n-1,1)=D(n+1)/n=D(n-1)+D(n)

∵上式は特定の１個が移動しない場合と、残りn-1個所に移動した場合の数の和である。

【準備４】

ｎ個のものの置換で特定の２個を除き移動しないものが無いものの数D(n,2)は次の漸化式を満たす｡
なお、D(1,2)=0　とする。

D(n,2)=D(n,1) + D(n-1,1)

∵上式は特定の2個のうち1個を通常状態とした場合の数と、その１個を移動しなかった場合の数の和である。
なお一般にはD(n,m)=D(n,m-1)+D(n-1,m-1)

以上の計算結果を下表に示す。

【上限】

行の置換、列の置換はラテン方陣の状態を崩さないので、
８×８セルの一行目と一列目の配置を固定（黄色セル）して
８！×７！倍すればよい。

２列目（緑セル）は１列目に対して、全て移動する置換で１つが固定されている置換の数の可能性がある。
即ち、D(7,1)=D(8)/7=2119個である。

２〜８行目は１行目に対して、全て移動する置換の可能性があるが、１列目と２列目が固定されているので、固定されたものの状態により
D(6)かD(6,1)かD(6,2)とおりの可能性がある。
これらの最大値は362である。

６行目に関しては特定の１種に関してみると３箇所が残されているだけなので
最大の可能性は3*3*3*3*2=162(＜362)とおりである。

同様に７行目は２の５乗=32とおり,８行目は１とおりが最大である。

よって、上限値として　
8!*7!*2119*3624*2*34*25≒3.84×1025

【下限】

行の置換、列の置換はラテン方陣の状態を崩さないので、
８×８セルの一行目と一列目の配置を固定（黄色セル）して
８！×７！倍すればよいのは上限と同じ。

セルを下図のように４×４のラテン方陣４個に分けて、個々に数えると

赤枠は問題２より５７６通り｡

黒枠は１列制限されているので
576/4!=24とおり。

青枠は１行１列制限されているので
576/4!/3!=4とおり。

４×４への分け方は　8C4/2=35とおりである。

よって、下限値として

8!*7!*35*576*242*4≒9.44×1015

【感想】

おまけは多様なこたえが出てきて面白い問題になるでしょう。
余裕があればもう少し狭めたいところです。
正解は多分1020あたりでしょう。

PCで計算してみました。
１０８,７７６,０３２,４５９,０８２,９５６,８００

　◆ 問題へもどる

　◆ 今週の問題へ

数学の部屋へもどる