階乗

数学において自然数 n の階乗(かいじょう、: factorialn! とは、1 から n までの全ての整数ののことである[1]。例えば、

である。空積の規約の下 0! = 1 と定義する[2]

階乗は数学の様々な場面に出現するが、特に組合せ論代数学解析学などが著しい。階乗の最も基本的な出自は n 個の相異なる対象を1列に並べる方法(対象の置換)の総数が n! 通りであるという事実である。

階乗数 オンライン整数列大辞典の数列 A000142
0! 1
1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5040
8! 40320
9! 362880
10! 3628800
11! 39916800
12! 479001600
13! 6227020800
14! 87178291200
15! 1307674368000
16! 20922789888000
17! 355687428096000
18! 6402373705728000
19! 121645100408832000
20! 2432902008176640000
21! 51090942171709440000
22! 1124000727777607680000
23! 25852016738884976640000

階乗の定義は、最も重要な性質を残したまま、非整数を引数とする函数に拡張することができる。そうすれば解析学における著しい手法などの進んだ数学を利用できるようになる。

定義

いくつか同値な条件により定義することが可能である。

  • 再帰的な定義
  • 微分に関する「冪の法則英語版」を用いた定義
  • n! = ( n 元集合の置換の総数 )

上記の何れの定義においても、

となることが織り込み済みである(最初の定義では「 0 項の積は 1 と定める」という規約によって)[注釈 1]。このように定義する理由は:

  1. 零個の対象の置換は(「何もしない」という)ちょうど一通りであること。
  2. n > 0 のとき有効な漸化式 (n + 1)! = n! × (n + 1), が n = 0 の場合にも延長できること。
  3. 指数関数などの冪級数としての表示
    など多くの公式が短く表せるようになること。
  4. 組合せ論における多くの等式が任意のサイズに適用して意味を持つこと。例えば零個の元を空集合から選ぶ方法の総数は
    であり、一般に n 元集合から n 個全ての元を選び出す方法の総数は
    と書ける。

など様々に挙げることができる。

より進んだ数学においては、引数が非整数の場合にも階乗函数を定義することができる(後述)。そういった一般化された定義のもとでの階乗は関数電卓や、MapleMathematica などの数学ソフトウェアで利用できる。

プログラミング言語における階乗

多くのプログラミング言語において、再帰的な定義を利用し、プロシージャ再帰呼び出しを用いた階乗の実装が可能である。

以下はC言語での例である。例示するコードではunsigned long long型を使用しているが、unsigned long long型では小さな階乗(21!)でもオーバーフローしてしまうため、大きな階乗については任意精度演算による実装を検討すべきである[3]

unsigned long long factorial(unsigned int n)
{
    if (n > 0)
         return n * factorial(n - 1);
    return 1; // 0! == 1
}

組合せ論

階乗を含む公式は数学の多くの分野に現れるが、階乗のおおもとの出自は組合せ論にある。相異なる n 個の対象の順列k-順列)の総数は n! 通りである。

階乗はしばしば「順番を無視する」という事実を反映するものとして分母に現れる。古典的な例としては n 個の元から k 個の元を選ぶ組合せk-組合せ)の総数が挙げられる。このような組合せは順列から得ることができる。実際、k-順列の総数

において、順番のみが違う(k-組合せでは違いが無視される)k-順列が k ! 通りずつ存在するから、k-組合せの総数は

となる。この数は、二項冪 (1 + X)n における Xk の係数となることから、二項係数 とも呼ばれる。

代数学に現れる階乗にはいくつも理由があるが、既述の如く二項展開の係数として現れたり、ある種の演算の対称化英語版 において置換による平均化を行うなど、組合せ論的な理由で現れるものもある。

微分積分学においても階乗は例えばテイラー級数の分母として現れるが、これは冪函数 xnn 階導函数が n ! であることを補正する定数である。確率論でも階乗は用いられる。

階乗は数式操作にも有効である。例えば nk-順列の総数を

と書けば、(この数値を計算することを考えれば効率が悪くなるが)二項係数の対称性

を見るには都合がよい。

数論における階乗

階乗は数論にも多くの応用を持つ。特に n !n 以下の全ての素数で整除されねばならない。このことの帰結として、n ≥ 5合成数となる必要十分条件

が満たされることである。より強い結果としてウィルソンの定理

p が素数であるための必要十分条件であることを述べる。

ルジャンドルの公式n ! の素因数分解に現れる p の重複度が

