目的
引き分けを許す $k$ 回総当たり戦を $n$ チームで行ったとき、その結果に表れる勝敗パターンと勝ち点パターンを列挙したい。
前回は $k=1$ の場合を調べたことになり、その一般化を行う。
e10s.hateblo.jp
用語
勝敗パターンを表す構造をグラフにより定義したい。トーナメントを拡張した概念を用いることにする。前回の定義も参照。
en.wikipedia.org
mathworld.wolfram.com
- 部分トーナメント
- 単純な無向グラフのすべての辺を任意の向きの有向辺にしたグラフであり、同じことだが、任意の頂点間の辺は高々 1 本である単純な有向グラフのことを部分トーナメントと呼ぶ。前回は向き付けされたグラフと呼んだ。
- トーナメント
- 任意の頂点間に向きを問わず辺が存在する部分トーナメントをトーナメントと呼ぶ。
- 部分重み付きトーナメント
- $k$ を非負の整数とする。頂点集合 $V$ と重み関数 $w: V \times V \to \qty{0,1,\dots,k}$ および、$$E \triangleq \qty{(u,v) \in V \times V \mid u \neq v \land w(u,v) + w(v,u) \leq k \land w(u,v)>0}$$ で定義される辺集合からなる単純な辺重み付き有向グラフ $(V, E, w)$ を部分 $k$-重み付きトーナメントと呼ぶ。
部分 $1$-重み付きトーナメント $(V, E, w)$ の辺の重みはすべて $1$ であり、部分トーナメント $(V, E)$ と同一視できる。
また、$k'>k$ であるとき、部分 $k$-重み付きトーナメントは部分 $k'$-重み付きトーナメントでもある。
これはこの論文の定義を参考にした。
www.jair.org
そして、勝ち点パターンを表す勝ち点列を定義する。
- 勝ち点列
- 部分 $k$-重み付きトーナメント $(V, E, w)$ と適当な数 $p_+, p_\pm, p_-$ について、各頂点 $u$ に対して、$$\begin{align} q_u &\triangleq \sum_{v \in V, v \neq u} ( p_+ w(u, v) + p_- w(v, u) + p_\pm \qty{ k - w(u, v) - w(v, u) } ) \\ &= k (\abs{V} - 1) p_\pm + \sum_{v \in V, v \neq u} \qty{ (p_+ - p_\pm) w(u, v) + (p_- - p_\pm) w(v, u) } \end{align}$$で定める $q_u$ を頂点 $u$ の $(k; p_+, p_\pm, p_-)$-勝ち点と呼び、それらを大きい順で並べた列をそのグラフの $(k; p_+, p_\pm, p_-)$-勝ち点列と呼ぶ。
勝ち点列はグラフの隣接行列を用いても計算できる。$A$ を隣接行列、$\vb*{1}$ を成分がすべて $1$ の $\abs{V}$ 次元列ベクトル、$I$ を単位行列、$\bar{I}$ を対角成分が $0$ でそれ以外が $1$ の $\abs{V}$ 次正方行列とし、$$
\begin{align}
\vb*{q} &= p_+ A \vb*{1} + p_- A^\top \vb*{1} + p_\pm (k \bar{I} - A - A^\top) \vb*{1} \\
&= \{ k p_\pm \bar{I} + (p_+ - p_\pm) A + (p_- - p_\pm) A^\top \} \vb*{1} \\
&= \{ (k (\abs{V} - 1) p_\pm I + (p_+ - p_\pm) A + (p_- - p_\pm) A^\top \} \vb*{1}
\end{align}
$$で得られる列ベクトル $\vb*{q}$ は各行が隣接行列における同じ行に対応する頂点の $(k; p_+, p_\pm, p_-)$-勝ち点である。よって、その成分を並び替えることで $(k; p_+, p_\pm, p_-)$-勝ち点列が求められる。
方法
勝敗パターンとグラフ
引き分けを許す $n$ チーム $k$ 回総当たり戦の勝敗パターンを $n$ 頂点ラベルなし部分 $k$-重み付きトーナメント $T_{n,k} = (V, E, w)$ により表すことにする。また、それら全体の集合を $\mathcal{T}_{n,k}$ と表すことにし、これを求めたい。
$T_{n,k}$ の $n$ 個の頂点をそれぞれ各チームと対応付け、ある 2 チーム $t_u, t_v$ に対応する頂点をそれぞれ $u, v$ とおく。$t_u$ が $t_v$ に対して $w_{u, v}$ 勝したとき、重み $w(u, v)$ を $w_{u, v}$ と定めることにする。
注意すべきは、このグラフには引き分けの数は明示されない。しかし、ある 2 チーム $t_u$ と $t_v$ の間の $k$ 回の対戦において、$t_u$ の $w_{u, v}$ 勝、$t_v$ の $w_{v, u}$ 勝であった場合、その両者の対戦において引き分けは $k-(w_{u, v}+w_{v, u})$ 回あることがわかる。ゆえに、$T_{n,k}$ をもってチーム数、対戦回数、勝ち・引き分け・負けの数をすべて表すデータたりうる。
勝ち点パターンとグラフ
上述の長々とした議論より、勝ち・引き分け・負けにそれぞれ勝ち点 $p_+, p_\pm, p_-$ を定めれば、その $k$ 回総当たり戦の結果として現れる勝ち点パターンが計算できる。そしてそれは対応するグラフの $(k; p_+, p_\pm, p_-)$-勝ち点列で表される。$\mathcal{T}_{n,k}$ の各元から得られる $k$-勝ち点列をすべて求めたい。
具体例
4 チーム 1 回総当たり戦の結果として次の組み合わせ表が得られたとする。便宜上チームに番号を割り当て、勝利・引き分け・敗北の数を順にハイフンで繋いで表記することにする。勝ち点は一般的なサッカー形式で、$(p_+, p_\pm, p_)=(3,1,0)$ とする。
| 0 | 1 | 2 | 3 | 計 | 勝ち点 | |
|---|---|---|---|---|---|---|
| 0 | ＼ | 1-0-0 | 0-1-0 | 1-0-0 | 2-1-0 | 7 |
| 1 | 0-0-1 | ＼ | 1-0-0 | 1-0-0 | 2-0-1 | 6 |
| 2 | 0-1-0 | 0-0-1 | ＼ | 0-1-0 | 0-2-1 | 2 |
| 3 | 0-0-1 | 0-0-1 | 0-1-0 | ＼ | 0-1-2 | 1 |
これに対応するグラフは次のようになり、$(1;3,1,0)$-勝ち点列は $(7,6,2,1)$ である。
別のグラフを挙げる。
このグラフを 3 回総当たり戦の結果としてみれば、次の組み合わせ表に対応し、$(3;3,1,0)$-勝ち点列は $(16,12,8,8)$ である。
| 0 | 1 | 2 | 3 | 計 | 勝ち点 | |
|---|---|---|---|---|---|---|
| 0 | ＼ | 3-0-0 | 0-3-0 | 1-1-1 | 4-4-1 | 16 |
| 1 | 0-0-3 | ＼ | 1-2-0 | 2-1-0 | 3-3-3 | 12 |
| 2 | 0-3-0 | 0-2-1 | ＼ | 0-3-0 | 0-8-1 | 8 |
| 3 | 1-1-1 | 0-1-2 | 0-3-0 | ＼ | 1-5-3 | 8 |
また、同じグラフを 4 回総当たり戦の結果としてみれば、各対戦において引き分けが 1 試合ずつ増え、すなわち各チームについて引き分けが 3 試合ずつ増えることになるので、次の組み合わせ表に対応し、$(4;3,1,0)$-勝ち点列は $(19,15,11,11)$ である。
| 0 | 1 | 2 | 3 | 計 | 勝ち点 | |
|---|---|---|---|---|---|---|
| 0 | ＼ | 3-1-0 | 0-4-0 | 1-2-1 | 4-7-1 | 19 |
| 1 | 0-1-3 | ＼ | 1-3-0 | 2-2-0 | 3-6-3 | 15 |
| 2 | 0-4-4 | 0-3-1 | ＼ | 0-4-0 | 0-11-1 | 11 |
| 3 | 1-2-1 | 0-2-2 | 0-4-0 | ＼ | 1-8-3 | 11 |
パターン数
汎用的な列挙プログラムを書いたが、長いので載せない。タイトル詐欺である。勝ち点パターン数は一般的なサッカー形式のみ載せる。
$k=1$ のとき
| n | 勝敗パターン | 勝ち点パターン |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 7 | 7 |
| 4 | 42 | 40 |
| 5 | 582 | 355 |
| 6 | 21480 | 3678 |
$k=2$ のとき
| n | 勝敗パターン | 勝ち点パターン |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 4 | 4 |
| 3 | 44 | 40 |
| 4 | 2085 | 748 |
| 5 | 512562 | 13744 |
$k=3$ のとき
| n | 勝敗パターン | 勝ち点パターン |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 6 | 6 |
| 3 | 180 | 140 |
| 4 | 42255 | 4014 |
$k=4$ のとき
| n | 勝敗パターン | 勝ち点パターン |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 9 | 9 |
| 3 | 590 | 348 |
| 4 | 477480 | 12903 |
そして、$n$ チーム 1 回総当たり戦における勝敗パターンの数は OEIS にある。
1 回総当たり戦と 2 回総当たり戦における勝ち点パターンの数についても OEIS にある。一般的なサッカー形式で、$p_+=3, p_\pm=1, p_-=0$ である。
こちらは一般的なチェス形式で、$p_+=1, p_\pm=0.5, p_-=0$ である。
〆
前回は 2022 年のワールドカップ時期に書いたのだが、この記事はその直後に書きはじめ、リファインを重ねていた。今や 2024 年のアジアカップが終わってしまった。
組合せ爆発がひどいので、この先はすごいアルゴリズムかすごいコンピュータがないと計算する気にならない。
