ヨーキョクデイ

100% pure impurities, which may imply some value. (j は虚数単位)

引き分けを許す複数回総当たり戦の勝敗パターンと勝ち点パターンの列挙

目的

引き分けを許す $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)$ と同一視できる。

部分トーナメントと部分 1-重み付きトーナメントの例

また、$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)$ である。

4 チームによる総当たり戦の結果の例 1

別のグラフを挙げる。

4 チームによる総当たり戦の結果の例 2

このグラフを 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 年のアジアカップが終わってしまった。

組合せ爆発がひどいので、この先はすごいアルゴリズムかすごいコンピュータがないと計算する気にならない。

電源換装

8 年選手になったマシンの電源ユニットも当然 8 年選手であって、いよいよ問題も生じてきたのであり、交換することにした。
e10s.hateblo.jp

スタンバイ電圧は出ているが、パソコン本体の電源ボタンを押しても電源が入らないことが多くなり、そのときは電源ユニット側のスイッチを入れ直すと勝手に起動する確率が高いという症状で、それがマザーボードの設定で電源ユニットのオフ→オンで起動する設定にしていなくても発動するという謎現象。不健全なのでその設定を有効にした上で電源ユニットのスイッチを入れ直すことで起動する運用をしていたが、何度かそのスイッチをカチカチしないといけないときもあった。

中途半端に原因の切り分けをしたが、電源ユニット自体が問題ではないとしても、さすがに延命しすぎだろうから新調した次第。新しい電源は玄人志向の KRPW-BK650W/85+ という 650W モノ。現状でも 450W モノをもてあましているが、安かったので。
www.kuroutoshikou.com

HDD もそろそろ危ないよなぁ。

n 回目に初めてビンゴする確率

ヨビノリの動画で $n$ 回目に初めてビンゴする確率について触れていたので、コンピュータのパワーで計算してみようと思った。
www.youtube.com

復習

ありがちな高校数学の問題。

問 1

赤玉が $R$ 個、緑玉が $G$ 個、青玉が $B$ 個あり、これらはすべて区別できる。

(1)

玉を $k$ 個を選ぶ選び方の総数は?

(2)

赤玉、緑玉、青玉をそれぞれ $r,g,b$ 選ぶ選び方の総数は?

答 1

(1)

$R+G+B$ 個の玉から $k$ 個選ぶ場合の数であるから、$\binom{R+G+B}{k}$。

(2)
  • 赤玉について、$R$ 個から $r$ 個選ぶ場合の数は $\binom{R}{r}$
  • 緑玉について、$G$ 個から $g$ 個選ぶ場合の数は $\binom{G}{g}$
  • 青玉について、$B$ 個から $b$ 個選ぶ場合の数は $\binom{B}{b}$

求める総数はそれらの積で、$\binom{R}{r} \binom{G}{g} \binom{B}{b}$。

特定の盤面を得る確率

問 2

縦横 $5$ マスずつからなるビンゴカードがある。中央のマスは FREE であり穴があらかじめ開けてある。このビンゴカードの FREE 以外のマスには下の図のように数が割り振られている。

1 2 3 4 5
6 7 8 9 10
11 12 FREE 14 15
16 17 18 19 20
21 22 23 24 25

さて、$1$ から $75$ までの数が書かれたボールを重複なくランダムに引いてゆき、引いたボールに書かれた数が割り振られたマスがビンゴカードにあればそのマスを開けることを $10$ 回繰り返す。

(1)

引かれたボールの組合せの総数は?

(2)

結果として新たに $1,2,3$ のマスにのみ穴が開くときに引かれたボールの組合せの総数は?

(3)

結果として新たに $1,2,3$ のマスにのみ穴が開く確率は?

答 2

前述の問 1 と同じ考え方で解ける。

(1)

$75$ 個のボールから引くボールを $10$ 個選ぶ場合の数であるから、$\binom{75}{10}=828931106355$。

(2)

ボールについて $(1,2,3),(4,\dots,12,14,\dots,25),(26,\dots,75,13)$ がそれぞれ書かれたボールの組はそれぞれ、

  • 引くと狙ったマスに穴を開けられるボールの組(甲)
  • 引くと狙ったマス以外のマスに穴を開けられるボールの組(乙)
  • カードにない数の書かれたボールの組(丙)

