順列・組み合わせ(Permutation and combination)

ある事柄が何通りの起こり方があるかを考えるとき，その起こり方の個数を場合の数という．

番号のついた$n$個の異なったものをある規則のもとに順に並べたものを順列(permutation)といい，順列の総数を順列の数という．

• 順列 異なる$n$個のものから$r$個とって１列に並べる順列の数は

  $${}_{n}P_{r} = n(n-1)(n-2)\cdots (n-r+1) = \frac{n!}{(n-r)!}$$

  である．特に， ${}_{n}P_{n} = n!$，$0! = 1$とする．
• 重複順列 異なる$n$個のものから重複を許して$r$個とる順列の数は
  $${}_{n}\Pi_{r} = n^{r}$$

• 円順列 異なる$n$個のものを円形に並べる順列の数は
  $$(n-1)!$$

• 同じものを含む順列 $n$個のもののうち，$p$個，$q$個, $\ldots$, $r$個がそれぞれ同じであるとき，これらを１列に並べる順列の数は
  $${n \choose {p,q,\ldots,r}} = \frac{n!}{p! q! \cdots r!}, p+q+\cdots +r = n$$

並べる順序は考えずに，複数個から幾つか選んだ組を組合せ(combination)という．

• 組み合わせ 異なる$n$個のものから$r$個とる組み合わせの数は
  $${}_{n}C_{r} = \frac{n!}{r! (n-r)!}$$

  である．特に， ${}_{n}C_{0} = 1$， ${}_{n}C_{n} = 1$とする．

• 幾つかの組に分ける $n$個の物を，$p$個，$q$個, $\ldots$, $r$個の組に分ける組合せの数は
  $${n \choose {p,q,\ldots,r}} = \frac{n!}{p! q! \cdots r!}, p+q+\cdots +r = n$$

• 重複組合せ $n$個の異なるものから，繰り返しを許して，$r$個とるときの組合せの数は
  $${}_{n}H_{r} = \binom{n+r-1}{r} = \frac{n(n+1)\cdots(n+r-1)}{r!}$$

演習問題 1..1  

1. 0 から 6 までの7個の数字を取り出して並べるとき，次のような4けたの整数はいくつあるか求めよう．

(a)

すべての数字が異なる場合

(b)

5の倍数

(c)

同じ数字が重複してもよい場合

2. 1から10までの番号のついたカードから6枚を取り出すとき，次のような場合の数を求めよう．

(a)

すべての場合

(b)

1と2のカードを含む場合

(c)

1または2のカードを含む場合

3. 1枚の硬貨を5回投げるとき，次の場合は何通りあるか求めよう．

(a)

表の出る回数が0回，1回，2回，3回，4回，5回のそれぞれの場合

(b)

起こりえるすべての場合

4. $a,b,c,d,e,f$の文字を一列に並べるのに次の場合は何通りあるか求めよう．

(a)

$a,b$が隣あう場合

(b)

$a,b$が隣合わない場合

(c)

$a,b$が両端にくる場合

5. $a,a,a,a,b,b,c,d$の8個の文字を並べる順列の総数は ${8 \choose 4,2,1,1}$で与えられることを示せ．