平成１１年１２月２９日

［双子の並び方］

　太郎さんが勤務している学校には、何組かの双子がいます。今、全部で２ｎ人のｎ組の双子を

一列に並べる方法は何通りあるか、知りたくなりました。ただし、同じ組の双子は隣り合わないように

します。そこで、次の問いに答えてください。

問題１：ｎ＝１，２，３　のときの並び方は何通りあるか。

問題２：一般に、ａ(n)　通りあったとして、漸化式を導いてください。

問題３：可能なら、ａ(n)　をｎで表してください。

正直言って、まだ、太郎さんは一般の場合の答は知りません。

１２月２９日追加注釈

太郎さんは、同じ組の双子について、区別をする場合と、区別しない場合があることに

読者の寄せられた解答から気づきました。これから解答を寄せられる方は、先に区別しないで考えて、

その後、区別する場合に発展させてください。よろしくお願いします。

意外にあっさりいったので，勘違いしているかもしれません。

********************************

ｎ組の双子の位置関係の数（双子の入れ替わりを考えない場合）を，b(n)とします。

問題１

n＝1のときは，明らかに不可能　a(1)＝０，

n＝2のとき，２組の双子の位置関係は　○×○×　または　×○×○の２通りで　b(2)＝２

２組の双子がそれぞれ入れ替わることができるので，a(2)＝2^2*b(2)＝８

n＝3のとき，３組目の双子は，｜○｜×｜○｜×｜の５カ所の｜のうちの２カ所に入れるので，

b(3)＝5Ｃ2*b(2)＝20，したがって，a(3)＝2^3*b(3)＝160

問題２，問題３

n≧3のとき，問題１の考え方で，ｎ組目の双子の入り方は，(2n-1)Ｃ2通りなので，

　b(n)＝(2n-1)Ｃ2*b(n-1)が成り立つ。

　従って，b(n)＝(2n-1)(2n-2)/2*(2n-3)(2n-4)/2*・・・*5×4/2*b(2)

　　　　　　　＝b(2)*(2n-1)！/（3！*2＾(n-2))

ｎ組の双子は入れ替わり方は，２^nであるから，

　a(n)＝8(2n-1)！/3!＝4(2n-1)！/3　これは，n=2のときも成立

＜水の流れ：コメント＞２９日記入

「sambaGREEN」さんの解答の中で、

n＝3のとき，３組目の双子は，｜○｜×｜○｜×｜の５カ所の｜のうちの２カ所に入れるので，

としてありますが、例えば　　○｜○×｜×　　の中に３組目の双子入れる方法もありますから、

もれていますね。　

誤りのご指摘，ありがとうございました。sambaGREENです。

最近，こういうミス多いんですよね。自覚しているだけに重傷です（反省，体力回復せねば）。

考え直しましたが，実は行き詰まりました。というわけで，「解答」でなく「報告」という形で送らせていただきました。

**********************************************

ｎ組の双子の位置関係の数（双子の入れ替わりを考えない場合）で考えます。

双子の入れ替わりを考える場合，それに2^nをかければ，よいわけですから。

ｎ組の双子のうち，１組だけが隣り合う場合をb(n)，２組が隣り合う場合をc(n)とします。

問題１

n＝1のとき，あきらかに，a(1)＝０，b(1)＝１，c(1)＝０

n＝2のとき，a(2)＝２　○×○×，×○×○

　　　　　　b(2)＝２　○××○，×○○×

　　　　　　c(2)＝２　○○××，××○○

n＝3のとき，

まず，a(3)について，３組目の双子は，

　　　1○2×3○4×5の　５カ所のうちの２カ所に入れるので，5Ｃ2通り

　　　1○2×3×4○5の　3と，残りの４カ所のうちの１カ所に入るので，４通り

　　　1○2○3×4×5の　２と４に入らなければならないから，１通り

　　　よって，a(3)＝２*10＋2*4＋2*1＝30

b(3)について，３組目の双子は，

　　　1○2×3○4×5の　５カ所のうちの１カ所に隣り合って入るので，５通り

　　　1○2×3×4○5の　3に隣り合って入るか，残りの４カ所のうち２カ所で（1＋4Ｃ2）通り

　　　1○2○3×4×5の　2または4と，1，3，5のうち１カ所で，6通り

　　　よって，b(3)＝2*5＋2*7＋2*6＝36

c(3)について，３組目の双子は，

　　　1○2×3×4○5の　3以外の４カ所のうちの１カ所に隣り合って入るので，４通り

　　　1○2○3×4×5の　1,3,5のうち２カ所に入る，2または4に隣りあって入るで，3Ｃ2＋2通り

　　　よって，c(3)＝2*4＋2*5＝18

問題２

n≧3のとき，n＝3のときの考え方で，