であることを示す。これは

に等しくなる。ただし、sp(n)np進展開の係数の和である。

n ! が素数となる n2 のみである。n! ± 1 の形の素数は階乗素数と呼ばれる。

1! より大きな階乗は全て偶数である(これらは明らかに因数 2 を持ち、2 の倍数である)。同様に、5! より後の階乗は 10 の倍数(25 を因数に持つ)であり、十進展開の末尾には 0 が並ぶ英語版

ブロカールの問題

ブロカールの問題とは、

を満たす n, m は存在するか、という問題である。2015年9月現在、これを満たす (n, m) の組[注釈 2]

(4, 5), (5, 11), (7, 71)

しか見つかっていない。ABC予想が真であれば、解は有限個しかないことが、Marius Overholt により示されている。

階乗の解析学

階乗の逆数和

階乗の逆数の総和は収束級数

を与える(ネイピア数を参照)。この和は無理数となるけれども、階乗に適当な正整数を掛けて和が有理数となるようにすることができる。例えば、

この級数の値が 1 となることを見るには、その部分和が 1 − 1/(n+2)! であることを確認すればよい。したがって、階乗数の全体は無理列英語版を成さない[4]

階乗の増大度

階乗の自然対数 f(n) = log(n!) のグラフをプロットしたもの。このグラフは一見して適当に選び出した n に対する一次函数で近似できそうにも思えるが、そのような直観は誤りである。

n が増えるにつれて、階乗 n !n を変数とする任意の多項式函数あるいは指数函数よりも早く増加する(ただし、二重指数関数よりは遅い)。

n ! の近似式の多くは自然対数

であることを利用する。最も単純に得られる log(n!) の近似値を評価する式は、上記の式と以下の積分:

によって与えられる。積分を評価すれば

を得る。これは、ランダウの記号を用いれば log(n!) のオーダーは Θ(n log n) であることを言っているのであり、この結果はソートアルゴリズム計算量を測るのに重要な役割を果たす。さて上記の log(n!) の評価から

が分かる。実用上はより弱い結果だがより評価のしやすいものを用いることもある。上記の式から簡単な評価をしてみると、任意の n に対して (n/3)n < n! であり、また n ≥ 6 のとき n! < (n/2)n であることなどが分かる。

大きな n に対して n ! をよりよく評価するにはスターリングの公式

を利用する。(ここで は両辺の比が 1 に収束することを表す。)実は任意の n に対して

であることが証明できる[5]

log(n !) の別な近似はシュリニヴァーサ・ラマヌジャンにより

したがって

と与えられている[6]。この近似の誤差は、スターリングの公式よりも小さい。

連続変数への補間

ガンマ関数とパイ関数

階乗函数は負の整数を除く任意の実数に対するものに一般化することができる。例えば * 0! = 1! = 1, * (−1/2)! = π, * (1/2)! = π/2.

負の整数を除けば、階乗関数は非整数の値に対しても定義することができるが、そのためには解析学の道具立てが必要である。そのように階乗の値を「補間」して得られるものの一つがガンマ函数 Γ(z) である(ただし引数が 1 だけずれる)。これは負の整数を除く任意の複素数 z に対して定義される。z の実部が正である場合には

で与えられる。ガンマ函数と階乗との関係は、任意の自然数 n に対して

が成り立つことである。オイラーのもともとの定義式は

である。ガウスの導入した別表記として、負でない実数 z に対するパイ函数 Π(z)

を満たす。ガンマ函数との関係は

である。非負整数 n に対し

が成り立つことを思えば、こちらのほうが階乗を補完した函数としては適していると言えるかもしれない。さてパイ函数は階乗が満たすのと同じ漸化式

を、しかし定義される限り任意の複素数 z に対して満たす。事実としてはこれはもう漸化式ではなくて函数等式と見るべきものであるが。この函数等式をガンマ函数に関するものに書き換えれば

となる。階乗を延長したものがパイ函数なのだから、定義可能な任意の複素数 z に対して

と定めることは可能である。これらの補間函数を用いて半整数における階乗の値を定めるならば、例えば

が成り立ち、さらに自然数 nN に対して

が得られる。例えば

同様に nN に対して

が成り立ち、例えば

