順列・組み合わせ
重複順列 (sequence with repetition)
r人をn個の部屋に分ける
$_{n}\Pi_{r}=\underbrace{n\times{n}\times\times{n}}_{r個の積}=n^r$
順列の個数(permutation)
$1\leqq x_1\ne x_2\ne\cdots \ne x_k \leqq n$
$\displaystyle {}_n\mathrm{P}_r = \frac{n!}{(n-r)!}=\overbrace {n(n-1)(n-2)・・・(n-r+1) \quad}^{r個}$
$\displaystyle {}_n\mathrm{P}_r = \frac{n!}{(n-r)!}=\overbrace {n(n-1)(n-2)・・・(n-r+1) \quad}^{r個}$
$1\le x_i\le n,1\le x_j\le n,k_i\ne k_j,1\le i\lt j \le k$
$\displaystyle {}_n\mathrm{P}_r = n(n-1)(n-2)・・・(n-r+1)=\frac{n!}{(n-r)!}$
順列・組み合わせ
重複順列
r人をn個の部屋に分ける
$_{n}\Pi_{r}=\underbrace{n\times{n}\times\cdots\times{n}}_{r個の積}=n^r$
順列
$1\le x_i\le n,1\le x_j\le n,k_i\ne k_j,1\le i\lt j \le k$
$\displaystyle {}_n\mathrm{P}_r = \frac{n!}{(n-r)!}=\overbrace {n(n-1)(n-2)・・・(n-r+1) \quad}^{r個}$
組み合わせ
$\displaystyle {}_n \mathrm{C}_r =\frac{_n \mathrm{P} _r}{r!}=\frac{n!}{r!(n-r)!}= \frac{\overbrace {n(n-1)(n-2)\cdots (n-r+1)}^{r個}}{\underbrace {r\times (r-1)\times \cdots 2 \times 1}_{r個}}$
組み合わせの相補性
nからr個選ぶ組合わせとn-r個選ぶのは同じ
${}_n\mathrm{C}_r={}_n\mathrm{C}_{r-1}$
nとrを1ずつ増やす場合
n人からr人を選んでから代表を決めることと、n人の中から代表を選び、残ったn-1人からr-1人を選ぶことは同じ
$r\;{}_n\mathrm{C}_r=n\;{}_{n-1}\mathrm{C}_{r-1}$
両辺をrで割ると
${}_n\mathrm{C}_r =\displaystyle\frac{n}{r}{}_{n-1}\mathrm{C}_{r-1}$
nにn+1、rにr+1を代入して
${}_{n+1}\mathrm{C}_{r+1}=\displaystyle\frac{n+1}{r+1} \ _n\mathrm{C}_r$
ｒが1増えた場合
${}_n\mathrm{C}_r$でもう一人選べたらn-r人から1人選べる。しかし、分母もr+1人増える
$\displaystyle{}_n\mathrm{C}_{r+1}=\frac{n-r}{r+1}{}_n\mathrm{C}_r$
rにr-1を代入して
$ \displaystyle{}_n\mathrm{C}_r= \frac{n-r+1}{r}{}_n\mathrm{C}_{r-1}$
nを1増やす
$\displaystyle{}_{n+1}\mathrm{C}_r= \frac{n+1}{n-r+1}{}_n\mathrm{C}_r$
$\displaystyle{}_n\mathrm{C}_r=\frac{n}{n-r}{}_{n-1}\mathrm{C}_r$
組み合わせの分割
特定の要素を選ぶ場合と選ばない場合に分ける
${}_n\mathrm{C}_r={}_{n-1}\mathrm{C}_r+{}_{n-1}\mathrm{C}_{r-1} \hspace{10px}(n \geqq 1)$
nを1増やす式を証明
$\displaystyle{}_n\mathrm{C}_r={}_{n-1}\mathrm{C}_r+{}_{n-1}\mathrm{C}_{r-1}={}_{n-1}\mathrm{C}_r+\frac{r}{n-r}{}_{n-1}\mathrm{C}_r=\frac{n}{n-r}{}_{n-1}\mathrm{C}_r$
$\displaystyle\because{}_{n-1} \mathrm{C}_{r}=\frac{n-r}{r}{}_{n-1} \mathrm{C}_{r-1}$
rを増やして累計（二項定理）
$(x+y)^n=\sum\limits_{r=0}^{n}{}_n \mathrm{C}_r\:x^{n-r}y^r=\sum\limits_{r=0}^{n}{}_n \mathrm{C}_r\;x^r y^{n-r}$
$2^n= \sum\limits_{k=0}^{n}{}_n\mathrm{C}_k={}_n\mathrm{C}_0+{}_n\mathrm{C}_1+{}_n\mathrm{C}_2+{}_n\mathrm{C}_3+\cdots{}_n\mathrm{C}_n$
$\sum\limits_{k=r}^{n}{}_k\mathrm{C}_r={}_{n+1}\mathrm{C}_{r+1}$
$\sum\limits_{k=0}^{n} {}_k\mathrm{C}_r={}_{n+1}\mathrm{C}_{r+1}$
$if n<r:→{}_k\mathrm{C}_r=0$