　a(n)＝(2n-1)Ｃ2*a(n-1)＋(2n-2)*b(n-1)＋c(n-1)

　b(n)＝(2n-1)*a(n-1)＋{(2n-2)Ｃ2＋1}*b(n-1)＋2*(2n-3)*c(n-1)

　c(n)＝(2n-2)*b(n-1)＋{(2n-3)Ｃ2＋2}*c(n-1)

と，漸化式が完成したように思ったのですが，実はまだ，見落としがありました。

　○○・・・××・・・△△のように３組が隣り合う場合に，

　３カ所のうち２カ所に割って入る場合の数をb(n)に加える必要があります。

　３カ所のうち１カ所と，それ以外の１カ所入る場合の数をc(n)に加える必要があります。

つまり，３組が隣り合う場合d(n)を考える必要が生じます。そうすれば，今度は４組が，５組が・・・。無限地獄。

発想の転換が必要かもしれません。どなたか，よろしく・・・。

＜水の流れ：コメント＞２９日記入

いや、ありがたいです。いろいろな考え方から、思わぬ副産物のでてくる例はいくらでもあります。

私の目標の一般項まで至っていません。皆さん！お願いします。

双子の並び方の問題解答

　今回は十進Basicを使って解いてみました．

n=1--> 0

n=2--> 8

n=3--> 240

n=4--> 13824

n=5--> 1263360

　残念ながらパソコンでは，漸化式やら一般項を求める事は出来ませんので，このくらいで勘弁して下さい．

!futago.bas

let kosuu=0

for j0=0 to 1

let j1=0+1-j0

if int(j0/2)<>int(j1/2) then let kosuu=kosuu+1

next j0

print "n=1-->";kosuu!

let kosuu=0

for j0=0 to 3

for j1=0 to 3

if j0<>j1 and int(j0/2)<>int(j1/2) then

for j2=0 to 3

if j0<>j2 and j1<>j2 and int(j1/2)<>int(j2/2) then

let j3=0+1+2+3-j0-j1-j2

if int(j2/2)<>int(j3/2) then let kosuu=kosuu+1

end if

next j2

end if

next j1

next j0

print "n=2-->";kosuu

!

let kosuu=0

for j0=0 to 5

for j1=0 to 5

if j0<>j1 and int(j0/2)<>int(j1/2) then

for j2=0 to 5

if j0<>j2 and j1<>j2 and int(j1/2)<>int(j2/2) then

for j3=0 to 5

if j0<>j3 and j1<>j3 and j2<>j3 and int(j2/2)<>int(j3/2) then

for j4=0 to 5

if j0<>j4 and j1<>j4 and j2<>j4 and j3<>j4 and int(j3/2)<>int(j4/2) then

let j5=0+1+2+3+4+5-j0-j1-j2-j3-j4

if int(j4/2)<>int(j5/2) then let kosuu=kosuu+1

end if

next j4

end if

next j3

end if

next j2

end if

next j1

next j0

print "n=3-->";kosuu

!

let kosuu=0

for j0=0 to 7

for j1=0 to 7

if j0<>j1 and int(j0/2)<>int(j1/2) then

for j2=0 to 7

if j0<>j2 and j1<>j2 and int(j1/2)<>int(j2/2) then

for j3=0 to 7

if j0<>j3 and j1<>j3 and j2<>j3 and int(j2/2)<>int(j3/2) then

for j4=0 to 7

if j0<>j4 and j1<>j4 and j2<>j4 and j3<>j4 and int(j3/2)<>int(j4/2) then

for j5=0 to 7

if j0<>j5 and j1<>j5 and j2<>j5 and j3<>j5 and j4<>j5 and int(j4/2)<>int(j5/2) then

for j6=0 to 7

if j0<>j6 and j1<>j6 and j2<>j6 and j3<>j6 and j4<>j6 and j5<>j6 and int(j5/2)<>int(j6/2) then

let j7=0+1+2+3+4+5+6+7-j0-j1-j2-j3-j4-j5-j6

if int(j6/2)<>int(j7/2) then let kosuu=kosuu+1

end if　next j6

end if　next j5

end if　next j4

end if　next j3

end if　 next j2

end if　next j1

next j0

print "n=4-->";kosuu

!

let kosuu=0

for j0=0 to 9

for j1=0 to 9

if j0<>j1 and int(j0/2)<>int(j1/2) then

for j2=0 to 9

if j0<>j2 and j1<>j2 and int(j1/2)<>int(j2/2) then

for j3=0 to 9

if j0<>j3 and j1<>j3 and j2<>j3 and int(j2/2)<>int(j3/2) then

for j4=0 to 9

if j0<>j4 and j1<>j4 and j2<>j4 and j3<>j4 and int(j3/2)<>int(j4/2) then

for j5=0 to 9

if j0<>j5 and j1<>j5 and j2<>j5 and j3<>j5 and j4<>j5 and int(j4/2)<>int(j5/2) then