に対応する。

  • (甲)について、$3$ 個のボールから $3$ 個選ぶ場合の数は $\binom{3}{3}=1$
  • (乙)について、$21$ 個から $0$ 個選ぶ場合の数は $\binom{21}{0}=1$
  • (丙)について、$51$ 個から $10-3-0=7$ 個選ぶ場合の数は $\binom{51}{7}=115775100$

求める総数はそれらの積で、$\binom{3}{3} \binom{21}{0} \binom{51}{7}=\binom{51}{7}=115775100$。

(3)

(1)(2) より、$\binom{51}{7} / \binom{75}{10} = 115775100/828931106355 = 19740/141335227$。

補題

縦横 $M$ マスずつからなるビンゴカードがある。FREE マスが適当な箇所に $f$ 個あり、穴があらかじめ開けてある。$N$ 個のボールを重複なくランダムに引いてゆき、引いたボールに書かれた数に対応するマスがビンゴカードにあればそのマスを開けることを $n$ 回繰り返すとき、新たに特定の $m$ マスにのみ穴が開く確率を $p(M,f;N;n,m)$ とすると、$$p(M,f;N;n,m) = \frac{ \binom{N-(M^2-f)}{n-m} }{ \binom{N}{n} }$$である。

これは問 2 と同様に考えることで導ける。

リーチ盤面から考える

n-1 回目に特定のリーチ状態である確率

上記の補題と同様のビンゴカードとボールを考える。$n-1$ 回ボールを引いたとき、新たに特定の $m$ マスにのみ穴が開く確率は、補題より、$$
p(M,f;N;n-1,m) = \frac{ \binom{N-(M^2-f)}{(n-1)-m} }{ \binom{N}{n-1} }$$である。

さて、このとき、ビンゴが完成したラインが存在せず、かつリーチ状態であるとする。$n-1$ 回目で初めてリーチしたとは限らないことに注意。そして $n$ 回目に引いたボールによってビンゴが完成するようなボールが $k$ 個あるとする。

例として、下に示す $M=5,f=2$ の珍奇なビンゴカードを考える。$n-1$ 回ボールを引いたとき、○で示した $m=9$ マスに穴が開いていた。

F
F

$n$ 回目引いたボールによって☆で示した $k=2$ マスのいずれかに穴が開けば斜めビンゴか縦ビンゴが完成する。

n-1 回目に特定のリーチ状態であるとき n 回目にビンゴが完成する確率

このような $n-1$ 回で特定のリーチ状態であるとき、ビンゴが完成するようなボールを $n$ 回目に引く確率は $k/\qty[ N-(n-1) ]$ であるから、そのようなリーチ状態から $n$ 回目に初めてビンゴが完成する確率は、$$
p(M,f;N;n-1,m) \frac{k}{N-(n-1)} = \frac{ \binom{N-(M^2-f)}{(n-1)-m} }{ \binom{N}{n-1} } \frac{k}{N-(n-1)}$$となる。

確率分布

n 回目にビンゴが完成する確率

前述の議論より。

ボールの数を $N$ とする。縦横 $M$ マス、FREE マスが $f$ 個あるビンゴカードを考える。このカードにおいて $n-1$ 回ボールを引いたときに実現しうる、ビンゴが完成したラインが存在せず、かつリーチ状態である盤面全体の集合を $S$ とする。そのような任意の盤面 $s \in S$ について、FREE マス以外の穴の数を $m_s$ とし、$n$ 回目にボールを引いたときにビンゴが完成するようなボールが $k_s$ 個あるとする。このとき、$n$ 回目にボールを引いたときにビンゴが完成する確率は、$$
\sum_{s \in S} p(M,f;N;n-1,m_s) \frac{k_s}{N-(n-1)} = \sum_{s \in S} \frac{ \binom{N-(M^2-f)}{(n-1)-m_s} }{ \binom{N}{n-1} } \frac{k_s}{N-(n-1)}$$となる。

数値計算

とはいえ、そのようなリーチ状態を組合せ論的に列挙するのは非常にやりたくないので、コンピュータによって列挙することにし、その上で具体的な確率分布を算出した。小数第 12 位まで。FREE マスは存在するならば中央に 1 個だけある想定で。

以下に $n$ 回目で初めてビンゴが完成する確率とその累積である $n$ 回目までにビンゴが完成する確率の一覧表を挙げる。

