■コマネチ大学数学科65講：順列組み合わせ

　

「インド式計算ドリル」がニンテンドーDSで今年の冬発売が決定した中村亨センセがひさしぶりに登場。渋谷スタジオでの収録は今夜が最後。次回からはダイ♪ダイ♪ダイ♪ダイバスター♪お台場スタージオで収録の「たけしのコマネチ大学数学科」第65講。今回は順列組み合わせ……ということなのだが。

問題：1枚500円のチケット売り場に500円玉を持った6人と1000円札しか持っていない6人の合計12人が並んでいる。販売開始時に売り場係りが釣銭を用意していないとすると、釣銭が不足しないような客の並び方は何通りあるか？

　この問題、すでに、このブログの「数学オリンピック：つり銭問題」というエントリーで紹介してしまっていた；；

　釣銭を用意していないという設定なので、500円玉の数に注目して考える。つまり、500円玉を受け取ったら、+1枚、千円札を受け取ったらお釣りを渡すので、-1枚とカウントする。これをグラフ化すると下の図のようになる。

　このグラフでは500円玉の数がマイナスになっているので、お釣りがない状態になっている。確認しておくと、総組み合わせ数－釣銭がマイナスになる組み合わせ＝答えだ。12人から6人を選ぶ組み合わせ総数は、


これを計算すると(924)
これから、釣銭がマイナスになる組み合わせを引けばよい。

中村センセの「美しき数学の時間」では、はじめて500円玉の数がマイナス（-1)になったとき、y=-1の線に沿ってグラフを折り返す(上下反転させる)方法が紹介された。あまり説明がされなかったが、どの段階で500円玉が(-1)になっても、そのグラフを、y=-1の線で上下反転させると、(0,-2)から(12,0)のグラフと1対1で対応する。元のグラフのスタート地点は(0,0)なので、それを、y=-1の線で折れば、スタート地点が(0,-2)になるのは、当たり前ちゃ、当たり前。で、グラフの下降(－方向）の線と上昇(＋方向）の線を数えてみれば、5と7になる。これも、y=-1に沿って折り返したので、6-1=5、6+1=7になるのは、当たり前ちゃ、当たり前だ。つまり、500円玉の数がマイナスになる組み合わせは、


計算すると(792)。ちなみに12個から5個を選ぶと残りは7個なので、12個から7個を選んでも同じ(792）になる。
先ほどの総数(924)から、マイナスになる組み合わせ数(792)を引くと、答えは(132)通り。

　今回、マス北野には、助っ人として、ベナン共和国出身の留学生、ポヌさんが加わった。マス北野によると、ゾマホンのお友達ということだが、たぶん、ゾマホンの設立したNPO法人IFEを通じて、国際交流プログラムの一環として、日本に留学しているんじゃないかと思う。

　コマ大生は、問題の客の数が12人ということから、セ・リーグとパ・リーグに分かれて、いつものように身をもって検証。答えは「132通り」となった。

　マス北野は、枝分かれ図のように組み合わせを描いていき、なんとかパターンを見つけようとしたが、答えは、オレ「116」、ポヌ「132」(どうやら、コマ大生の答えを見て、マス北野が勝手に書いたようだ＾＾；）

　東大生は500円を「○」、1000円を「×」として、組み合わせを場合分けして考えたが、タイムアウトでギブアップ。答えは「80通り(以上)」となった。

　そんなわけで、今回のコマネチ・フィールズ賞はコマ大生が獲得。

　ところで今回の問題は、「コマネチ大学数学科29講：カタラン数」に出てくる公式を知っていれば、公式に当てはめるだけで簡単に答えが出てしまう。
・2n人が交差することなく握手する方法の数
・(n+2)角形を内部で交わらない対角線で三角形に分割する方法の数


また、コマ大生がセ・リーグとパ・リーグに分けて「セセセパパパセセセパパパ」としたように、東大生が「○×」の並びで考えたように、以下の問題も応用できる。
・n組のかっこの正しいつけ方
・n個ある数の掛け算の順序