for j6=0 to 9

if j0<>j6 and j1<>j6 and j2<>j6 and j3<>j6 and j4<>j6 and j5<>j6 and int(j5/2)<>int(j6/2) then

for j7=0 to 9

if j0<>j7 and j1<>j7 and j2<>j7 and j3<>j7 and j4<>j7 and j5<>j7 and j6<>j7 and int(j6/2)<>int(j7/2) then

for j8=0 to 9

if j0<>j8 and j1<>j8 and j2<>j8 and j3<>j8 and j4<>j8 and j5<>j8 and j6<>j8 and j7<>j8 and int(j7/2)<>int(j8/2) then

let j9=0+1+2+3+4+5+6+7+8+9-j0-j1-j2-j3-j4-j5-j6-j7-j8

if int(j8/2)<>int(j9/2) then let kosuu=kosuu+1

end if　next j8

end if　 next j7

end if　next j6

end if　 next j5

end if　next j4

end if　next j3

end if　next j2

end i　 next j1

next j0

print "n=5-->";kosuu

end

双子の並び方の問題解答２

　いつの間にか注釈が追加されていました．気が付きませんでした．場合の数の問題で，区別がつく，つかないは重要なポイントです．しかし人間にからむ場合，たとえ双子でも，区別がつかない訳はありません．区別がつきにくい白球，赤球の並び方を求める訳ではないのですから，区別がつかない場合の数を求める必要はないと思うのですが，どうでしょう．

とにかく解いてみます．やはり今回はデータが具体的に残るエクセルのマクロを使いました．結果は，

n=1--> 0

n=2--> 2

n=3--> 30

n=4--> 864

n=5--> 39480

Option Explicit

Sub Macro1()

Dim j(9), aru(9), kosuu(5), j0, j1, j2, j3, j4, j5, j6, j7, j8, jj, n, m, dame As Integer

For j1 = 1 To 5: kosuu(j1) = 0: Next

Dim narabi As String

Range("A1").Select

n = 2

For j0 = 0 To n - 1: j(0) = j0

For j1 = 0 To n - 1

If j0 <> j1 Then

j(1) = j1

For j2 = 0 To n - 1

If j1 <> j2 Then

j(2) = j2

GoSub last

If j2 <> j(3) Then GoSub printing

End If

Next

End If

Next

Next　'

n = 3

For j0 = 0 To n - 1: j(0) = j0

or j1 = 0 To n - 1

If j0 <> j1 Then

j(1) = j1

For j2 = 0 To n - 1

If j1 <> j2 Then

j(2) = j2

For j3 = 0 To n - 1

If j2 <> j3 Then

j(3) = j3

For j4 = 0 To n - 1

If j3 <> j4 Then

j(4) = j4: m = 4: GoSub check

If dame = 0 Then

GoSub last

If j4 <> j(5) Then GoSub printing

End If

End If

Next

End If

Next

End If

Next

End If

Next

Next

'

n = 4

For j0 = 0 To n - 1: j(0) = j0

For j1 = 0 To n - 1

If j0 <> j1 Then

j(1) = j1

For j2 = 0 To n - 1

If j1 <> j2 Then

j(2) = j2

For j3 = 0 To n - 1

If j2 <> j3 Then

j(3) = j3

For j4 = 0 To n - 1

If j3 <> j4 Then

j(4) = j4: m = 4: GoSub check

If dame = 0 Then

For j5 = 0 To n - 1

If j4 <> j5 Then

j(5) = j5: m = 5: GoSub check

If dame = 0 Then

For j6 = 0 To n - 1

If j5 <> j6 Then

j(6) = j6: m = 6: GoSub check

If dame = 0 Then

GoSub last

If j6 <> j(7) Then GoSub printing

End If

End If

Next

End If

End If

Next

End If

End If

Next

End If

Next

End If

Next

End If

Next

Next'

n = 5

For j0 = 0 To n - 1: j(0) = j0

For j1 = 0 To n - 1

If j0 <> j1 Then

j(1) = j1

For j2 = 0 To n - 1

If j1 <> j2 Then

j(2) = j2

For j3 = 0 To n - 1

If j2 <> j3 Then

j(3) = j3

For j4 = 0 To n - 1

If j3 <> j4 Then

j(4) = j4: m = 4: GoSub check

If dame = 0 Then

For j5 = 0 To n - 1

If j4 <> j5 Then

j(5) = j5: m = 5: GoSub check

If dame = 0 Then

For j6 = 0 To n - 1

If j5 <> j6 Then

j(6) = j6: m = 6: GoSub check

If dame = 0 Then

For j7 = 0 To n - 1

If j6 <> j7 Then

j(7) = j7: m = 7: GoSub check

If dame = 0 Then

For j8 = 0 To n - 1

