◆大阪府 ＣＨＥＣＫ さんからの解答。
【本命問題】
題意の数列の個数はカタラン数に等しいので
| 2nＣn ｎ＋1 | 通り。 |
以下は証明。
ｘｙ平面上の領域｛0≦ｘ≦ｎ，0≦ｙ≦ｎ｝内において
原点Ａ（0，0）から点Ｂ（ｎ，ｎ）までの最短経路を考える。
（1回の移動において(＋1，0)（0，＋1）方向のいずれかを等確率で選んでいく）
ここで，金太郎飴数列において，
値が1となる項を（＋1，0）方向，−1となる項を（0，＋1）方向への移動と対応させる。
このとき，金太郎飴数列において，初項からの和が常に負でないという条件は，
最短経路が直線Ｌ：ｙ＝ｘ＋1上の点を通過しないという条件に対応する。
まず，点ＡからＢまでの経路数は，
Ｌ上を通ってもかまわない場合も含めて
2nＣn通り。
次にＬ上を通過する経路を数える。
このような経路の1つについて最初にＬと交わった点以降はＬについて折り返した道順を考えると，
これは点Ａから点Ｐ（ｎ−1，ｎ＋1）に至る道順の1つと対応する。
この逆の対応も成り立つ。
よって点Ａから点Ｐに行く最短経路数と1対1対応であり，
2nＣn-1通り。
以上より題意の数列の個数は
| 2nＣn−2nＣn-1＝ | 2nＣn ｎ＋1 | 通り。 |
【感想】
「金太郎飴数列」というネーミングはいいですね，ぴったりです。
数列の切断のここまでつっこんだ問題は僕にとっては目新しく参考になりました。
【出題者のコメント】
おみごとです！
必要にして十分に明解です。
カタラン数になることが判明すれば、解けたのも同然ですね。
「括弧の位置問題」や「多角形の三角形分割問題」の解がカタラン数になるのは、あまりにも有名ですが、整列問題として出題してみました。
◆愛知県 Y.M.Ojisan さんからの解答。
『５つのナップザック 』の解答をご覧ください。
【出題者のコメント】
【問題２】を、追加します。
（Y.M.Ojisan さんの解法がヒントになって出来た問題です）
◆大阪府 ＣＨＥＣＫ さんからの解答。
【問題２】
ｘｙ平面上の動点Pを考える。
最初Pは原点(0,0)にあり，A(男)，B(女)の順列に対して，
AならばPは(+1,+1)方向に,BならばPは(+1,-1)方向に移動するように対応させる。
このとき,Pの移動した経路（点列）を順に線分で結んでいくことにより
区間0≦ｘ≦2ｎに1本の連続したグラフができる。
このグラフをｙ＝f(x)とし，f(x)はｘ＝ｔのときに最小値ｍをとるとする。
（1）ｍ≧0のとき，f(x)≧0よりA,Bの順列は金太郎飴整列となる。
（2）ｍ＜0のとき，グラフｙ＝f(x)を(−ｔ,−ｍ)方向に平行移動させ，
その後に−ｔ≦ｘ≦0の部分を(+2ｎ,0)方向に平行移動させてできるグラフを
ｙ＝g(x)とすれば，このグラフは常にg(x)≧0を満たし，かつ連続であり，
g(0)＝g(2ｎ)＝0である。
よってこのグラフｙ＝g(x)に従ってA,Bの順列を定めれば金太郎飴整列となる。
（g(1)は当然正であり，先頭は男生徒となる）
また，ｙ＝f(x)からｙ＝g(x)への変形操作は，円周上に並ぶ男女ｎ人ずつの円順列の先頭の男生徒を変える操作に対応する。
以上から，どのような円周上の並び方をしていても、先頭になればその１列が「金太郎飴整列」になる男生徒が、ｎ人の内で少なくとも１人は存在する。
【感想】
金太郎飴整列は設定の変え方次第でいろいろ拡張できますね。
なかなか面白いです。
なお，この問題2から以下のようなことも分ります。
| ｎ人ずつの男生徒と女生徒がおり，その２ｎ人が，十分大きな円周上の任意の位置に全員並んでいる。 ここで男女1人ずつのペアをｎ組作り，ペアの男女を線分で結ぶ。 このとき，ｎ本全ての線分が他の線分と交点を持たないようなペアの作り方が少なくとも1つ存在する。 |