Easy Exercise

数学について勉強したこと、見つけたことのメモ。

ディガンマ関数

ディガンマ関数と自然数の累乗の逆数和との関係についてのメモ。

ディガンマ関数

ディガンマ関数とは、ガンマ関数 \Gamma(s) の対数微分

\displaystyle \psi(s) = \frac{\mathrm{d}}{\mathrm{d}s}\log(\Gamma(s)) = \frac{\Gamma'(s)}{\Gamma(s)}

で定義される関数\psi(s)です。

ガンマ関数の無限乗積表示

ガンマ関数の無限乗積表示について復習します。

命題1 全ての s\in\mathbb{C} に対して
\displaystyle \frac{1}{\Gamma(s)} = s e^{\gamma s} \prod_{n=1}^{\infty}\left(1+\frac{s}{n}\right)e^{-s/n}
が成り立つ。ここで \gammaオイラーの定数
\displaystyle \gamma = \lim_{n\to\infty}\left(\sum_{k=1}^{n}\frac{1}{k}-\log n\right)
である。

この命題の証明は

integers.hatenablog.comにあります。

ディガンマ関数の性質1

命題1の両辺の対数微分をとると次が分かります:

定理1 s \neq 0,-1,-2,\ldots に対して
\displaystyle \psi(s) = -\gamma + \sum_{n=0}^{\infty} \left(\frac{1}{n+1} - \frac{1}{n+s} \right)
が成り立つ。特に
\psi(1) = -\gamma
である。

さらに、第一の等式の両辺を繰り返し微分すると次も分かります:

定理2 k1以上の整数とする。s \neq 0,-1,-2,\ldots に対して
\displaystyle {\psi}^{(k)}(s) = {(-1)}^{k-1} k! \sum_{n=0}^{\infty} \frac{1}{(n+s)^{k+1}}
が成り立つ。特に
\displaystyle {\psi}^{(k)}(1) = {(-1)}^{k-1} k! \zeta(k+1)
である。

このようにディガンマ関数の導関数s=1 での値はゼータ値と関係しています。

次に s=2,3,4,\ldots での値を見ていきます。

ディガンマ関数の性質2

定理3 n1 以上の整数とする。s \neq 0,-1,-2,\ldots に対して
\displaystyle \psi(s+n) = \psi(s) + \sum_{k=0}^{n-1} \frac{1}{s+k}
が成り立つ。特に
\displaystyle \psi(n+1) = -\gamma + \sum_{k=1}^{n} \frac{1}{k}
である。

証明.ガンマ関数の関数等式 \Gamma(z+1)=z\Gamma(z) の両辺の対数微分をとると

\displaystyle \psi(z+1) - \psi(z) = \frac{1}{z}

が分かり、 z=s,s+1,\ldots,s+n-1 について辺々加えると第一の等式を得る。この等式において s=1 とおけば第二の等式を得る。証明終わり

また両辺の微分により次も分かります:

定理4 n,k1 以上の整数とする。s \neq 0,-1,-2,\ldots に対して
\displaystyle {\psi}^{(k)}(s+n) = {\psi}^{(k)}(s) + {(-1)}^{k} k! \sum_{m=0}^{n-1} \frac{1}{{(s+m)}^{k+1}}
が成り立つ。特に
\displaystyle {\psi}^{(k)}(n+1) = {(-1)}^{k} k! \left( -\zeta(k+1) + \sum_{m=1}^{n} \frac{1}{{m}^{k+1}} \right)
である。

ニムゲームと排他的論理和

ニムと呼ばれる二人で行うゲームの必勝法と、それにまつわる演算を紹介します。

ニム

ニムは二人のプレイヤーがいくつかの石の山から石を交互に取り合うゲームです。ニムのルールはいろいろバリエーションがありますが、次のルールを考えます。

ニムのルール
  1. 石の山をいくつか用意する。
  2. 二人のプレーヤーは交互に 1 個以上石を取る。このとき、複数の山にまたがっては取れないが、一つの山からは何個でも取れる。
  3. 取れる石が無くなったら負け。

後でルール2を変えたゲームも考えます。

以下では、ニムの局面を非負整数の順序対で表します。

(4,2,1) は、1 番目の山に 4 個、2 番目の山に 2 個、3 番目の山に 1 個石がある局面。

Grundy

ニムの局面には、Grundyという非負整数値が定まります。

Grundy値の定義と性質については

fibonacci-freak.hatenablog.com

にあります。そこに書かれているように、Grundy値が 0 の局面は後手必勝、nonzeroの局面は先手必勝です。

ニムの局面 (n_1,\ldots,n_k)Grundy値を G(n_1,\ldots,n_k) と表すことにすると、局面 (n_1,\ldots,n_k) は局面 (n_1),\ldots,(n_k) の直和*1だから、上の記事の第一定理より、

\begin{split} G(n_1,\ldots,n_k)&= G(n_1) \oplus \cdots \oplus G(n_k) \\&= n_1 \oplus \cdots \oplus n_k \end{split}

ここで \oplus は二進記数法の各桁ごとの排他的論理和です。この「二進記数法の各桁ごとの排他的論理和」のことも単に排他的論理和と呼びます。

11 \oplus 5 = {1011}_2 \oplus {101}_2 = {1110}_2=14

よって次の結果を得ます:

定理1 ニムの局面(n_1,\ldots,n_k)が後手必勝 \Leftrightarrow n_1 \oplus \cdots \oplus n_k = 0

これをもとにしたニムの必勝法の手順は

ニム(複数山の石取りゲーム)の必勝法 | 高校数学の美しい物語

の「ニムの必勝法の概略」にあります。その記事では「後手必勝」のことを単に「必勝形」と呼んでいます。

N-ニム

N自然数とします。上のニムのルールにおいて、一つの山から取れる石の個数を 1 以上 N 以下に変更したゲームを考えます。区別のため、このゲームを N -ニムと呼ぶことにします*2

N-ニムの局面も同じく順序対で表し、N-ニムの局面 (n_1,\ldots,n_k)Grundy値を G_N(n_1,\ldots,n_k) と表すことにすると、

\begin{split} G_N(n_1,\ldots,n_k)&= G_N(n_1) \oplus \cdots \oplus G_N(n_k) \\&= (n_1 \ \mathrm{mod} \ N+1) \oplus \cdots \oplus (n_k \ \mathrm{mod} \ N+1) \end{split}

ここで自然数 k に対して n \ \mathrm{mod} \ k は、整数 nk で割った余り(0 以上 k-1 以下)を返す関数です。

まとめると次の結果となります:

定理2 N-ニムの局面 (n_1,\ldots,n_k) が後手必勝 \Leftrightarrow (n_1 \ \mathrm{mod} \ N+1) \oplus \cdots \oplus (n_k \ \mathrm{mod} \ N+1) = 0

3-ニムの必勝法

N=3の場合について必勝法を考えます。

3-ニムの局面(n_1,\ldots,n_k)が後手必勝 \Leftrightarrow n_1, \ldots , n_k のうち、4 で割って 1 余るものの個数、2 余るものの個数、3 余るものの個数の偶奇が一致する。

証明.定理2から明らか。証明終わり

この系をもとに具体的な必勝法の手順を考えます。(n_1,\ldots,n_k)3-ニムの先手必勝の局面とします。n_1, \ldots , n_k のうち、4 で割ってi(i=0,1,2,3) 余るものの個数を a_i とおいて、a_1,a_2,a_3 の偶奇で場合分けします。系により次の二つの場合に分かれます。

1:a_1,a_2,a_3 のうち、偶数が 2 個、奇数が 1 個のとき

奇数であるものを a_i(i\neq 0) とすると、a_0\to a_0+1 かつ a_i\to a_i-1 となる手が存在する。

例えば a_1 が奇数だとすると、石の個数が 4 で割って 1 余る山を一つ選んで、1 個石を取る。

2:a_1,a_2,a_3 のうち、偶数が 1 個、奇数が 2 個のとき

奇数であるものを a_i,a_j(0\lt i\lt j) とすると、a_i \to a_i+1 かつ a_j\to a_j-1 となる手が存在する。

例えば a_1,a_3 が奇数だとすると、石の個数が 4 で割って 3 余る山を一つ選んで、2 個石を取る。

この手順を繰り返せば自分の番が終わった後の局面は常に後手必勝となっているので、最終的には石が全く無い状態(=勝ち)に到達できます。

m\oplus nの計算

最後に、m\oplus n の値の計算結果を示します。値が同じ所は同じ色で塗っています。

f:id:oddie2357:20180505171441j:plain

この表を眺めると、いろんな対称性に気がつくと思います。例えばこの図を 2 倍に拡大したときの相似性が見て取れます。

*1:ゲームの局面 S_1S_2 の直和とは、単に S_1S_2 を横に並べた局面のことで、その指し手の集合は、S_1 の指し手と S_2 の指し手の直和。

*2:この記事のみでの呼称。

このブログについて

はじめまして、oddieと申します。

このブログは主に、私が数学について見つけたこと、勉強したことの備忘録です。

自分の数学の勉強のモチベーションアップのために活用していくつもりです。

数学の特定の分野に偏らず、様々な分野について書いていきたいと思います。

文章の誤植や、論理的におかしいところなどありましたら、コメントで指摘くださると幸いです。