3×3 マス、FREE あり、ボール 45 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.004040404040 0.004040404040
3 0.008362696735 0.012403100775
4 0.012846068660 0.025249169435
5 0.017376258329 0.042625427764
6 0.021847025477 0.064472453242
7 0.026161359911 0.090633813152
8 0.030232439839 0.120866252992
9 0.033984353607 0.154850606599
10 0.037352598740 0.192203205339
11 0.040284372231 0.232487577569
12 0.042738665971 0.275226243540
13 0.044686181260 0.319912424799
14 0.046109076297 0.366021501096
15 0.047000560581 0.413022061677
16 0.047364350132 0.460386411809
17 0.047213997454 0.507600409263
18 0.046572110160 0.554172519423
19 0.045469472164 0.599641991588
20 0.043944081380 0.643586072968
21 0.042040117820 0.685626190788
22 0.039806856029 0.725433046817
23 0.037297535766 0.762730582583
24 0.034568204846 0.797298787429
25 0.031676548069 0.828975335498
26 0.028680716145 0.857656051644
27 0.025638168541 0.883294220184
28 0.022604544156 0.905898764340
29 0.019632573760 0.925531338100
30 0.016771048093 0.942302386193
31 0.014063855560 0.956366241753
32 0.011549103426 0.967915345179
33 0.009258336440 0.977173681619
34 0.007215866797 0.984389548416
35 0.005438229363 0.989827777779
36 0.003933776069 0.993761553848
37 0.002702423409 0.996463977256
38 0.001735566944 0.998199544201
39 0.001016176739 0.999215720940
40 0.000519087643 0.999734808583
41 0.000211498340 0.999946306923
42 0.000053693077 1.000000000000
43 0.000000000000 1.000000000000
44 0.000000000000 1.000000000000
45 0.000000000000 1.000000000000
3×3 マス、FREE なし、ボール 45 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.000000000000 0.000000000000
3 0.000563777308 0.000563777308
4 0.001691331924 0.002255109232
5 0.003364657023 0.005619766255
6 0.005548966695 0.011168732950
7 0.008194320333 0.019363053283
8 0.011237564815 0.030600618098
9 0.014604520118 0.045205138216
10 0.018212338522 0.063417476738
11 0.021971972087 0.085389448825
12 0.025790687593 0.111180136418
13 0.029574572632 0.140754709050
14 0.033230981080 0.173985690130
15 0.036670870677 0.210656560807
16 0.039810989956 0.250467550763
17 0.042575876280 0.293043427043
18 0.044899631263 0.337943058306
19 0.046727444345 0.384670502651
20 0.048016839849 0.432687342500
21 0.048738627298 0.481425969798
22 0.048877539348 0.530303509146
23 0.048432546164 0.578736055310
24 0.047416839589 0.626152894899
25 0.045857484995 0.672010379895
26 0.043794743171 0.715805123065
27 0.041281069164 0.757086192230
28 0.038379799481 0.795465991710
29 0.035163543561 0.830629535272
30 0.031712299978 0.862341835250
31 0.028111322302 0.890453157552
32 0.024448764103 0.914901921655
33 0.020813137068 0.935715058723
34 0.017290620724 0.953005679447
35 0.013962266773 0.966967946220
36 0.010901145570 0.977869091790
37 0.008169486762 0.986038578551
38 0.005815870649 0.991854449200
39 0.003872531326 0.995726980526
40 0.002352837180 0.998079817705
41 0.001249018833 0.999328836538
42 0.000530219135 0.999859055673
43 0.000140944327 1.000000000000
44 0.000000000000 1.000000000000
45 0.000000000000 1.000000000000
5×5 マス、FREE あり、ボール 75 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.000000000000 0.000000000000
3 0.000000000000 0.000000000000
4 0.000003290962 0.000003290962
5 0.000013627365 0.000016918327
6 0.000035227201 0.000052145528
7 0.000072771981 0.000124917509
8 0.000131404952 0.000256322460
9 0.000216725572 0.000473048033
10 0.000334778066 0.000807826099
11 0.000492031665 0.001299857764
12 0.000695349959 0.001995207722
13 0.000951946596 0.002947154319
14 0.001269324440 0.004216478759
15 0.001655195257 0.005871674016
16 0.002117377057 0.007989051072
17 0.002663666417 0.010652717489
18 0.003301683470 0.013954400960
19 0.004038687833 0.017993088793
20 0.004881364553 0.022874453346
21 0.005835580218 0.028710033564
22 0.006906110718 0.035616144282
23 0.008096343748 0.043712488030
24 0.009407961019 0.053120449050
25 0.010840607219 0.063961056269
26 0.012391555002 0.076352611271
27 0.014055377606 0.090407988876
28 0.015823642977 0.106231631854
29 0.017684645381 0.123916277235
30 0.019623192253 0.143539469488
31 0.021620465339 0.165159934827
32 0.023653975732 0.188813910559
33 0.025697632150 0.214511542708
34 0.027721940422 0.242233483130
35 0.029694349642 0.271927832772
36 0.031579756534 0.303507589307
37 0.033341174341 0.336848763647
38 0.034940565920 0.371789329568
39 0.036339832819 0.408129162387
40 0.037501943118 0.445631105504
41 0.038392171080 0.484023276584
42 0.038979411523 0.523002688107
43 0.039237521875 0.562240209982
44 0.039146635724 0.601386845706
45 0.038694384054 0.640081229761
46 0.037876954948 0.677958184709
47 0.036699920280 0.714658104989
48 0.035178759369 0.749836864358
49 0.033339015516 0.783175879874
50 0.031216032218 0.814391912091
51 0.028854231898 0.843246143989
52 0.026305921190 0.869552065179
53 0.023629632664 0.893181697843
54 0.020888042611 0.914069740454
55 0.018145536595 0.932215277049
56 0.015465527271 0.947680804320
57 0.012907659890 0.960588464210
58 0.010525067351 0.971113531560
59 0.008361855459 0.979475387019
60 0.006451006931 0.985926393950
61 0.004812886624 0.990739280574
62 0.003454507638 0.994193788212
63 0.002369676574 0.996563464786
64 0.001540075598 0.998103540384
65 0.000937260353 0.999040800737
66 0.000525459574 0.999566260312
67 0.000264961019 0.999831221331
68 0.000115768584 0.999946989915
69 0.000041130838 0.999988120752
70 0.000010488700 0.999998609453
71 0.000001390547 1.000000000000
72 0.000000000000 1.000000000000
73 0.000000000000 1.000000000000
74 0.000000000000 1.000000000000
75 0.000000000000 1.000000000000
5×5 マス、FREE なし、ボール 75 個
n n 回目で初ビンゴの確率 n 回目までにビンゴする確率
1 0.000000000000 0.000000000000
2 0.000000000000 0.000000000000
3 0.000000000000 0.000000000000
4 0.000000000000 0.000000000000
5 0.000000695274 0.000000695274
6 0.000003476369 0.000004171642
7 0.000010429106 0.000014600748
8 0.000024334580 0.000038935327
9 0.000048668793 0.000087604120
10 0.000087601166 0.000175205287
11 0.000145990755 0.000321196041
12 0.000229378565 0.000550574606
13 0.000343973902 0.000894548508
14 0.000496632236 0.001391180744
15 0.000694821588 0.002086002332
16 0.000946574049 0.003032576382
17 0.001260418618 0.004292995000
18 0.001645291315 0.005938286315
19 0.002110418328 0.008048704642
20 0.002665168006 0.010713872649
21 0.003318867770 0.014032740418
22 0.004080582546 0.018113322964
23 0.004958852271 0.023072175235
24 0.005961387262 0.029033562497
25 0.007094722017 0.036128284514
26 0.008363830172 0.044492114686
27 0.009771705995 0.054263820681
28 0.011318920863 0.065582741544
29 0.013003166567 0.078585908110
30 0.014818800955 0.093404709066
31 0.016756415165 0.110161124231
32 0.018802445262 0.128963569493
33 0.020938854369 0.149902423862
34 0.023142913848 0.173045337710
35 0.025387113669 0.198432451379
36 0.027639232205 0.226071683585
37 0.029862594205 0.255934277789
38 0.032016542087 0.287950819876
39 0.034057139899 0.322007959775
40 0.035938120995 0.357946080770
41 0.037612079735 0.395558160504
42 0.039031894419 0.434590054924
43 0.040152353517 0.474742408441
44 0.040931940613 0.515674349054
45 0.041334716138 0.557009065192
46 0.041332216861 0.598341282053
47 0.040905278585 0.639246560637
48 0.040045674840 0.679292235477
49 0.038757456308 0.718049691785
50 0.037057873626 0.755107565411
51 0.034977771826 0.790085337237
52 0.032561359060 0.822646696297
53 0.029865276564 0.852511972861
54 0.026956931111 0.879468903972
55 0.023912095354 0.903380999326
56 0.020811833900 0.924192833226
57 0.017738871413 0.941931704639
58 0.014773579829 0.956705284468
59 0.011989820066 0.968695104535
60 0.009450923565 0.978146028100
61 0.007206133559 0.985352161659
62 0.005287837989 0.990639999647
63 0.003709907966 0.994349907613
64 0.002467401328 0.996817308942
65 0.001537795793 0.998355104735
66 0.000883779286 0.999238884020
67 0.000457450181 0.999696334202
68 0.000205577794 0.999901911995
69 0.000075362487 0.999977274482
70 0.000019944423 0.999997218905
71 0.000002781095 1.000000000000
72 0.000000000000 1.000000000000
73 0.000000000000 1.000000000000
74 0.000000000000 1.000000000000
75 0.000000000000 1.000000000000

