# 調和数 ## 定義 第 $n$ 調和数(harmonic number)$H_n$ は $H_n \coloneqq \sum_{i=1}^n \frac{1}{i} = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ と定義される(定義13.4.1)。調和数には閉じた形(closed form)が知られていない。しかし[[和の近似]](積分限界法、定理13.3.2)を $f(x)=1/x$ に適用すると、$\int_1^n \frac{1}{x}\,dx=\ln(n)$ であることから $\ln(n)+\frac{1}{n} \le H_n \le \ln(n)+1$ という近い上下限が得られる(式13.20)。すなわち $H_n$ は $\ln(n)$ に非常に近い。より精密な近似式(証明なしで引用される、式13.21)は $H_n = \ln(n) + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + \frac{\mu(n)}{120n^4}$ で、$\gamma \approx 0.577215664\ldots$ はオイラーの定数(Euler's constant)、$\mu(n)$ は $0$ と $1$ の間の値である。$n=100$ のとき最初の2項($\ln(n)+\gamma$)だけで真の値との誤差が $1/200$ 未満に収まるほど、この近似は精密である。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.4.2) 調和数は本の張り出し問題(Book Stacking Problem)への応用を通じて導入される: $n$ 冊の本を積んで机の端から最大限張り出させたときの最大張り出し量 $B_n$ は、漸化式 $B_{n+1}=B_n+\frac{1}{2(n+1)}$($B_1=1/2$)を満たし、これを展開すると $B_n = \frac{1}{2}\sum_{i=1}^n \frac{1}{i} = \frac{H_n}{2}$ となる(式13.19)。$H_n$ が上限を持たず(対数的に、ただし非常にゆっくりと)発散するため、本の冊数さえ十分にあれば、机の端から任意の距離だけ本を突き出させられる——ただし必要な冊数は張り出し距離に対して指数的に増加する(張り出し3を得るには227冊が必要)。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.4.1, §13.4.2) 最初の $n$ 個の調和数の和 $\sum_{k=1}^n H_k$ にも閉じた形が存在し、和の順序を交換する(内側の和が閉じた形を持たない場合の技法)ことで $\sum_{k=1}^n H_k = (n+1)H_n - n$ が導かれる(式13.27)。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] §13.6) ## 横断的知見 (この concept は本ソースで初めて作成された。複数ソースの突き合わせによる知見は、他の source が調和数・級数の漸近挙動を扱う際にここへ追記する。) ## 未解決の問い - 調和数はアルゴリズム解析(例えばクイックソートの期待計算量やランダム化アルゴリズムの解析)で頻出することが知られているが、本章(第13章)では書籍の張り出し問題という物理的な応用にとどまり、計算機科学のアルゴリズム解析への直接の接続は扱われていない。後続章や別ソースの ingest 時に本節へ追記する。 - オイラーの定数 $\gamma$ 自体に閉じた形があるかどうかは数学的に未解決(有理数か無理数かすら証明されていない)という事実が、式13.21の近似の「精密さの限界」とどう関係するかは、本章では触れられていない。 - $\sqrt[3]{n}$ に比例する張り出しを実現する「逆ピラミッド」型のスタック構造(§13.4.2 末尾で結果のみ言及、証明は参考文献 [13] に委譲)は、調和数(対数的な張り出し)を超える構造としてどのように調和数の枠組みと接続するか未確認。 ## 関連 - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 13 Sums and Asymptotics]] - 概念: [[和の近似]](積分限界法によってH_nの上下限を導出する)、[[漸近記法]]($H_n \sim \ln(n)$ が漸近的等号の典型例) ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 13 §13.4.