第314問の解答
問題 [場合の数]
ある将棋大会の決勝トーナメント表を作ろうと思います。決勝トーナメント出場者はマサルさん、トモエさん、マサヒコ君、ツヨシ君、サトルさん、ノブユキ君の6人です。 このとき、異なるトーナメント表(*)は何通り作ることができるでしょうか。
(*)異なるトーナメント表とは、見た目だけでなく試合の対戦が異なるものをさします。
解答例1
あんみつさん、Nonさん、CRYING DOLPHINさん、Taroさん、ICさん、Nobさん、Banyanyanさん、小西孝一さん 、M.Hossieさん、ふじさきたつみさん、まるケンさん、拓パパさん、POPPYさん、有無相生さん、ステップ ばい ステップさん、はっち〜さん、トトロ@Nさん、他 多数
トーナメント表の形によって場合分けします。
6人の対戦では、対称的なものを除いて下記の6通りになります。
・A,Bへ配置するのに6C2=15通り
・C,Dへ配置するのに4C2=6通り
・E,Fは残りの2人が自動的に決まる
・このうち、ABとCDの対戦は対称的なので重複
よって、15×6÷2=45通り・A,Bへ配置するのに6C2=15通り
・C,Dへ配置するのに4C2=6通り
・Eへ配置するのに2C1=2通り
・Fへは残り1人が自動的に決まる
よって、15×6×2=180通り・A,Bへ配置するのに6C2=15通り
・C,Dへ配置するのに4C2=6通り
・Eへ配置するのに2C1=2通り
・Fへは残り1人が自動的に決まる
・このうち、ABとCDの対戦は対称的なので重複
よって、15×6×2÷2=90通りケース4と同様、15×6×2=180通り ・Aへ配置するのに6C1=6通り
・B,Cへ配置するのに5C2=10通り
・D,Eへ配置するのに3C2=3通り
・Fへは残り1人が自動的に決まる
・このうち、ABCとDEFの対戦は対称的なので重複
よって、6×10×3÷2=90通り・A,Bへ配置するのに6C2=15通り
・Cへ配置するのに4C1=4通り
・Dへ配置するのに3C1=3通り
・Eへ配置するのに2C1=2通り
・Fへは残り1人が自動的に決まる
よって、15×4×3×2=360通り従って、合計=45+90+90+180+180+360=945通りとなります。
答: 945通り
以上
解答例2
マサルさん、高田修成さん、Nonさん、中村明海さん、POPPYさん、kokoさん、 他
漸化式で考えます。n人の場合の組み合わせをTn通りとします。
まず、2人の場合、T2=1通り。
次に、n人から(n+1)人に増えるときを考えます。
n人の場合、よく知られたように、試合数=n-1となります。
従って、あるトーナメントの組み合わせ結果に対し、もう1試合を追加できる場所は、
各試合につき2通りと決勝戦後の1通り=(n-1)×2+1=2n-1個所。従って、Tn+1=Tn×(2n-1)が成り立ちます。
従って、Tn=(2n-3)×(2n-5)×・・・×3×1となり、
とくに、Tn=9×7×5×3×1=945通りとなります。
解答例3
高橋 道広さん、Banyanyanさん、ステップ ばい ステップさん、Banyanyanさん、トトロ@Nさん、他
まず、トーナメント表数の一般式(Snとします)を考えます。
ただし、対称的なものも除かずに数えることにします。
トーナメント表を、カッコでくくったのと考えてみると、n人の場合、試合数は(n-1)なので、
カッコ の個数も(n-1)個となります。すると、よく知られたように、このときの場合の数は(n-1)次のカタラン数となります。
(算チャレ:248、226、180、算チャレ2:091、数学の小部屋:006)
よって、Sn=Kn-1=2n-2Cn-1/n1つのトーナメント表に対し、n人の試合をする場所を決める方法は、n!通りあるので、
合計でSn×n!=2n-2Cn-1×(n-1)!通りとなります。これらのうち、各試合の対戦相手は互いに対称的なので2倍に数えていることになります。
従って、重複分を除くと、
Tn=Sn×n!/2n-1
=2n-2Cn-1×(n-1)!/2n-1
=(2n-2)!/((n-1)!×(n-1)!)×(n-1)!/2n-1
=(2n-2)!/((n-1)!×2n-1)
=(2n-2)×(2n-3)×(2n-4)×(2n-5)×・・・×2×1/(2n-2)×(2n-4)×・・・×4×2
=(2n-3)×(2n-5)×・・・×3×1
となります。よって、Tn=9×7×5×3×1=945通りとなります。