Σ（Summation）入門

n Σ i = 1

f (i)　= f (1) + f (2)+ f (3) + ... +f (n)

i が 1 から n まで f (i) を合計する。 すなわち、f (i) の i に 1 を代入したもの、2 を代入したもの、3 を代入したもの、...、n を代入したものを全て加えたものである。
i の範囲が、[1, n] とか、議論の中で明確な場合は、

Σ i	f (i)　= f (1) + f (2)+ f (3) + ... +f (n)

の様に省略することがある。全ての i について f (i) を合計すると読む。

10 Σ i = 1

i　= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

3 Σ i = 1

i2　= 1 + 4 + 9 = 14

5 Σ i = 2

Xi　 = X2 + X3 + X4 + X5

　Σの公式

n Σ i = 1

1　= 1 + 1 + 1 + ... + 1 = n

n Σ i = 1

i　= 1 + 2 + 3 + ... + n =

1 2

n(n+1)

n Σ i = 1

i2　= 1 + 4 + 9 + ... + n2 =

1 6

n(n+1)(2n+1)

n Σ i = 1

i3　= 1 + 8 + 27 + ... + n3 = {

1 2

n(n+1)} 2

n Σ i = 1

cf (i) = c

n Σ i = 1

f (i)　（但し c は i に関係ない定数）

n Σ i = 1

{f (i) + g (i)}=

n Σ i = 1

f (i) +

n Σ i = 1

g (i)

　２項展開

(a + b)n　=

n Σ r = 0

nＣra(n-r)br

= an　+ na(n-1)b　+

1 2

n(n-1)

a(n-2)b2　+ ...

+

1 2

n(n-1)

a2b(n-2)　+ nab(n-1)+ bn

_nＣ_r は２項係数と呼ばれ、異なる n 個の物の中から r 個取り出す組み合わせの数である。

n! (n-r)!r!

=

n(n-1)・・・(n-r+1) r(r-1)(r-2)・・・1

（→順列組合入門へ）

　Pascalの三角形

						ｎ		ｒ	→	0
↓									／		1
0 −								1		／		2
1 −							1		1		／		3
2 −						1		2		1		／		4
3 −					1		3		3		1		／		5
4 −				1		4		6		4		1		／		6
5 −			1		5		10		10		5		1		／		7
6 −		1		6		15		20		15		6		1		／
7 −	1		7		21		35		35		21		7		1
								nＣr

順列組合入門

　順列（Permutation）

異なる n 個の物の中から r 個取り出して並べる並べ方の数を _nＰ_r で表す。
１個目の取り出し方は n 通り、そのそれぞれについて、２個目の取り出し方は n-1 通り、３個目の取り出し方は n-2 通り、...､r 個目の取り出し方は n-(r-1) 通りなので、それらを全て掛け合わせる。

nＰr =

n! (n-r)!

=

n(n-1)・・・(n-r+1)

ちなみに、異なる n 個の物を並べる並べ方の数は _nＰ_n = n!^※ で与えられる。

　重複順列

異なる n 個の物の中から重複を許して r 個取り出して並べる並べ方の数を _nΠ_r で表す。（Πはギリシャ文字でπの大文字）
１個目の取り出し方は n 通り、そのそれぞれについて、２個目の取り出し方も n 通り、...、r 個目も n 通りなので、それらを全て掛け合わせる。
_nΠ_r = n^r

　組合（Combination）

異なる n 個の物の中から r 個取り出す組み合わせの数を _nＣ_r で表す。
異なる n 個の物の中から r 個取り出して並べる並べ方の数を r 個の物の並べ方で割ってやれば、取り出し方（組み合せ）の数が得られる。

nＣr =

nＰr r!

=

n! (n-r)!r!

=

n(n-1)・・・(n-r+1) r(r-1)(r-2)・・・1

　重複組合

異なる n 個の物の中から重複を許して r 個取り出す組み合わせの数を _nＨ_r で表す。
ａａａ|ｂｂ|ｃ||ｅ| の様に、１個目の仕切りの左側に１種目を、２個目の仕切りの左側に２種目を、...、ｎ個目の仕切りの左側にｎ種目を置くことにすると、ｎ個目の仕切りは必ず右端に来る。
x₁x₂x₃|₁x₄x₅|₂x₆|₃|₄x₇|₅ の様に、n 種（例の場合は５）の中から、取り出す物の個数 r（例の場合は７）と n-1個の仕切り（例の場合は４）の合計 n+r-1 個（例の場合は１１）の位置に、物を置くのか、仕切りを置くのかを考えると、それが求める重複組合になる。 n+r-1 個の位置から物を置く位置を r 個取る組み合わせは、n+r-1 個の位置から仕切りを置く位置を n-1 個取る組み合わせと考えても同じ。

nＨr = n+r-1Ｃr =

(n+r-1)! (n-1)!r!

=

(n+r-1)(n+r-2)・・・n r(r-1)(r-2)・・・1