パイ函数が殆ど全ての複素数値に対して定義される階乗の延長として唯一のものでないことはもちろんである。それは定義域において解析的としても同じことである。しかし、普通はこれが階乗の複素函数への最も自然な延長であるものと考える。例えば、ボーア・モレルップの定理はガンマ函数が Γ(1) = 1 かつ函数等式 Γ(n + 1) = nΓ(n) を満たす、ガウス平面の全域で有理型かつ実軸の正の部分で対数凸英語版となるような唯一の函数であることを述べる。同様の主張はパイ函数に関しても、函数等式 Π(n) = nΠ(n − 1) に関して述べられる。

そうは言うものの、解析的函数論の意味で恐らくより簡明な、階乗の値を補間する複素函数は存在する。例えばアダマールの「ガンマ」函数[7]はガンマ函数とは異なり整函数になる[8]

オイラーはまた非整数の階乗に対する近似無限乗積

についても考察している。これは上記のガンマ函数に関する公式と同じものと見做すことができる。しかしこの公式は収束が遅く、実用的な意味でパイ函数やガンマ函数の値を計算することに利用することはできない。

ガウス平面上での挙動

複素変数に対する階乗の絶対値と偏角を、単位長さ間隔で −3 ≤ x ≤ 3, −2 ≤ y ≤ 2 の範囲で描いた等高線。太くなぞった等高線は φ = ±π である。

複素変数の階乗の値をガンマ函数による表現を通して評価することができる。絶対値 ρ と偏角 φ を用いて

と書けば、絶対値一定曲線 ρ = (定数) と偏角一定曲線 φ = (定数) を等値線として格子を描くことができる。一定間隔で引いた等値線の間にさらに細かく等値線を引けば、それが補間で得られる値である。極である負の整数においては絶対値と偏角が定義できず、またその周辺で等値線は密になる。

展開の係数の最初の方
n gn 近似値
0 1 1
1 −γ −0.5772156649
2 0.9890559955
3 −0.9074790760
γオイラー・マスケローニ定数ζリーマンゼータ函数である。

|z| < 1 に対してはテイラー展開

が利用できる。この展開のより多くの項は、Sageのような計算機代数システムで計算できる。

階乗の近似

展開の係数 an[9]
n an
0 1/12
1 1/30
2 53/210
3 195/371
4 22999/22737
5 29944523/19733142
6 109535241009/48264275462

大きな値に対する階乗の値の近似をディガンマ函数の積分を通じて連分数表示を用いて記述できる。この方法はスティルチェスによる[7]もので、z! = exp(P(z)) と書けば P(z)

で、スティルチェスはこの第一項 p(z) の連分数展開

を与えた。

