順列

列 $(x_1,\ldots,x_k)\in X^k$ と写像 $\varphi\colon[k]\to X$（$\varphi(i)=x_i$）は、定義により同じデータであり、この対応は $X^k$ と写像全体の間の全単射である。成分が互いに相異なること（$i\neq j$ なら $x_i\neq x_j$）は、$\varphi$ が単射であることそのものである。$k=n$ のとき、$[n]$ から $n$ 元集合 $X$ への単射は、像が $n$ 個の元からなるので像が $X$ 全体となり、全単射である。逆に全単射は単射である。$\square$

1. $X$ の $k$-順列の全体を $A_k$ とし、$|A_k|=n^{\underline{k}}$ を $k$ についての帰納法で示す。$A_0$ は空の列だけなので $|A_0|=1=n^{\underline{0}}$ である。
$|A_k|=n^{\underline{k}}$ と仮定する。最後の成分を除く写像
$$ \pi\colon A_{k+1}\to A_k,\qquad(x_1,\ldots,x_k,x_{k+1})\mapsto(x_1,\ldots,x_k) $$
を考える。$(x_1,\ldots,x_k)\in A_k$ の逆像は、$y\in X\setminus\{x_1,\ldots,x_k\}$ による列 $(x_1,\ldots,x_k,y)$ の全体である。$x_1,\ldots,x_k$ は相異なるので $\{x_1,\ldots,x_k\}$ は $k$ 個の元からなり（このとき $k\le n$）、逆像は $n-k$ 個の元からなる。$A_{k+1}$ は $\pi$ の逆像の互いに交わらない和なので
$$ |A_{k+1}|=\sum_{s\in A_k}|\pi^{-1}(s)|=(n-k)\,|A_k|=(n-k)\,n^{\underline{k}}=n^{\underline{k+1}} $$
である。$A_k=\emptyset$ のときも両辺は $0$ で成り立つ。$k\le n$ のときの $n!/(n-k)!$ と $k> n$ のときの $0$ は、上で述べた $n^{\underline{k}}$ の値である。
2. 重複順列の全体を $B_k$ とし、同じく最後の成分を除く写像 $B_{k+1}\to B_k$ を考えると、各逆像は $y\in X$ による $(x_1,\ldots,x_k,y)$ の全体で $n$ 個の元からなる。よって $|B_{k+1}|=n|B_k|$、$|B_0|=1$ から $|B_k|=n^k$ である。$\square$

$k$-順列 $(x_1,\ldots,x_k)$ に、その成分の集合 $\{x_1,\ldots,x_k\}$ を対応させる写像 $\rho$ を考える。成分は相異なるので、これは $k$ 元部分集合である。$k$ 元部分集合 $T$ の逆像 $\rho^{-1}(T)$ は、$T$ の元をすべて一回ずつ並べた列、すなわち $T$ の並べ方の全体であり、thm-arr-count により $k!$ 個の元からなる。$k$-順列の全体は逆像の互いに交わらない和なので、$P(n,k)=(\text{$k$ 元部分集合の個数})\cdot k!$ である。$k$ 元部分集合の個数が $\binom{n}{k}$ である（二項係数）ので主張を得る。$\square$

1. $0$ でない多項式の根の個数は次数以下であり有限なので、無限個の根をもつ多項式は $0$ である。
2. $F(x,y)=\sum_jc_j(y)x^j$（$c_j$ は $y$ の多項式）と書く。$b\in\mathbb{N}$ を固定すると、$x$ の多項式 $F(x,b)=\sum_jc_j(b)x^j$ はすべての $a\in\mathbb{N}$ で $0$ になるので、1 から $0$ であり、各 $j$ で $c_j(b)=0$ となる。これがすべての $b\in\mathbb{N}$ で成り立つので、1 から $c_j=0$ であり、$F=0$ である。$\square$

$a,b\in\mathbb{N}$ とし、互いに交わらない集合 $A,B$ で $|A|=a$、$|B|=b$ となるものをとる。$A\cup B$ の $n$-順列 $(z_1,\ldots,z_n)$ を数える。thm-arr-count により、その個数は $(a+b)^{\underline{n}}$ である。
各 $n$-順列に、$A$ の元が置かれた位置の集合 $T:=\{i\in[n]\mid z_i\in A\}$ を対応させる。$|T|=k$ となる $T$ を一つ固定する。$T$ の元を小さい順に $i_1< \cdots< i_k$、$[n]\setminus T$ の元を小さい順に $j_1< \cdots< j_{n-k}$ とすると、位置の集合が $T$ である $n$-順列は、$A$ の $k$-順列 $(z_{i_1},\ldots,z_{i_k})$ と $B$ の $(n-k)$-順列 $(z_{j_1},\ldots,z_{j_{n-k}})$ の組と一対一に対応する。成分が相異なるという条件は、$A$ の側と $B$ の側で別々に課せば足りる（$A$ と $B$ は交わらない）からである。よってその個数は $a^{\underline{k}}\,b^{\underline{n-k}}$ であり、$|T|=k$ となる $T$ は $\binom{n}{k}$ 個ある。$k$ について和をとると、等式は $x=a$、$y=b$ を代入したときに成り立つ。$a,b\in\mathbb{N}$ は任意なので、lem-arr-polynomial の 2 から多項式として成り立つ。$\square$

