メインコンテンツへスキップ
見出し画像

順列と組み合わせに関する面白い(?)性質

    今回は、順列(nPr_nP_r)と組み合わせ(nCr_nC_r)に関する面白い性質について解説していきます。nPr_nP_rとnCr_nC_rについてなんとなく理解していれば基本的に面白いものだと思います。

    【前提】順列Pと組み合わせCの定義式

    まずは大前提として順列と組み合わせの定義式を確認しておきましょう。

    nPr=n!(n−r)!  nCr=nPrr!=n!r!(n−r)!_nP_r=\frac{n!}{(n-r)!} \\\ \\\ _nC_r=\frac{_nP_r}{r!}=\frac{n!}{r!(n-r)!}

    また、実際は少し計算の工夫をすると楽にできます。これは階乗を展開して約分すると導出できます。(これは結構有名です)

    nPr=n(n−1)(n−2)…(n−r+1)_nP_r=n(n-1)(n-2)…(n-r+1)

    式を見ただけではよくわからないと思うので、実際に計算してみましょう。

    10P5=10×9×8×7×6=30240_{10}P_5=10\times9\times8\times7\times6=30240

    つまり、nnからrr個階乗のやり方で掛け算すればいいということです。nCr_nC_rも公式にnPr_nP_rが含まれていることから楽に計算できますね。

    nPnとnCnの値

    まずはちょっとした豆知識的なことです。

    nPn=n! nCn=1_nP_n=n!\\\ _nC_n=1

    これはそれぞれの定義式からすぐに導出できます。

    nPn=n!(n−n)!=n!0!0!=1だから、n!0!=n!1=n!_nP_n=\frac{n!}{(n-n)!}=\frac{n!}{0!}\\ 0!=1だから、\frac{n!}{0!}=\frac{n!}{1}=n!

    nCn=nPnn! nPn=n!より、nCn=n!n!=1_nC_n=\frac{_nP_n}{n!}\\\ _nP_n=n!より、_nC_n=\frac{n!}{n!}=1

    順列Pと組み合わせCの関係性

    こちらも定義式からすぐに導出できるnPr_n\mathrm{P}_rとnCR_n\mathrm{C}_Rの関係性です。

    nPr=nCr×r!また、同じことだが r!=nPrnCr_nP_r=\\_nC_r\times r!\\ また、同じことだが  r!=\dfrac{_nP_r}{_nC_r}

    これの導出は超簡単です。

    nCr=nPrr!より、両辺にr!を掛けると、_nC_r=\dfrac{_nP_r}{r!}より、両辺にr!を掛けると、
    nPr=nCr×r!_nP_r=\\_nC_r\times r!
    また、両辺をnCrで割ると、また、両辺を_nC_rで割ると、
    r!=nPrnCrr!=\dfrac{_nP_r}{_nC_r}

    組み合わせの対称性

    次に結構有名なことだと思いますが組み合わせの対称性です。

    nCr=nC(n−r)_nC_r=\\_nC_{(n-r)}

    10C8=10C10−8=10C2=10P22!=10×92=45_{10}C_8=\\_{10}C_{10-8}=\\_{10}C_{2}=\dfrac{_{10}P_2}{2!}=\dfrac{10\times9}{2}=45などのように、
    r>n−rr>n-rのときは対称性を利用すると楽に計算できることがあります。

    次に導出(証明)です。

    nCr=n!r!(n−r)! …①_nC_r=\dfrac{n!}{r!(n-r)!}  …①
    ①にr=n−rを代入すると、①にr=n-rを代入すると、
    nC(n−r)=n!(n−r)!(n−(n−r))!=n!(n−r)!r!=n!r!(n−r)!_nC_{(n-r)}=\dfrac{n!}{(n-r)!(n-(n-r))!}=\dfrac{n!}{(n-r)!r!}=\dfrac{n!}{r!(n-r)!}
    よって、nCr=nC(n−r)よって、_nC_r=\\_nC_{(n-r)}

    組み合わせの「和」の値

    次に組み合わせの和の値を考えてみましょう。下のような式の値です。

    ∑r=0nnCr(=nC0+nC1+nC2+nC3+…+nCn−1+nCn)\sum_{r=0}^n \\_nC_r\\ (=\\_nC_0+\\_nC_1+\\_nC_2+\\_nC_3+…+\\_nC_{n-1}+\\_nC_n)

    この値は実は2n2^nになります。これは二項定理を利用して導出できます。

    二項定理より、二項定理より、
    (a+b)n=nC0an+nC1an−1b+nC2an−2b2+…+nCn−1abn−1+nCnbn(a+b)^n=\\_nC_0a^n+\\_nC_1a^{n-1}b+\\_nC_2a^{n-2}b^2+…+\\_nC_{n-1}ab^{n-1}+\\_nC_nb^n
    ここで、a=1,b=1を代入すると、ここで、a=1,b=1を代入すると、
    (1+1)n=nC0⋅1n+nC1⋅1n−1⋅1+nC2⋅1n−2⋅12+…+nCn⋅1n(1+1)^n=\\_nC_0\cdot1^n+\\_nC_1\cdot1^{n-1}\cdot1+\\_nC_2\cdot1^{n-2}\cdot1^2+…+\\_nC_n\cdot1^n
    これを計算すると、これを計算すると、
    2n=nC0+nC1+nC2+nC3+…+nCn−1+nCn2^n=\\_nC_0+\\_nC_1+\\_nC_2+\\_nC_3+…+\\_nC_{n-1}+\\_nC_n

    順列の「和」の値

    次は順列の和を見てみましょう。次のような式の値です。

    ∑r=0nnPr(=nP0+nP1+nP2+nP3+…+nPn−1+nPn)\sum_{r=0}^n \\_nP_r\\ (=\\_nP_0+\\_nP_1+\\_nP_2+\\_nP_3+…+\\_nP_{n-1}+\\_nP_n)

    この値は次のようなものになります。

    ∑r=0nnPr=n!(10!+11!+12!+…+1(n−1)!+1n!)\sum_{r=0}^n \\_nP_r=n!(\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+…+\frac{1}{(n-1)!}+\frac{1}{n!})

    次に導出です。これは単純です。

    まず、分母のn!にはrが含まれていないことから、まず、分母のn!にはrが含まれていないことから、

    ∑r=0nnPr=∑r=0nn!(n−r)!=n!∑r=0n1(n−r)!\sum_{r=0}^n \\_nP_r=\sum_{r=0}^n \frac{n!}{(n-r)!}=n!\sum_{r=0}^n \frac{1}{(n-r)!}

    ここで、rに値を代入していくと、ここで、rに値を代入していくと、

    n!∑r=0n1(n−r)!=n!(1n!+1(n−1)!+…+11!+10!)n!\sum_{r=0}^n \frac{1}{(n-r)!}=n!(\frac{1}{n!}+\frac{1}{(n-1)!}+…+\frac{1}{1!}+\frac{1}{0!})

    当然1n!+1(n−1)!+…+11!+10!=10!+11!+12!+…+1(n−1)!+1n!だから当然\frac{1}{n!}+\frac{1}{(n-1)!}+…+\frac{1}{1!}+\frac{1}{0!}=\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+…+\frac{1}{(n-1)!}+\frac{1}{n!}だから

    ∑r=0nnPr=n!(10!+11!+12!+…+1(n−1)!+1n!)\sum_{r=0}^n \\_nP_r=n!(\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+…+\frac{1}{(n-1)!}+\frac{1}{n!})

    【発展】n→∞のときの順列の和

    最後にちょっとした発展です。
    注:ここからのこの項はかなりマニアックな内容です。
      この内容はたぶん正直役に立ちません。
      下の式/文を見てやばいと思った方は読み飛ばしてもらって構いません。
    具体的には下のような式です。

    lim⁡n→∞∑r=0nnPr\lim_{n\to\infty}{\sum_{r=0}^n\\_nP_r}

    この値はe⋅n!e\cdot n!となります。以下にその導出を書きます。この導出では∑r=0nnPr=n!∑r=0n1(n−r)!\sum_{r=0}^n\\_nP_r=n!\sum_{r=0}^n\frac{1}{(n-r)!}の変形までは先ほどの導出と全く同じです。

    この導出は大学数学で習うであろうテイラー展開を使います。さすがにこれを覚えている人は少ないかと思うので、今回使う部分だけ軽く説明しておきます。

    ある関数f(x)がx=aで十分に微分可能であるとき、ある関数f(x)がx=aで十分に微分可能であるとき、
    f(x)をaの周りでテイラー展開すると次のようになる。f(x)をaの周りでテイラー展開すると次のようになる。

    f(x)=f(a)+f′(a)(x−a)1!+f′′(a)(x−a)22!+…+f(n)(a)f(x)=f(a)+f'(a)\frac{(x-a)}{1!}+f''(a)\frac{(x-a)^2}{2!}+…+f^{(n)}(a)

    ここで、テイラー展開が無限に続く場合はテイラー級数と呼ばれる。ここで、テイラー展開が無限に続く場合はテイラー級数と呼ばれる。
    そして、関数が∞回微分可能な場合はそして、関数が\infty回微分可能な場合は
    そのテイラー級数は関数を無限に精度よく近似する。そのテイラー級数は関数を無限に精度よく近似する。
    ここで、指数関数exのテイラー展開((ex)′=exより無限回微分可能)はここで、指数関数e^xのテイラー展開((e^x)'=e^xより無限回微分可能)は
    次のようになります。(a=0ならすなわちマクローリン級数)次のようになります。(a=0ならすなわちマクローリン級数)

    ex=x00!+x11!+x22!+x33!+…e^x=\frac{x^0}{0!}+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+…

    よって、exは下のような式で表せる。よって、e^xは下のような式で表せる。

    ex=∑k=0∞xkk!e^x=\sum_{k=0}^\infty \frac{x^k}{k!}

    これらのことをなんとなく理解したうえで導出に戻ります。

    まず、n−r=kとおくと、∑r=0n1(n−r)!=∑k=0n1k!まず、n-r=kとおくと、\sum_{r=0}^n\frac{1}{(n-r)!}=\sum_{k=0}^n{\frac{1}{k!}}
    これはexのテイラー展開にx=1を代入した形になっていることから、これはe^xのテイラー展開にx=1を代入した形になっていることから、
    n→∞のとき、∑k=0n1k!=eとなる。よって、n\to\inftyのとき、\sum_{k=0}^n{\frac{1}{k!}}=eとなる。よって、

    lim⁡n→∞∑r=0nnPr=e⋅n!\lim_{n\to\infty}{\sum_{r=0}^n\\_nP_r}=e\cdot n!

    この記事が参加している募集

     
     
    数学とPythonが好きな人です。 主に数学と自作のPythonプログラムの解説記事を書いています。 最近はBVE関連にハマってます… X垢(主にBVE):https://x.com/__init__92435

    あなたへのおすすめ