質問＜３６８＞２０００／１１／２３
X,Y,Z,Wの4種の文字をXも連続せず、Yも連続せず、Zも連続しないが、 Wは連続しても構わないという制限の下で、ｎ個を1列に並べる場合の 総数Sｎについて次の問に答えよ。 問１．S2を求めよ。 問２．S3を求めよ。 問３．S5を求めよ。 以上よろしくお願いします 静岡県 教員 原田佳彦
お返事２０００／１１／２３～２８
from=武田
一部ミスがありました。訂正を赤字でしてあります。 問１ ｘｙｚ ｗ ①② １ １ ０ ★☆ 3 Ｐ2 ＝３・２＝６通り １ １ ★ｗ 3 Ｃ1 ・2 Ｐ2 ＝３・１・２・１＝６通り ０ ２ ｗｗ １通り したがって、 Ｓ2 ＝６＋６＋１＝１３通り ……（答） 問２ ｘ ｙ ｚ ｗ ①②③ ２ １ ０ ★☆★ 3 Ｐ2 ＝３・２＝６通り １ １ １ ０ ★☆▲ 3 Ｐ3 ＝３・２・１＝６通り ２ １ ★ｗ★ 3 Ｃ1 ＝３通り １ １ １ ★☆ｗ 3 Ｃ2 ・3 Ｐ3 ＝３・３・２・１＝１８通り １ ２ ★ｗｗ 3 Ｃ1 ・３！／（１！・２！）＝３×３＝９通り ０ ３ ｗｗｗ １通り したがって、 Ｓ3 ＝６＋６＋３＋１８＋９＋１＝４３通り ……（答） 問３ ｘ ｙ ｚ ｗ ①②③④⑤ ２ ３ ０ ★☆★☆★ 3 Ｐ2 ＝６通り １ １ ３ ０ ★☆★▲★ 3 Ｃ1 ・2 Ｐ2 ＝６通り ２ ２ １ ０ ★☆★☆▲ 3 Ｃ2 ・｛５！／（２！２！１！）－２・４！／（２！１！１！）＋３！｝＝３６通り １ ３ １ ★☆★ｗ★ 3 Ｃ1 ・2 Ｃ1 ・2 Ｐ2 ＝３・２・２・１＝１２通り ２ ２ １ ★☆★☆ｗ 3 Ｃ2 ・｛５！／（２！２！１！）－２・４！／（２！１！１！）＋３！｝＝３６通り ２ １ １ １ ★☆★▲ｗ 3 Ｃ1 ・｛５！／（２！１！１！１！）－４！｝＝１０８通り ３ ２ ★ｗ★ｗ★ 3 Ｃ1 ＝３通り ２ １ ２ ★☆★ｗｗ 3 Ｐ2 ・｛５！／（２！１！２！）－４！／（２！１！１！）｝＝１０８通り １ １ １ ２ ★☆▲ｗｗ ５！／（２！１！１！１！）＝６０通り ２ ３ ★ｗ★ｗｗ 3 Ｃ1 ｛５！／（３！２！）－４！／（３！１！）｝＝１８通り １ １ ３ ★☆ｗｗｗ 3 Ｃ2 ・５！／（３！１！１！）＝６０通り １ ４ ★ｗｗｗｗ 3 Ｃ1 ・５！／（４！１！）＝１５通り ０ ５ ｗｗｗｗｗ １通り したがって、 Ｓ5 ＝６＋６＋３６＋１２＋３６＋１０８＋３＋１０８＋６０＋１８＋６０＋１５＋１ ＝４６９通り ……（答） ※下の関谷さんの解答と比べて、一部ミスを発見しました。
お便り２０００／１１／２７
from=Toshio Sekiya
（素晴らしいアイデアの解答が寄せられました。感謝感激！！ 武田） 武田先生こんにちは 今日先生のＨＰをみていたら、質問３６８が私のところにも来ていた問題でした。 私のほうの結果と違っているので、答えを吟味していただけたら幸いです。以下その 答案です。 Ｓ２やＳ３だけなら、がんばって数えていけば何とかなりますが、 Ｓ５あたりでは、少々厳しくなってきます。 そこで、この列の性質を分析して、もっと良い方法を見つけたいのです。 考えられる方法の１つに漸化式があります。 これは、ＳｎからＳｎ＋１を導く式を作るというものです。 ｎ＋１個並んだ列を考えます。 その列のはじめからｎ個を取った列も、問題の条件を満たしていることは明らかで す。 そこで、ｎ個の列を１つ取ったときに、その後ろに加えられる文字が何通りあるかを 調べれば、 Ｓｎ＋１が分かります。 この後ろに来る文字の場合の数は、はじめのｎ個の文字の列の最後の文字がＷか、 それ以外かによって異なります。 最後にＷが来た場合・・・次の文字はＸ，Ｙ，Ｚ，Ｗの４通り 最後にＷ以外（Ｘ，Ｙ，Ｚ）が来た場合・・・・次の文字は最後の文字と異なる文字 ３通り そこで、Ｓｎを次の２つの場合に分けて考えると良いでしょう。 Ｐｎ ・・・ 最後にＷが並ぶ、ｎ個の文字の列の総数 Ｑｎ ・・・ 最後にＷ以外の文字（Ｘ，Ｙ，Ｚ）が並ぶ、ｎ個の文字の列の総数 もちろん、Ｓｎ＝Ｐｎ＋Ｑｎになります。 ｎ個の列の最後にＷがあって、その次に、Ｗが加わる場合 ・・・・・・・ １通り ｎ個の列の最後にＷがあって、その次に、Ｘ，Ｙ，Ｚが加わる場合 ・・・ ３通り ｎ個の列の最後にＷ以外があって、その次に、Ｗが加わる場合 ・・・ １通り ｎ個の列の最後にＷ以外があって、その次に、Ｘ，Ｙ，Ｚが加わる場合 ・・・ ２ 通り これは、最後に来る文字と同一の文字は加えられないので、最後に来る各文字に対 して２通りずつあります。 以上の４つの場合から考えて、 Ｐｎ＋１＝Ｐｎ＋Ｑｎ Ｑｎ＋１＝３Ｐｎ＋２Ｑｎ ・・・・・・・・［１］ では、［１］の漸化式を使って、答えを出してみましょう。 Ｐ１＝１ Ｑ１＝３ です。 Ｐ２＝Ｐ１＋Ｑ１＝１＋３＝４ Ｑ２＝３Ｐ１＋２Ｑ１＝３＋２×３＝９ Ｐ３＝Ｐ２＋Ｑ２＝４＋９＝１３ Ｑ３＝３Ｐ２＋２Ｑ２＝１２＋１８＝３０ Ｐ４＝Ｐ３＋Ｑ３＝１３＋３０＝４３ Ｑ４＝３Ｐ３＋２Ｑ３＝３９＋６０＝９９ Ｐ５＝Ｐ４＋Ｑ４＝１４２ Ｑ５＝３Ｐ４＋２Ｑ４＝１２９＋１９８＝３２７ これより、 ｛Ｓ２＝４＋９＝１３ （答）｛Ｓ３＝１３＋３０＝４３ ｛Ｓ５＝１４２＋３２７＝４６９