3 年ぶりにマウス新調。ロジクールの M337 のチャタリングに耐えられなくなったので、同じくロジクールの M650 の赤をチョイスした。
e10s.hateblo.jp
Pioneer BDR-206JBK のトレイが開かなくなったので直した
11 年選手の BDR-206JBK だが、トレイを開けると勝手に閉まるという症状を 1 年ほど前に確認していたが、いよいよイジェクトしようとしても開かなくなり、イジェクトホールもなぜか効かないし、どうしたものかと思いつつも分解して修理することにした。
パイオニア製光学ドライブあるあるの症状のようで、先人達がノウハウを提供してくれているのでそれにならった。
- パイオニアのブルーレイを修理する～トレイが開かない問題の対処 | 創造の館
- BDドライブ（パイオニア BDR-206JBK)の修理 | bnr3293のブログ
- パイオニア製ブルーレイディスクが開かない！DIYで直してみました│じょーいちろぐ
- ＴＭＡＸ & おっさんの適当生活！ｗ Blu-rayドライブ2台同時故障 修理費220円
磁石を受ける部分にドーナツ型のパンチ穴補強シールを貼ればよいということだったが、そんなものはないので 3M の普通の黄色いマスキングテープを小さく切って 2 枚をポッチを挟んで貼った。そしてギアにタミヤのセラグリス HG を足しておいた。これで開閉機構を手動でガチャガチャと慣らした上で再度組み立てたところ、無事に復活したのでよかった。
翌日追記。なんやかんや、まだ不調。
オーディオ IF 新調
ここ何年も新調したいとは思っていたのだが、今まで 12 年も使っていた Roland の UA-1G パイセンの入力側の何かがいよいよ不調になったので。
www.roland.com
ここで、今回は Arturia というフランスの会社の MiniFuse 2 というのの白をチョイス。
www.arturia.com
引き分けを許す総当たり戦の勝敗パターンと勝ち点パターンの列挙
目的
引き分けを許す 1 回総当たり戦を $n$ チームで行ったとき、その結果に表れる勝敗パターンと勝ち点パターンを列挙したい。
サッカーのワールドカップが盛り上がっており、気になったので。
方法
勝敗パターンの列挙
1 回総当たり戦の結果をグラフにより表すことにする。グラフの頂点をチームと見なし、ある試合について勝ちチームから負けチームへと有向辺を 1 本だけ結ぶ。引き分けの場合は辺を結ばない。
これによって得られるグラフたちを全パターン列挙する。また、頂点のラベルを入れ替えても同型なグラフは区別しない。
用語と蛇足
- 向き付けされたグラフ
- 単純な無向グラフのすべての辺を任意の向きの有向辺にしたグラフであり、同じことだが、任意の頂点間の辺は高々 1 本である単純な有向グラフのことを向き付けされた (oriented) グラフと呼ぶ。定訳はないらしい。上記の作業で得られるグラフはこれ。
- トーナメント
- 任意の頂点間に向きを問わず辺が存在する向き付けされたグラフをトーナメントと呼ぶ。総当たり戦に引き分けがない場合に得られるグラフはこれ。 いわゆるトーナメント戦も総当たり戦も英語では tournament らしく、今は後者のことであるが、今回の話にトーナメントはとくに絡まない。
mathworld.wolfram.com
勝ち点パターンの列挙
勝敗パターンに対応する向き付けされたグラフにおいて、ある頂点の出次数と入次数は対応するチームのそれぞれ勝利数と敗北数に等しい。$n$ チームによる 1 回総当たり戦では各チームはいずれも $n-1$ 試合を行うことから、勝利・敗北・引き分けにそれぞれ勝ち点を割り振れば、その総当たり戦の結果として現れる勝ち点配分が計算できる。
具体例
4 チーム 1 回総当たり戦の結果として次の組み合わせ表が得られたとする。
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | ＼ | 勝 | 分 | 勝 |
| 1 | 負 | ＼ | 勝 | 勝 |
| 2 | 分 | 負 | ＼ | 分 |
| 3 | 負 | 負 | 分 | ＼ |
これに対応するグラフは次のようになる。
また、$ n$ チーム 1 回総当たり戦における勝敗パターンの数は OEIS にある。
勝ち点パターンについても OEIS にある。勝ち点については一般的なサッカー形式で、勝利・敗北・引き分けにそれぞれ 3、0、1 が割り振られたもの。
コード
SageMath で書いた。
関数たち。
def oriented_graphs(n): # OEIS: A001174 a = graphs.nauty_geng(str(n)) # Non-isomorphic simple undirected graphs with n vertices return digraphs.nauty_directg(a, options="-o") def point_allocation(graph, *, for_win=3, for_lose=0, for_draw=1): return tuple( sorted( ( for_draw * (graph.num_verts() - 1) + (for_lose - for_draw) * graph.in_degree(v) + (for_win - for_draw) * graph.out_degree(v) for v in graph.vertex_iterator() ), reverse=True, ) ) def by_point_allocation(graphs, *, for_win=3, for_lose=0, for_draw=1): # OEIS: A064626 a = dict() for g in graphs: b = point_allocation(g, for_win=for_win, for_lose=for_lose, for_draw=for_draw) a.setdefault(b, list()) a[b].append(g.copy(immutable=True)) return a
呼び出し例。3 チーム 1 回総当たりでの勝ち点パターンを列挙。
for g in oriented_graphs(3): print(point_allocation(g))
呼び出し結果。
(2, 2, 2) (4, 2, 1) (4, 4, 0) (4, 3, 1) (6, 1, 1) (6, 3, 0) (3, 3, 3)
呼び出し例。1～6 チーム 1 回総当たりでの勝ち点パターン of 勝敗パターン。
for n in range(1, 7): total = {"graph": 0, "alloc": 0} alloc_patterns = by_point_allocation(oriented_graphs(n)) for e in alloc_patterns.keys(): # print(e) for g in alloc_patterns[e]: total["graph"] += 1 # g.show(layout="circular") total["alloc"] += 1 print("%s: %s of %s" % (n, total["alloc"], total["graph"]))
呼び出し結果。
1: 1 of 1 2: 2 of 2 3: 7 of 7 4: 40 of 42 5: 355 of 582 6: 3678 of 21480
エレ解 2022.3 出題 1 を部分分数分解の公式で解く
問題
数学セミナー 2022 年 3 月号のエレガントな解答をもとむ、の出題 1。 解答は同 6 月号。
www.web-nippyo.jp
正の整数 $k$ について次の値を求めよ。
$$\sum^k_{j=0}(-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1}$$
というシンプルなもの。
解答
部分分数分解の公式より、$$\prod_{j=0}^n \frac{1}{z+j} = \frac{1}{n!} \sum_{j=0}^n (-1)^j \binom{n}{j} \frac{1}{z+j}$$が成り立ち、この両辺を $(-2)^{n+1}$ で割ると、$$\prod_{j=0}^n \frac{1}{-2(z+j)} = \frac{1}{(-2)^n n!} \sum_{j=0}^n (-1)^j \binom{n}{j} \frac{1}{-2(z+j)}$$である。これに $n = 2k+1,-2z = 2k+1$ を代入して、$$\prod_{j=0}^{2k+1} \frac{1}{2(k-j)+1} = \frac{1}{(-2)^{2k+1} (2k+1)!} \sum_{j=0}^{2k+1} (-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1}$$となる。つまり、$$\sum_{j=0}^{2k+1} (-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1} = (-2)^{2k+1} (2k+1)! \prod_{j=0}^{2k+1} \frac{1}{2(k-j)+1}$$である。
ここで、$$
\begin{align}
&\phantom{{}={}} \sum_{j=k+1}^{2k+1} (-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1} \\
&= \sum_{j=-k}^0 (-1)^{2k+1+j} \binom{2k+1}{2k+1+j} \frac{1}{2(k-(2k+1+j))+1} \\
&= \sum_{j=0}^k (-1)^{2k+1-j} \binom{2k+1}{2k+1-j} \frac{1}{2(k-(2k+1-j))+1} \\
&= \sum_{j=0}^k (-1)^{1-j} \binom{2k+1}{j} \frac{-1}{2(k-j)+1} \\
&= \sum_{j=0}^k (-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1}
\end{align}
$$が成り立つ。また、同様の変形により、$$
\begin{align}
&\phantom{{}={}} \prod_{j=k+1}^{2k+1} \frac{1}{2(k-j)+1} \\
&= \prod_{j=-k}^0 \frac{1}{2(k-(2k+1+j))+1} \\
&= \prod_{j=0}^k \frac{1}{2(k-(2k+1-j))+1} \\
&= \prod_{j=0}^k \frac{-1}{2(k-j)+1} \\
&= (-1)^{k+1} \prod_{j=0}^k \frac{1}{2(k-j)+1}
\end{align}
$$が成り立つ。さらに、$$
\begin{align}
&\phantom{{}={}} \prod_{j=0}^k \frac{1}{2(k-j)+1} \\
&= \frac{1}{(2k+1)!!} \\
&= \frac{2^k k!}{(2k+1)!}
\end{align}
$$
が成り立つ。
したがって、$$2\sum_{j=0}^k (-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1} = (-2)^{2k+1} (2k+1)! \cdot (-1)^{k+1} \qty[ \frac{2^k k!}{(2k+1)!} ]^2 $$となるから、これを整理して、$$\sum_{j=0}^k (-1)^j \binom{2k+1}{j} \frac{1}{2(k-j)+1} = \frac{(-16)^k (k!)^2}{(2k+1)!}$$となる。
〆
この問題に取り組んだせいで、今年の春から部分分数分解ネタにお熱なのだったという実。あの思い入れの強さと裏腹に実用性不明な公式の活用先を初めて見いだせたので、非常によかったという思い出。
二項係数の逆数の部分分数分解
Wikipedia に載っていたものの、証明がなかったので。
en.wikipedia.org
まず、二項係数を一般化して、複素数 $z$ と非負整数 $n$ について、$$
\begin{align}
\binom{z}{n}
&\triangleq \frac{z (z-1) \cdots (z-n+1)}{n!} \\
&= \frac{1}{n!} \prod_{k=0}^{n-1} (z-k)
\end{align}
$$と定義する。$z$ が $n$ 以上の整数であれば通常の二項係数と同じ。
ここで、$$
\begin{align}
\frac{1}{\binom{z}{n}}
&= n! \prod_{k=0}^{n-1} \frac{1}{z-k} \\
&= n! (-1)^n \prod_{k=0}^{n-1} \frac{1}{(-z)+k} \\
&= n! (-1)^n \cdot \frac{1}{(n-1)!} \sum_{k=0}^{n-1} (-1)^k \binom{n-1}{k} \frac{1}{(-z)+k} \\
&= n! (-1)^n \cdot \frac{1}{(n-1)!} \sum_{k=0}^{n-1} (-1)^{k-1} \frac{(n-1)!}{k! ((n-1)-k)!} \cdot \frac{1}{z-k} \\
&= \sum_{k=0}^{n-1} (-1)^{n+k-1} \frac{n! (n-k)}{k! (n-k)!} \cdot \frac{1}{z-k} \\
&= \sum_{k=0}^{n-1} (-1)^{n+k-1} \binom{n}{k} \frac{n-k}{z-k}
\end{align}
$$が成り立つ。
また、$$
\begin{align}
\frac{1}{\binom{z+n}{n}}
&= n! \prod_{k=0}^{n-1} \frac{1}{z+n-k} \\
&= n! \prod_{k=0}^{n-1} \frac{1}{(z+1)+k} \\
&= n! \cdot \frac{1}{(n-1)!} \sum_{k=0}^{n-1} (-1)^k \binom{n-1}{k} \frac{1}{(z+1)+k} \\
&= n! \cdot \frac{1}{(n-1)!} \sum_{k=0}^{n-1} (-1)^k \frac{(n-1)!}{k! ((n-1)-k)!} \cdot \frac{1}{z+k+1} \\
&= \sum_{k=0}^{n-1} (-1)^k \frac{n!}{k! ((n-1)-k)!} \cdot \frac{1}{z+k+1} \\
&= \sum_{k=1}^n (-1)^{k-1} \frac{n!}{(k-1)! (n-k)!} \cdot \frac{1}{z+k} \\
&= \sum_{k=1}^n (-1)^{k-1} \frac{n! k}{k! (n-k)!} \cdot \frac{1}{z+k} \\
&= \sum_{k=1}^n (-1)^{k-1} \binom{n}{k} \frac{k}{z+k}
\end{align}
$$が成り立つ。
いずれも、調和数列の積の部分分数分解の公式を用いた。
e10s.hateblo.jp
調和数列と多項式の積の部分分数分解（Melzak の公式）
以前に触れた Melzak の公式であるが、その証明をして、さらにいろいろな例に適応させる試み。
e10s.hateblo.jp
Melzak の公式
非負整数 $n$ と複素数 $w,z$ と高々 $n$ 次の多項式 $P(w)$ について、次の等式が成り立つ。
$$P(w+z) \prod_{k=0}^n \frac{1}{z+k} = \frac{1}{n!} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{P(w-k)}{z+k}$$
ただし $z$ は極を除く。また、$\binom{n}{k}$ は二項係数。
証明
以前の証明をなぞる。
左辺は、$z$ について分母が $n+1$ 次で分子が高々 $n$ 次であり、$$P(w+z) \prod_{k=0}^n \frac{1}{z+k} = \sum_{k=0}^n \frac{a_k}{z+k}$$と部分分数分解できるから、$k=m$ のときの係数 $a_m$ を求めればよい。この両辺に $z+m$ を掛けて、$z = -m$ とすることを考える。
右辺について、$$
\begin{align}
&\phantom{{}={}} \eval{ (z+m)\sum_{k=0}^n \frac{a_k}{z+k} }_{z=-m} \\
&= \eval{ \qty[ \sum_{k=0}^{m-1} \frac{a_k (z+m)}{z+k} + a_m + \sum_{k=m+1}^{n} \frac{a_k (z+m)}{z+k} ] }_{z=-m} \\
&= \sum_{k=0}^{m-1} \frac{a_k (-m+m)}{-m+k} + a_m + \sum_{k=m+1}^n \frac{a_k (-m+m)}{-m+k} \\
&= a_m
\end{align}
$$である。左辺について、$$
\begin{align}
&\phantom{{}={}} \eval{ (z+m) P(w+z) \prod_{k=0}^n \frac{1}{z+k} }_{z=-m} \\
&= \eval{ P(w+z) \qty[ \prod_{k=0}^{m-1} \frac{1}{z+k} ] \qty[ \prod_{k=m+1}^n \frac{1}{z+k} ] }_{z=-m} \\
&= P(w-m) \qty[ \prod_{k=0}^{m-1} \frac{1}{-m+k} ] \qty[ \prod_{k=m+1}^n \frac{1}{-m+k} ] \\
&= P(w-m) \qty[ (-1)^m \prod_{k=0}^{m-1} \frac{1}{m-k} ] \qty[ \prod_{k=1}^{n-m} \frac{1}{k} ] \\
&= P(w-m) \cdot (-1)^m \frac{1}{m!} \cdot \frac{1}{(n-m)!} \\
&= \frac{1}{n!} (-1)^{m} \binom{n}{m} P(w-m)
\end{align}
$$であるから、辺々を比較して、$$a_m = \frac{1}{n!} (-1)^{m} \binom{n}{m} P(w-m) $$ゆえ、示された。
系
とくに $w=0$ としたとき、$$P(z) \prod_{k=0}^n \frac{1}{z+k} = \frac{1}{n!} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{P(-k)}{z+k}$$が成り立つ。
系の具体例
調和数列の積
$$\prod_{k=0}^n \frac{1}{z+k} = \frac{1}{n!} \sum_{k=0}^n (-1)^k \binom{n}{k} \frac{1}{z+k}$$であるが、$P(w) \triangleq 1$ とすれば、$P(-k)=1$ ゆえ成り立つ。というのは以前にも言及した例である。
等差数列が分母・分子に交互に来る積
以前示したのと同じ流れであるが。
$$\qty[ \prod_{k=0}^{n-1} (z+2k+1) ] \qty[ \prod_{k=0}^n \frac{1}{z+2k} ] = \frac{1}{4^n} \sum_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} \frac{1}{z+2k}$$であるが、左辺の分母・分子を $2^{n+1}$ で割り、$\zeta \triangleq z/2$ とおくことで、$$
\begin{align}
\qty[ \prod_{k=0}^{n-1} (z+2k+1) ] \qty[ \prod_{k=0}^n \frac{1}{z+2k} ]
&= \qty[ \frac{1}{2} \prod_{k=0}^{n-1} \qty( \frac{z}{2}+\frac{2k+1}{2} ) ] \qty[ \prod_{k=0}^n \frac{1}{\frac{z}{2}+k} ] \\
&= \frac{1}{2} \qty[ \prod_{k=0}^{n-1} \qty( \zeta+\frac{2k+1}{2} ) ] \qty[ \prod_{k=0}^n \frac{1}{\zeta+k} ]
\end{align}
$$となる。ここで、$$P(w) \triangleq \prod_{i=0}^{n-1} \qty( w+\frac{2i+1}{2} )$$と定義して、$$\qty[ \prod_{k=0}^{n-1} (z+2k+1) ] \qty[ \prod_{k=0}^n \frac{1}{z+2k} ] = \frac{1}{2} P(\zeta) \prod_{k=0}^n \frac{1}{\zeta+k}$$を考えると、$$
\begin{align}
P(-k)
&= \prod_{i=0}^{n-1} \qty( -k+\frac{2i+1}{2} ) \\
&= \frac{1}{2^n} \prod_{i=0}^{n-1} (-2k+2i+1) \\
&= (-1)^k \frac{(2k)!(2(n-k))!}{4^n k!(n-k)!}
\end{align}
$$となり、$$
\begin{align}
\frac{1}{n!} (-1)^k \binom{n}{k} P(-k)
&= \frac{1}{n!} (-1)^k \binom{n}{k} \cdot (-1)^k \frac{(2k)!(2(n-k))!}{4^n k!(n-k)!} \\
&= \frac{1}{4^n} \binom{2k}{k} \binom{2(n-k)}{n-k}
\end{align}
$$であるから、$$
\frac{1}{2} P(\zeta) \qty[ \prod_{k=0}^n \frac{1}{\zeta+k} ]
= \frac{1}{2} \sum_{k=0}^n \frac{1}{4^n} \binom{2k}{k} \binom{2(n-k)}{n-k} \frac{1}{\zeta+k}
$$より、$$\qty[ \prod_{k=0}^{n-1} ( z+2k+1 ) ] \qty[ \prod_{k=0}^{n} \frac{1}{z+2k} ]
= \frac{1}{4^n} \sum_{k=0}^n \binom{2k}{k} \binom{2(n-k)}{n-k} \frac{1}{z+2k}$$となる。
調和数列の部分列の積
たとえば、$$\frac{1}{(z+1)(z+3)(z+4)} = \frac{1}{6(z+1)} - \frac{1}{2(z+3)} + \frac{1}{3(z+4)}$$であるが、少し遠回りして、$$\frac{1}{(z+1)(z+3)(z+4)} = z(z+2) \prod_{k=0}^4 \frac{1}{z+k}$$をいったん考えることにする。ここで、$$P(w) \triangleq w(w+2)$$とおくと、$P(0)=0, P(-1)=-1,P(-2)=0,P(-3)=3,P(-4)=8$ である。すると、$$
\begin{align}
z(z+2) \prod_{k=0}^4 \frac{1}{z+k}
&= \frac{1}{4!} \qty[ \frac{1 \cdot 0}{z} - \frac{4 \cdot (-1)}{z+1} + \frac{6 \cdot 0}{z+2} - \frac{4 \cdot 3}{z+3} + \frac{1 \cdot 8}{z+4} ] \\
&= \frac{1}{6(z+1)} - \frac{1}{2(z+3)} + \frac{1}{3(z+4)}
\end{align}
$$となる。
〆
本丸に切り込んだ感。
