順列@組合せ@2項定理

かけざんとは？

3 x 2 を考える。
3 x 2 とは3つの要素があり、それぞれの要素は2つの要素を持っていると考えられる。
つまり、行列である。

data[3][2]
        
          [0]   [1]
data[0]    *     * 
data[1]    *     *
data[2]    *     *

つまり6個の要素を持つ。

void test(int* array){

 //printf("array[0][1]=%x\n",array[0][1]); <--こんなことはできない
 
 for(int i=0;i<6;i++){
    printf("array=0x%x\n",array);
    printf("*array=%x\n",*array);
    array++;
 }
}

int main(void){
　
　int* matrixp;
　int  matrix[3][2]={{1,2},{3,4},{5,6}};
　 
　matrixp = (int *)matrix;
　
　test(matrixp);

　return 0;
}

array=0x12ff64
*array=1
array=0x12ff68
*array=2
array=0x12ff6c
*array=3
array=0x12ff70
*array=4
array=0x12ff74
*array=5
array=0x12ff78
*array=6
Press any key to continue

データは0x12ff64番地から順々に並ぶため、ポインタの受け手側は、[2][3]か[3][2]か分からない。

順列

異なるn個のものからr個取り出して1列に並べたものを、
n個からr個とる順列
といい、その総数は、

${}_n P_r = n(n-1)(n-2)\cdots(n-r+1)$

たとえば 6個の文字 a,b,c,d,e,fから3個の文字を取り出すとき、総数は

${}_6 P_3$ $= 6 \times 5 \times 4 = 120$

これを考える。

最初は 6通りから1つを選ぶ。
ひとつ選ぶと次は5通りから1つを選ぶ。
つまり

a          b          c          d          e           f
|          |          |          |          |           |
b c d e f  a c d e f  a b d e f  a b c e f  a b c d f   a b c d e

6つの要素が各々5つの要素をもつことになるから

6 x 5 = 30

次に2つ選ぶと次は4通りから1つ選ぶから

a                                              b          c          d          e           f
|                                              |          |          |          |           |
b         c        d        e        f         a c d e f  a b d e f  a b c e f  a b c d f   a b c d e
|         |        |        |        |         | | | | |
c d e f   b d e f  b c e f  b c d f  b c d e   4 4 4 4 4

5つの要素はそれぞれ4つの要素をもつことになるから

6 x 5 x 4 = 120

となる。

階乗

nの階乗 $n! = n(n-1)(n-2)\cdots 3 \cdot 2 \cdot 1$
0!=1

順列は、

${}_n P_r = \frac{n!}{(n-r)!}$
とくに
${}_n P_n = n!$

また、 ${}_n P_0 = 1$

組合せ

順列は、異なるn個のものからr個を取り出したとき!

組合せとは、異なるn個のものからr個取り出して1組にしたものを
n個からr個とる組合せといい、その総数は、

${}_n C_r = \frac{{}_n P_r }{r!}$
$=\frac{n(n-1)(n-2)\cdots(n-r+1)}{r(r-1)(r-2)\cdots 2 \cdot 1}$ $=\frac{n!}{(n-r)!r!}$

■例

(1) ${}_7 C_3 = \frac{ {}_7 P_3 }{3!}$
$=\frac{7\cdot6\cdot5}{3\cdot2\cdot1} = 35$

${}_7 C_3 = \frac{ 7! }{4! 3!} =\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{4\cdot3\cdot2\cdot1\cdot3\cdot2\cdot1}$

(2)7人から3人を選ぶ組合せ

${}_7 C_3 = \frac{{}_7 P_3 }{3!} = 35$ 通り

組合せの関係式

${}_n C_r =$ ${}_n C_{n-r}$
${}_n C_r =$ ${}_{n-1} C_{r-1} +$ ${}_{n-1} C_r$

■例

(i) 5人から2人の委員を選ぶ組合せは、
${}_5 C_2 = \frac{5\cdot 4}{2\cdot 1} = 10$

(i) 5人から委員にならない3人を選ぶ組合せは、
${}_5 C_3 = \frac{5\cdot 4\cdot 3}{3\cdot 2\cdot 1} = 10$
ゆえに
${}_5 C_2 =$ ${}_5 C_3 =$ ${}_5 C_{5-2}$

2項定理

2項定理(binomial theorem)とは、2項式 x + y のべき乗(冪乗) (x + y)^n の展開(二項展開)
を表す公式のことである。

2項展開の一般項 $x^{k} y^{(n-k)}$ の係数を二項係数と呼び、

$\Bigl(\begin{array}{GC+23}n\\k\end{array}\Bigr)$
$= {}_n C_{k} = \frac{n!}{(n-k)!k!}$

と表す。

すなわち2項定理は、

$(x+y)^n = \sum^{n}_{k=0} \Bigl(\begin{array}{GC+23}n\\k\end{array}\Bigr) x^k y^{n-k}$

$(x+y)^3 = \sum^{3}_{k=0} \Bigl(\begin{array}{GC+23}3\\k\end{array}\Bigr) x^k y^{3-k}$
$= \Bigl(\begin{array}{GC+23}3\\0\end{array}\Bigr) x^0 y^{3}$
$+ \Bigl(\begin{array}{GC+23}3\\1\end{array}\Bigr) x^1 y^{2}$
$+ \Bigl(\begin{array}{GC+23}3\\2\end{array}\Bigr) x^2 y^{1}$
$+ \Bigl(\begin{array}{GC+23}3\\3\end{array}\Bigr) x^3 y^{0}$

$= y^3 + 3xy^{2} + 3x^{2}y + x^3$

2項係数を求めるMatlabスクリプト

%メインファンクションの定義
function [C]=bincoeff(n);

%２項係数: nCk = n! / k!(n-k)!

%初期化
C=[];

%2項係数の計算
for k=0:n
  num = kai(n)/(kai(k)*kai(n-k));
  C = [C,num];
end 

%サブファンクションの定義
function out = kai(x)

%階乗 x!
out=prod(1:x);

■結果

>> bincoeff(3)

ans =

     1     3     3     1

参考文献

Focus Up 数学 I + A 高橋陽一朗著啓林館