$m\in\mathbb{N}$ とし、写像 $f\colon[n]\to[m]$ を数える。thm-arr-count の 2 によりその個数は $m^n$ である。
$f$ に対し、$f(i)=f(j)$ で定まる同値関係による $[n]$ の分割を考える。そのブロックの個数 $k$ は像 $f([n])$ の元の個数に等しい。ブロックを最小元の小さい順に $C_1,\ldots,C_k$ と並べ、$f$ が $C_r$ の上でとる値を $y_r$ とすると、相異なるブロックの値は相異なるので、$(y_1,\ldots,y_k)$ は $[m]$ の $k$-順列である。逆に、$[n]$ の $k$ ブロックへの分割と $[m]$ の $k$-順列 $(y_1,\ldots,y_k)$ が与えられれば、$C_r$ の元に $y_r$ を対応させる写像 $f$ がただ一つ定まり、その分割と順列はもとのものに戻る。よって写像全体は、$k=0,\ldots,n$ についての組（分割、$k$-順列）の全体と一対一に対応し、
$$ m^n=\sum_{k=0}^{n}S(n,k)\,m^{\underline{k}} $$
となる。$m\in\mathbb{N}$ は任意なので、lem-arr-polynomial の 1 から多項式として成り立つ。$\square$

まず、$j\cdot j!=(j+1)!-j!$ を $j=0,\ldots,N-1$ で足すと、差が打ち消し合って
$$ \sum_{j=0}^{N-1}j\cdot j!=N!-1\qquad(N\ge1) $$
を得る。
$n$ についての帰納法で示す。$n=1$ では $m=0$ で、$c_1=0$ の一通りである。$n\ge2$ とし、$m$ を $(n-1)!$ で割った商を $c_1$、余りを $r$ とする（$0\le r< (n-1)!$）。$m< n!=n\cdot(n-1)!$ より $c_1\le n-1$ である。帰納法の仮定を $r$ と $n-1$ に当てはめると、$r=\sum_{i=2}^{n}c_i(n-i)!$（$0\le c_i\le n-i$）と書けるので、存在が示された。
一意性：$m=\sum_{i=1}^nc_i(n-i)!$ が条件を満たす表示なら、上の和の公式から
$$ 0\le\sum_{i=2}^{n}c_i(n-i)!\le\sum_{i=2}^{n}(n-i)(n-i)!=\sum_{j=0}^{n-2}j\cdot j!=(n-1)!-1 $$
なので、$c_1$ は $m$ を $(n-1)!$ で割った商、残りの和は余り $r$ でなければならない。帰納法の仮定から $r$ の表示は一意なので、全体も一意である。$\square$

並べ方 $\tau=(b_1,\ldots,b_n)\neq\sigma$ が $\sigma$ より小さいのは、最初に成分が異なる位置 $i$ で $b_i< a_i$ となるときである。この位置 $i$ で分類する。位置 $i$ で初めて異なり $b_i< a_i$ となる $\tau$ は、$b_1=a_1,\ldots,b_{i-1}=a_{i-1}$ を満たし、$b_i$ は $a_1,\ldots,a_{i-1}$ 以外の元で $a_i$ より小さいもの、残りの $b_{i+1},\ldots,b_n$ は残った $n-i$ 個の元の並べ方である。$a_1,\ldots,a_{i-1}$ 以外の元は $a_i,a_{i+1},\ldots,a_n$ なので、$b_i$ の選び方は $\{a_j\mid j> i,\ a_j< a_i\}$ の $c_i$ 通りである。残りの並べ方は thm-arr-count により $(n-i)!$ 通りある。位置 $i$ ごとの分類は互いに交わらないので、個数は $\sum_ic_i(n-i)!$ である。
$c_i$ は位置 $i$ より右の $n-i$ 個の成分のうちのいくつかを数えるので $0\le c_i\le n-i$ である。辞書式順序は $n!$ 個の並べ方の上の全順序なので、小さい順に並べると、$\sigma$ より小さいものの個数 $\operatorname{rk}(\sigma)$ は $0,1,\ldots,n!-1$ をちょうど一回ずつとる。前半から $\operatorname{rk}(\sigma)=\sum_ic_i(n-i)!$ であり、lem-arr-factorial-base によりこの表示から $(c_1,\ldots,c_n)$ は一意に決まる。よって $(c_1,\ldots,c_n)$ から $\operatorname{rk}(\sigma)$ が決まり、$\sigma\mapsto\operatorname{rk}(\sigma)$ は単射なので、$\sigma\mapsto(c_i)$ は単射である。条件 $0\le c_i\le n-i$ を満たす組は $n\cdot(n-1)\cdots1=n!$ 個あり、並べ方も $n!$ 個なので、この単射は全単射である。$\square$