If j7 <> j8 Then

j(8) = j8: m = 8: GoSub check

If dame = 0 Then

GoSub last

If j8 <> j(9) Then GoSub printing

End If

End If

Next

End If

End If

Next

End If

End If

Next

End If

End If

Next

End If

End If

Next

End If

Next

End If

Next

End If

Next

Next

MsgBox "n=1-->" & kosuu(1) & Chr(13) & "n=2-->" & kosuu(2) & Chr(13) & "n=3-->" & kosuu(3) & Chr(13) & "n=4-->" & kosuu(4) & Chr(13) & "n=5-->" & kosuu(5)

End'

check:

For jj = 0 To n - 1: aru(jj) = 0: Next

For jj = 0 To m: aru(j(jj)) = aru(j(jj)) + 1: Next

dame = 0: jj = 0

While dame = 0 And jj < n: dame = -(aru(jj) > 2): jj = jj + 1: Wend

Return

'

last:

j(2 * n - 1) = 0

For jj = 1 To n - 1: j(2 * n - 1) = j(2 * n - 1) + 2 * jj: Next

For jj = 0 To 2 * n - 2: j(2 * n - 1) = j(2 * n - 1) - j(jj): Next

Return

'

printing:

kosuu(n) = kosuu(n) + 1

narabi = "": For jj = 0 To 2 * n - 1: narabi = narabi + Str$(j(jj)): Next

ActiveCell.FormulaR1C1 = kosuu(n)

SendKeys "{right}", True: ActiveCell.FormulaR1C1 = narabi

SendKeys "{down}", True: SendKeys "{left}", True

Return

End Sub

　このプログラムは計算が終わるのに１時間はかかるかも知れません．気をつけて下さい。

＜水の流れ：コメント＞　１１日記入

エクセルで開いてみたら、なの並び方がすべて書いてありました。全部で４０，３７６行あります。

この言葉通り、大変な作業のようです。本当にありがたいです。この時間に費やされた苦労に頭が下がります。

感謝の気持ちとお礼を言います。

　いつもお世話になっています。sambaGREENです。

もともとの問題の場合の数（双子のそれぞれを区別する場合）を　a(n)，

双子の入れ替わりを考えない場合（前回考えていた場合）をb(n)，

双子の位置のパターンの数（「○×○×」と「×○×○」を区別しない）をc(n)　とします。

a(n)＝2^n*b(n)，b(n)＝n!*c(n)が成り立ちますから，

c(n)を求めればよいことになります。

また，ｎ組の双子のうち，１組だけが隣り合うパターンの数をd(n)とします。

　　　　　　　　　　　　　（「○××○」と「×○○×」は区別しない）

n＝1のとき，あきらかに，c(1)＝０，d(1)＝1

n＝2のとき，c(2)＝1　○×○×

　　　　　　　　d(2)＝1　○××○

n＝3のとき，

　双子のパターンのみを考えていますから一番左を●とするともう一つの●は

1）●1○2×3○4×5　の場合　2〜5の４カ所に入ることが出来ます。

　　　●○●×○×

　　　●○×●○×

　　　●○×○●×

　　　●○×○×●

2）●1○2×3×4○5　の場合　3しか入れません。

　　　●○×●×○

　よって，c(3)＝4+1＝5

つぎに，d(3)について考えます。

1)　c(3)のパターンの左の●を右の●とくっつけることによって，

　　　●○●×○×　　→　○●●×○×　

　　　●○×●○×　　→　○×●●○×

　　　●○×○●×　　→　○×○●●×

　　　●○×○×●　　→　○×○×●●　

　　　●○×●×○　　→　○×●●×○　

2)　●●にc(2)のパターンをくっつけることによって，

　　　　　　　　　　　　　　　　●●○×○×

　よって，d(3)＝5+1＝6

n組の双子のときをn＝3のときの考え方と同じように考えていきます。

一番左を●とするともう一つの●は，

1)　c(n-1)のパターンそれぞれの，2n-2ヶ所に入ることができるから，(2n-2)*c(n-1)　通り

2)　d(n-1)のパターンそれぞれの，1ヶ所に入ることができるから，　　　　　d(n-1)　通り

したがって，　c(n)＝(2n-2)*c(n-1)＋d(n-1)

また，d(n)＝c(n)＋c(n-1)となるので，上式に代入して整理すると，

　　c(n)＝(2n-1)*c(n-1)＋c(n-2)　，c(1)＝0，c(2)＝1　となります。

Excelで計算した結果は以下の通りです。

「浜田さん」の２種類の計算結果の報告とも合致しているので，漸化式は正しいはずです。

しかし，残念ながら，私には一般項を求められませんでした。

どなたか，一般項を求めて下さい。もしくは求められないことを示して下さい。

（漸化式はあまり得意では・・・（泣））