トピック 6： 累乗、順列、階乗

メモ

$`X, Y`$ を集合として、次のような記法を使う。$`\newcommand{\mrm}[1]{\mathrm{#1} }`$

  • $`\mrm{Map}(X, Y)`$ ： $`X`$ から $`Y`$ へのすべての写像の集合
  • $`\mrm{InjMap}(X, Y)`$ ： $`X`$ から $`Y`$ へのすべての単射写像の集合
  • $`\mrm{BijMap}(X, Y)`$ ： $`X`$ から $`Y`$ へのすべての双射〈全単射〉写像の集合

$`N, R`$ は有限集合として、その基数〈cardinality〉は小文字 $`n, r`$ とする。

$`\quad \mrm{card}(N) = n\\
\quad \mrm{card}(R) = r
`$

このとき：

  1. $`\mrm{card}(\mrm{Map}(R, N)) = n^r`$
  2. $`\mrm{card}(\mrm{InjMap}(R, N)) = n^{[r]} = {_n P_r}`$
  3. $`\mrm{card}(\mrm{BijMap}(N, N)) = n!`$

$`\mrm{Two}`$ を二元集合として、$`\mrm{Pow}(X) \cong \mrm{Map}(X, \mrm{Two})`$ だから、

  • $`\mrm{card}(\mrm{Pow}(N)) = \mrm{card}(\mrm{Map}(N, \mrm{Two})) = 2^n`$