設定
MOD
写像12相
$k$ 個の箱に $n$ 個のボールを入れる場合の数。箱を区別するか、ボールを区別するか、箱に入るボールの個数が $0, 1$ か $1$ 個以上か制限なしかで $12$ 種類ある。
k =
n =
箱
ボール
0, 1
制限なし
$1$ 個以上
区別する
区別する
{_k}{\rm P}{_n}
k^n
k! \left\{{n \atop k}\right\}
区別する
区別しない
{_k}{\rm C}{_n}
{_k}{\rm H}{_n}
{_{k - 1}}{\rm C}{_{n - 1}}
区別しない
区別する
k \ge n
B(n, k)
\left\{{n \atop k}\right\}
区別しない
区別しない
k \ge n
p_k(n)
p_k(n - k)
累乗
$n^r$ 累乗・重複順列: $O(\log r)$
n =
r =
n^r =
$n^{-1}$ 逆元: $O(\log r)$
n =
n^{-1} =
階乗
$n!$ 階乗: $O(n)$
n =
n! =
${_n}{\rm P}{_r}$ 順列: $O(r)$
n =
r =
{_n}{\rm P}{_r} =
${_n}{\rm C}{_r}$ 二項係数・組合せ: $O(r)$
n =
r =
{_n}{\rm C}{_r} =
${_n}{\rm H}{_r}$重複組合せ: $O(r)$
n =
r =
{_n}{\rm H}{_r} =
分割数
$p(n)$ 分割数(正整数 $n$ を $1$ 個以上の正整数の和で表す方法の数): $O(n^2)$
n =
p(n) =
$p_k(n)$ 正整数 $n$ を $k$ 個の正整数の和で表す方法の数: $O(nk)$
n =
k =
p_k(n) =
$p_{\le k}(n)$ 正整数 $n$ を $k$ 個
以下
の正整数の和で表す方法の数: $O(nk)$
n =
k =
p_{\le k}(n) =
ベル数
$B_n$ ベル数(区別できる $n$ 個のボールをいくつかのグループに分割する場合の数): $O(n \log n)$
n =
B_n =
$B(n, k)$ ベル数(区別できる $n$ 個のボールを区別できない $k$ 個以下の箱に分割する場合の数): $O(\min(n, k) \log n)$
n =
k =
B(n, k) =
スターリング数
$\left\{{n \atop k}\right\}$ 第2種スターリング数: $O(k \log n)$
n =
k =
\left\{{n \atop k}\right\} =
$k! \left\{{n \atop k}\right\}$ (区別できる $n$ 個のボールを区別できる $k$ 個の箱にそれぞれ $1$ 個以上振り分ける場合の数): $O(k \log n)$
n =
k =
k! \left\{{n \atop k}\right\} =