トーナメントひいき問題

http://www.kmonos.net/wlog/53.php#_0036050910
の、トーナメントひいき問題。
総当たりよりはマシそうな方法が思いついたので一応書いておく。

勝たせたい人を頂点に、木を作る。子の条件は：

1. 親に負ける
2. 直径の祖先に含まれない

の二つ。で、優勝者が戦う試合数の数の世代しか作らない。
で、作った木の中からトーナメントを作れるようなものを選び出せばよい。

……木を作るだけで指数的な時間がかかりそう。まあでも、実装してみるつもりである。

それはともかく。
「本質的に違うトーナメント表の正確な総数」は、簡単である*1。
そうなる理由は省略して、結果だけ書くと：
　P=2ⁿ人の場合の「本質的に違うトーナメント表の正確な総数」x は、x = P!/( 2^P-1 )
である。
計算すると：

n = 1, P = 2, x = 1
n = 2, P = 4, x = 3
n = 3, P = 8, x = 315
n = 4, P = 16, x = 638512875
n = 5, P = 32, x = 1.23e+026
n = 6, P = 64, x = 1.38e+070
n = 7, P = 128, x = 2.27e+177

となる。
8人までのトーナメントなら余裕で総当たり可能。16人のトーナメントは、6億通り余り。かなり厳しい。
その先は、総当たりは絶対無理。

というわけで、探索プログラムを書こうかとも思っていたんだが、今日はもう寝るのでやめ。週末にでも書こうかしらん。

*1:高校の数学の時間に解いた憶えがある