質問<368>2000/11/23
X,Y,Z,Wの4種の文字をXも連続せず、Yも連続せず、Zも連続しないが、 Wは連続しても構わないという制限の下で、n個を1列に並べる場合の 総数Snについて次の問に答えよ。 問1.S2を求めよ。 問2.S3を求めよ。 問3.S5を求めよ。 以上よろしくお願いします 静岡県 教員 原田佳彦
お返事2000/11/23~28
from=武田
一部ミスがありました。訂正を赤字でしてあります。 問1 xyz w ①② 1 1 0 ★☆ 3 P2 =3・2=6通り 1 1 ★w 3 C1 ・2 P2 =3・1・2・1=6通り 0 2 ww 1通り したがって、 S2 =6+6+1=13通り ……(答) 問2 x y z w ①②③ 2 1 0 ★☆★ 3 P2 =3・2=6通り 1 1 1 0 ★☆▲ 3 P3 =3・2・1=6通り 2 1 ★w★ 3 C1 =3通り 1 1 1 ★☆w 3 C2 ・3 P3 =3・3・2・1=18通り 1 2 ★ww 3 C1 ・3!/(1!・2!)=3×3=9通り 0 3 www 1通り したがって、 S3 =6+6+3+18+9+1=43通り ……(答) 問3 x y z w ①②③④⑤ 2 3 0 ★☆★☆★ 3 P2 =6通り 1 1 3 0 ★☆★▲★ 3 C1 ・2 P2 =6通り 2 2 1 0 ★☆★☆▲ 3 C2 ・{5!/(2!2!1!)-2・4!/(2!1!1!)+3!}=36通り 1 3 1 ★☆★w★ 3 C1 ・2 C1 ・2 P2 =3・2・2・1=12通り 2 2 1 ★☆★☆w 3 C2 ・{5!/(2!2!1!)-2・4!/(2!1!1!)+3!}=36通り 2 1 1 1 ★☆★▲w 3 C1 ・{5!/(2!1!1!1!)-4!}=108通り 3 2 ★w★w★ 3 C1 =3通り 2 1 2 ★☆★ww 3 P2 ・{5!/(2!1!2!)-4!/(2!1!1!)}=108通り 1 1 1 2 ★☆▲ww 5!/(2!1!1!1!)=60通り 2 3 ★w★ww 3 C1 {5!/(3!2!)-4!/(3!1!)}=18通り 1 1 3 ★☆www 3 C2 ・5!/(3!1!1!)=60通り 1 4 ★wwww 3 C1 ・5!/(4!1!)=15通り 0 5 wwwww 1通り したがって、 S5 =6+6+36+12+36+108+3+108+60+18+60+15+1 =469通り ……(答) ※下の関谷さんの解答と比べて、一部ミスを発見しました。
お便り2000/11/27
from=Toshio Sekiya
(素晴らしいアイデアの解答が寄せられました。感謝感激!! 武田) 武田先生こんにちは 今日先生のHPをみていたら、質問368が私のところにも来ていた問題でした。 私のほうの結果と違っているので、答えを吟味していただけたら幸いです。以下その 答案です。 S2やS3だけなら、がんばって数えていけば何とかなりますが、 S5あたりでは、少々厳しくなってきます。 そこで、この列の性質を分析して、もっと良い方法を見つけたいのです。 考えられる方法の1つに漸化式があります。 これは、SnからSn+1を導く式を作るというものです。 n+1個並んだ列を考えます。 その列のはじめからn個を取った列も、問題の条件を満たしていることは明らかで す。 そこで、n個の列を1つ取ったときに、その後ろに加えられる文字が何通りあるかを 調べれば、 Sn+1が分かります。 この後ろに来る文字の場合の数は、はじめのn個の文字の列の最後の文字がWか、 それ以外かによって異なります。 最後にWが来た場合・・・次の文字はX,Y,Z,Wの4通り 最後にW以外(X,Y,Z)が来た場合・・・・次の文字は最後の文字と異なる文字 3通り そこで、Snを次の2つの場合に分けて考えると良いでしょう。 Pn ・・・ 最後にWが並ぶ、n個の文字の列の総数 Qn ・・・ 最後にW以外の文字(X,Y,Z)が並ぶ、n個の文字の列の総数 もちろん、Sn=Pn+Qnになります。 n個の列の最後にWがあって、その次に、Wが加わる場合 ・・・・・・・ 1通り n個の列の最後にWがあって、その次に、X,Y,Zが加わる場合 ・・・ 3通り n個の列の最後にW以外があって、その次に、Wが加わる場合 ・・・ 1通り n個の列の最後にW以外があって、その次に、X,Y,Zが加わる場合 ・・・ 2 通り これは、最後に来る文字と同一の文字は加えられないので、最後に来る各文字に対 して2通りずつあります。 以上の4つの場合から考えて、 Pn+1=Pn+Qn Qn+1=3Pn+2Qn ・・・・・・・・[1] では、[1]の漸化式を使って、答えを出してみましょう。 P1=1 Q1=3 です。 P2=P1+Q1=1+3=4 Q2=3P1+2Q1=3+2×3=9 P3=P2+Q2=4+9=13 Q3=3P2+2Q2=12+18=30 P4=P3+Q3=13+30=43 Q4=3P3+2Q3=39+60=99 P5=P4+Q4=142 Q5=3P4+2Q4=129+198=327 これより、 {S2=4+9=13 (答){S3=13+30=43 {S5=142+327=469