【数学】場合の数・順列・組合せ　代表的な問題

  • 約数の個数と総和

自然数Nを素因数分解するとN=p^a q^bとなるとき

Nの正の約数の個数は(a+1)(b+1)

正の約数の総数は(1+p...+p^a)(1+q...+q^b)となる。

―例ー

「２８」の正の約数は　　28=2^2 \cdot 7　から

 2^a \cdot 7^bとなる。(a=0,1,2)(b=0,1)

よって、aは３通り、b２通りのため

3 \cdot 2=(2+1)(1+1)=6　となる。

総和は

2^0 \cdot 7^0+2^0 \cdot 7^1+2^1 \cdot 7^0+2^1 \cdot 7^1+2^2 \cdot 7^0+2^2 \cdot 7^1

=2^0 \cdot (7^0+7^1)+2^1 \cdot (7^0+7^1)+2^2 \cdot (7^0+7^1)

=(1+2^1+2^2)(1+7^1) となる。

 

 

  • じゅず順列

異なるいくつかのものを円形に並べ、回転や裏返して一致するものを同じものとみる順列を「じゅず順列」という。

円順列の場合では異なっていても、裏返したら一致するものもあるため、総数は円順列の「半分」になる。

つまり、異なるn個のもののじゅず順列の総数は\frac{(n-1)!}{2}となる。

 

 

  • 重複組合わせ

異なるn個のものから、重複を許してr個取る組み合わせの総数は「Ｈ」を使い、

{}_n H_r={}_{n+r-1}C_r（n＜rでもよい）

ー例ー

「♠、☘、♡、♢の４つのスートから、含まないものがあってもよいとして５枚選ぶ」

仕切りを考える、仕切りは４つのスートを分けるため4-1=3　となり

例えば

「〇｜〇｜〇〇｜〇」

「〇〇〇｜〇〇｜｜」のように、考えられる。

こうすると、５つの〇と３つの｜の順列の総数が、４種から５枚選ぶ選び方の総数に一致する。これは、同じものを含む順列で、８つの場所から、５個の場所を選ぶ組み合わせに等しいため

{}_{5+4-1}C_5=56　となる。

 

 

  • 組分け

組分けでは、「分けるものが区別できるか」「分けてできるものが区別できるか」を考える。

―例ー

８人いるとき

①「１人、２人、５人の３組に分ける。」

分けるものが区別できるから、{}_8C_1 \cdot {}_7C_2 \cdot {}_5C_5=168（通り）となる。

 

②「Ａ４組、Ｂ４組に分ける。」

分けてできるものが区別できるからＡとＢを区別し、

「Ａに４人選ぶ方法」×「Ｂに４人選ぶ方法」となるため

{}_8C_4 \cdot {}_4C_4=70（通り）となる。

 

③「４人、４人の３組に分ける。」

 どちらも区別できず、同じものが2!通りずつできるから

\frac{{}_8C_ 4 \cdot {}_4C_4}{2!}=35（通り）となる。