シミュレーション

より一般的な 5×5 マス、FREE あり、ボール 75 個の場合について、モンテカルロ法を使ってビンゴするまでボールを引き続けるシミュレーションを 10 万回した結果と理論値を比較したグラフを示す。横軸がボールを引く回数、縦軸がそこで初めてビンゴする確率である。

青い点がシミュレーション結果、赤い点が理論値であるが、どうだろう。

参考

無線ルータ新調

15 年選手の WZR-AGL300NH をもう引退させようという試みで、バッファローの WSR-3200AX4S を導入。11ax 対応機器はないのだが、先行投資だと思って。アクセスポイント 2 台体制は 5 年前の WSR-2533DHP 導入以来変わらずだが、今まで別にしていた SSID を揃えてみる試みが吉と出るか凶と出るか。

e10s.hateblo.jp
e10s.hateblo.jp

テレビのリモコンの効きが悪いので直した

もはや何年使っているかわからない東芝 REGZA のリモコン CT-90419 の電源ボタンだけ反応が悪くなり、いよいよ不便なので分解して修理することにした。幸いにも先人が修理動画を上げていたのでそれを参考にした。


www.youtube.com

www.youtube.com

ボタン裏の導電性ゴムの抵抗が何 MΩ オーダだったので、アルミホイルを両面テープでその部分に貼り付けることで修理完了。

