今回は、順列(nPr)と組み合わせ(nCr)に関する面白い性質について解説していきます。nPrとnCrについてなんとなく理解していれば基本的に面白いものだと思います。
【前提】順列Pと組み合わせCの定義式
まずは大前提として順列と組み合わせの定義式を確認しておきましょう。
nPr=(n−r)!n! nCr=r!nPr=r!(n−r)!n!
また、実際は少し計算の工夫をすると楽にできます。これは階乗を展開して約分すると導出できます。(これは結構有名です)
nPr=n(n−1)(n−2)…(n−r+1)
式を見ただけではよくわからないと思うので、実際に計算してみましょう。
10P5=10×9×8×7×6=30240
つまり、nからr個階乗のやり方で掛け算すればいいということです。nCrも公式にnPrが含まれていることから楽に計算できますね。
nPnとnCnの値
まずはちょっとした豆知識的なことです。
nPn=n! nCn=1
これはそれぞれの定義式からすぐに導出できます。
nPn=(n−n)!n!=0!n!0!=1だから、0!n!=1n!=n!
nCn=n!nPn nPn=n!より、nCn=n!n!=1
順列Pと組み合わせCの関係性
こちらも定義式からすぐに導出できるnPrとnCRの関係性です。
nPr=nCr×r!また、同じことだが r!=nCrnPr
これの導出は超簡単です。
nCr=r!nPrより、両辺にr!を掛けると、
nPr=nCr×r!
また、両辺をnCrで割ると、
r!=nCrnPr
組み合わせの対称性
次に結構有名なことだと思いますが組み合わせの対称性です。
nCr=nC(n−r)
10C8=10C10−8=10C2=2!10P2=210×9=45などのように、
r>n−rのときは対称性を利用すると楽に計算できることがあります。
次に導出(証明)です。
nCr=r!(n−r)!n! …①
①にr=n−rを代入すると、
nC(n−r)=(n−r)!(n−(n−r))!n!=(n−r)!r!n!=r!(n−r)!n!
よって、nCr=nC(n−r)
組み合わせの「和」の値
次に組み合わせの和の値を考えてみましょう。下のような式の値です。
r=0∑nnCr(=nC0+nC1+nC2+nC3+…+nCn−1+nCn)
この値は実は2nになります。これは二項定理を利用して導出できます。
二項定理より、
(a+b)n=nC0an+nC1an−1b+nC2an−2b2+…+nCn−1abn−1+nCnbn
ここで、a=1,b=1を代入すると、
(1+1)n=nC0⋅1n+nC1⋅1n−1⋅1+nC2⋅1n−2⋅12+…+nCn⋅1n
これを計算すると、
2n=nC0+nC1+nC2+nC3+…+nCn−1+nCn
順列の「和」の値
次は順列の和を見てみましょう。次のような式の値です。
r=0∑nnPr(=nP0+nP1+nP2+nP3+…+nPn−1+nPn)
この値は次のようなものになります。
r=0∑nnPr=n!(0!1+1!1+2!1+…+(n−1)!1+n!1)
次に導出です。これは単純です。
まず、分母のn!にはrが含まれていないことから、
r=0∑nnPr=r=0∑n(n−r)!n!=n!r=0∑n(n−r)!1
ここで、rに値を代入していくと、
n!r=0∑n(n−r)!1=n!(n!1+(n−1)!1+…+1!1+0!1)
当然n!1+(n−1)!1+…+1!1+0!1=0!1+1!1+2!1+…+(n−1)!1+n!1だから
r=0∑nnPr=n!(0!1+1!1+2!1+…+(n−1)!1+n!1)
【発展】n→∞のときの順列の和
最後にちょっとした発展です。
注:ここからのこの項はかなりマニアックな内容です。
この内容はたぶん正直役に立ちません。
下の式/文を見てやばいと思った方は読み飛ばしてもらって構いません。
具体的には下のような式です。
n→∞limr=0∑nnPr
この値はe⋅n!となります。以下にその導出を書きます。この導出では∑r=0nnPr=n!∑r=0n(n−r)!1の変形までは先ほどの導出と全く同じです。
この導出は大学数学で習うであろうテイラー展開を使います。さすがにこれを覚えている人は少ないかと思うので、今回使う部分だけ軽く説明しておきます。
ある関数f(x)がx=aで十分に微分可能であるとき、
f(x)をaの周りでテイラー展開すると次のようになる。
f(x)=f(a)+f′(a)1!(x−a)+f′′(a)2!(x−a)2+…+f(n)(a)
ここで、テイラー展開が無限に続く場合はテイラー級数と呼ばれる。
そして、関数が∞回微分可能な場合は
そのテイラー級数は関数を無限に精度よく近似する。
ここで、指数関数exのテイラー展開((ex)′=exより無限回微分可能)は
次のようになります。(a=0ならすなわちマクローリン級数)
ex=0!x0+1!x1+2!x2+3!x3+…
よって、exは下のような式で表せる。
ex=k=0∑∞k!xk
これらのことをなんとなく理解したうえで導出に戻ります。
まず、n−r=kとおくと、∑r=0n(n−r)!1=∑k=0nk!1
これはexのテイラー展開にx=1を代入した形になっていることから、
n→∞のとき、∑k=0nk!1=eとなる。よって、
n→∞limr=0∑nnPr=e⋅n!