さて、任意の複素数 z ≠ 0 に対して log(z!) = P(z) あるいは log(Γ(z + 1)) = P(z) とするのは誤りであり[要出典]、実際には実軸の近くの特定の範囲の z でしか成り立たない(一方 |ℑ(Γ(z + 1))| < π である。引数の実部は大きいほど、虚部はより小さくなければならない。しかし逆の関係式 z! = exp(P(z)) は原点を除くガウス平面の全域で有効である。ただし実軸の負の部分では収束性は弱くなる[要出典](特異点の周辺ではどのような近似もよい収束性を得ることが難しい)。一方、|ℑ(z)| > 2 または ℜ(z) > 2 の範囲では上記の六つの係数は double 精度の複素数に対してその階乗の近似値を得るのに十分である。より高い精度でより多くの係数を計算するには rational QD-scheme (H. Rutishauser's QD algorithm)[10]を用いる。

負の整数に対する拡張不能性

関係式 n! = n × (n − 1)! を使えばある整数に対する階乗をそれより「小さい」整数の階乗から計算できる。この関係式を逆に使えば、「大きい」整数に対して与えられた階乗から

と計算することも可能である。しかし注意すべきは、これでは負の整数に関する階乗を計算することはできないということである(この式に従って (−1)! を計算するには零除算が必要となりこれ以下の負の整数における階乗の値の計算は不可能となる)。このことはガンマ函数においても同じことで、ガンマ函数は負の整数を除くガウス平面の全域において定義できるにも拘らず、負の整数における値だけは定義することができない。

一般化

多重指数記法

多重指数 に対し階乗は、

と定義できる。これは例えば、多変数関数の展開に使われる。

デデキント環への拡張

マンジュル・バルガヴァは階乗を一般のデデキント環上で定義し、いくつかの古典的な問題を解決するために用いた[11]。それらの階乗は整数ではなく、イデアルとなる。

階乗に類似する概念

二重階乗

二重階乗の例
(-9)!! = 1/105
(-7)!! = −1/15
(-5)!! = 1/3
(-3)!! = −1
(-1)!! = 1
0!! = 1
1!! = 1
2!! = 2
3!! = 3
4!! = 8
5!! = 15
6!! = 48
7!! = 105
8!! = 384
9!! = 945
10!! = 3840
11!! = 10395
12!! = 46080
13!! = 135135
14!! = 645120
15!! = 2027025
16!! = 10321920
17!! = 34459425
18!! = 185794560
19!! = 654729075
20!! = 3715891200

階乗の類似として、二重階乗 n!! は自然数 n に対し一つ飛ばしに積を取る。二重階乗 n!! は階乗 n! の二回反復合成 (n!)! とは異なる。

奇数 n = 1, 3, 5, 7, … に対する二重階乗の最初の方の値は

1, 3, 15, 105, 945, 10395, 135135, …,A001147

偶数 n = 0, 2, 4, 6, 8, … に対する二重階乗の値の最初の方は

1, 2, 8, 48, 384, 3840, 46080, 645120, …A000165

で与えられる。

負の奇数にも拡張される( )。また、複素数値への拡張として、以下が知られている[12]

多重階乗

より一般に多重階乗 (multifactorial) は、連続した整数の積である通常の階乗 n!、一つ飛ばしの積である二重階乗 n!!、二つ飛ばしの積である三重階乗 n!!! または n!3、三つ飛ばしの四重階乗 n!!!! または n!4 などを総称して言う。

三重階乗の例
1, 4, 28, 280, 3640, 58240, 1106560, …A007559
2, 10, 80, 880, 12320, 209440, 4188800, …A008544
3, 18, 162, 1944, 29160, 524880, …A032031
四重階乗の例
1, 5, 45, 585, 9945, 208845, 5221125, …A007696
2, 12, 120, 1680, 30240, 665280, 17297280, …A001813
3, 21, 231, 3465, 65835, 1514205, …A008545
4, 32, 384, 6144, 122880, 2949120, …A047053
定義
一般の k-重階乗 n!k は正整数 n に関して帰納的に

と定義できる。これと異なる定義として

定義

とするものもある。

階乗冪

自然数 n, k に対して、nk-順列の総数 nkn から始めて上から k 個の連続する整数の積を取る(ある意味で不完全な階乗とも呼べる)階乗の類似物であった。これを下降階乗冪と呼ぶ。その反対に n から始めて下から k 個の連続する整数の積をとったもの nk上昇階乗冪といい、これら二つを総称して階乗冪と呼ぶ。ただし一般に自然数に限らず(実数や複素数などに値をとる)x を変数として

を考えることが多い。明らかに自然数 n に対して

また一般に実数 x ≠ 0 に対して

と定義する(空積も参照)が x = 0 のときもそうであるかは規約による(例えば上記の関係式 n! = nnn = 0 のとき 1 = 0! = 00 で矛盾しない。0^0も参照)。

素数階乗

素数階乗 (Primorial) n は最初の n-個の素数の総乗

である[13]。(オンライン整数列大辞典の数列 A002110

これは、素数が無限に存在するという命題の証明に用いられることがある。

超階乗

Pickover (1995)[14]超階乗superfactorial)は、階乗を入れ子に拡張したものである。ドル記号$を用いて書かれる。またLawrence Hollom氏が開発した超階乗配列表記は階乗をベースとした配列表記で従来の階乗や超階乗より遥かに大きな増加速度を持つ。

定義[注釈 3]

nが3以上になると、非常に大きい値になる。

これとは異なる種類の超階乗の定義がある。Neil J. A. Sloane and Simon Plouffe (1995) The Encyclopedia of Integer Sequences[15] は、超階乗superfactorial)を定義した。例として、4の超階乗は次のようになる。

一般的にこの定義における超階乗は下の式で定義される。

定義[注釈 3]

これは以下と同値:

最初のいくつかの値は、次のようになる:

1, 1, 2, 12, 288, 34560, 24883200, 125411328000, … A000178

超階乗は、複素数値にも拡張できる。その結果はバーンズのG関数と呼ばれる。定義は次のようになる。

自然数に対しては、以下が成り立っている。

hyperfactorial

ハイパー階乗 (hyperfactorial) は、以下で定義される。

これはとても大きくなっていく。最初のいくつかの値はつぎの通りである[16]

1, 4, 108, 27648, 86400000, ……

ハイパー階乗は定義域を複素数にまで拡張できる。それはK函数と呼ばれ、以下で定義される。

自然数 n に対し、次が成り立つ。

階冪

以下、↑をクヌースの矢印表記とする。

階乗が連続する整数を順に「乗」じるのに対し、連続する整数を順に冪にする演算として階「冪」 (exponential factorial) [注釈 4] n!(感嘆符は右肩に添字として書く)[要出典]

で与えられる。つまり、自然数 n に対して

であり、最初の5つの値は次のようになる。

0! = 1, 1! = 1, 2! = 2, 3! = 9, 4! = 262144, ……オンライン整数列大辞典の数列 A049384

5! の値は十進展開で183231桁にも及ぶきわめて大きな自然数である。

これ以降は、グーゴルプレックス より遥かに大きくなる(6! を計算すると、およそ 66.2×10183230 ≒ 104.8×10183230 となる)。

全ての自然数の exponential factorial の逆数の総和は、

となる。この数は、超越数であり、リウヴィル数である[18]

また、高次 exponential factorial が定義される。例として、二次 exponential factorial は、

となる。一般の m-次 exponential factorial は

で与えられる。ただし、n, m は自然数である。

歴史

n 個の相異なる対象を1列に並べる方法の総数が n! 通りであるということは、少なくとも12世紀にはインドの学者によって知られていた[19]ファビアン・ステッドマン英語版は1677年にチェンジリンギング英語版への応用として階乗を記述した[注釈 5]。再帰的な手法による記述の後、Stedman は(独自の言葉を用いて)階乗に関しての記述を与えている:

Now the nature of these methods is such, that the changes on one number comprehends [includes] the changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire body;[21]

感嘆符(!)を用いた、この "n!" という表記は1808年クリスチャン・クランプによって発明された[22]

注釈

  1. ^ 空集合から空集合への全単射は空写像ただ1つ存在する。
  2. ^ このような (n, m) を、ブラウン数 (: Brown numbers) と呼ぶ。
  3. ^ a b 両者は全く同値でない
  4. ^ 指数階乗[17]中国語: 阶幂
  5. ^ The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed.[20]

出典

  1. ^ 階乗」『精選版 日本国語大辞典』https://kotobank.jp/word/%E9%9A%8E%E4%B9%97コトバンクより2022年2月7日閲覧 
  2. ^ Graham, Knuth & Patashnik, p. 111
  3. ^ この記事の過去の版で「大きな階乗についてはdouble型のような浮動小数点数型を用いるなどの工夫が必要となる」との記述があったが、2021年時点の典型的な64ビットマイクロプロセッサでは、整数型のビット長 > 浮動種数点型仮数部のビット長 なのでこれは当たらない。
  4. ^ Guy 2004, p. 346
  5. ^ 杉浦 1980, p. 339, 定理 15.7.
  6. ^ Ramanujan 1988, p. 339
  7. ^ a b Hadamard 1894
  8. ^ Peter Luschny, Hadamard versus Euler - Who found the better Gamma function?.
  9. ^ Digital Library of Mathematical Functions, http://dlmf.nist.gov/5.10
  10. ^ Peter Luschny, On Stieltjes' Continued Fraction for the Gamma Function..
  11. ^ The Factorial Function and Generalizations
  12. ^ Weisstein, Eric W. "Double Factorial". mathworld.wolfram.com (英語).
  13. ^ Weisstein, Eric W. "Primorial". mathworld.wolfram.com (英語).
  14. ^ Pickover, Clifford A. (1995). Keys to Infinity. New York: John Wiley & Sons. doi:10.2307/2687608. JSTOR 2687608 
  15. ^ Sloane, Neil J. A.; Plouffe, Simon (1995). The Encyclopedia of Integer Sequences. San Di\ego: Academic Press. ISBN 0-12-558630-2. https://oeis.org/book.html 
  16. ^ オンライン整数列大辞典の数列 A002109
  17. ^ 巨大数研究 Wiki 指数階乗
  18. ^ Sondow, Jonathan. "Exponential Factorial". mathworld.wolfram.com (英語).
  19. ^ Biggs, pp. 109–136
  20. ^ Stedman 1677, pp. 6–9
  21. ^ Stedman 1677, p. 8.
  22. ^ Higgins, p. 12

参考文献

関連項目

外部リンク