調和数列の積の部分分数分解とシフト

濱中裕明先生の X のポストより。

それ部分分数分解で解けるよ案件なので。

調和数列の積の部分分数分解

再掲。

公式

非負整数 $n$ と複素数 $z$ について、次の等式が成り立つ。

$$\prod_{k=0}^{n} \frac{1}{z+k} = \frac{1}{n!} \sum_{k=0}^n (-1)^k \binom{n}{k}\frac{1}{z+k}$$

ただし、$z \neq 0, -1, -2, -3, \ldots, -n$。また、$\binom{n}{k}$ は二項係数。

シフト

$k$ を $n+1$ まで動かしてみる。このとき、$$\prod_{k=0}^{n+1} \frac{1}{z+k} = \qty[ \prod_{k=0}^n \frac{1}{z+k} ] \frac{1}{z+n+1}$$であり、また、$$\prod_{k=0}^{n+1} \frac{1}{z+k} = \frac{1}{z} \qty[ \prod_{k=1}^{n+1} \frac{1}{z+k} ] = \frac{1}{z} \qty[ \prod_{k=0}^n \frac{1}{z+k+1} ]$$である。

両者を比較して、
$$\prod_{k=0}^n \frac{1}{z+k} = \frac{z+n+1}{z} \prod_{k=0}^n \frac{1}{(z+1)+k}$$であり、部分分数分解の公式から、$$
\begin{align}
\sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{z+k}
&= \frac{z+(n+1)}{z} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{(z+1)+k} \\
&= \qty( 1+\frac{n+1}{z} ) \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{z+k+1}
\end{align}
$$となる。

また、$d \neq 0$ として、$z$ を $z/d$ で置き換えると、$$\sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{\frac{z}{d}+k} = \qty( 1+\frac{n+1}{\frac{z}{d}} ) \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{\frac{z}{d}+k+1}$$であり、両辺の分母に $d$ を掛けることにより、$$\sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{z+kd} = \qty( 1+\frac{(n+1)d}{z} ) \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{z+(k+1)d}$$を得る。

解答

件の問題については、$z=1, d=2$ の場合であり、$$\sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{2k+1} = (2n+3) \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{2k+3}$$となる。