§D2.6分割と写像の数え上げ

証明.$\mathcal{S}$を$[n]$のちょうど$k$個のブロックからなる分割全体の集合とする。分割のブロックは互いに交わらず合併が$[n]$であるから、$\mathcal{P}\in\mathcal{S}$に対して$n$を含む$\mathcal{P}$のブロックはただ一つ定まる。そこで$\mathcal{S}_1$を$\{n\}$をブロックにもつ$\mathcal{P}\in\mathcal{S}$の全体、$\mathcal{S}_2$を$n$を含むブロックが二元以上である$\mathcal{P}\in\mathcal{S}$の全体とすると、$\mathcal{S}=\mathcal{S}_1\cup\mathcal{S}_2$かつ$\mathcal{S}_1\cap\mathcal{S}_2=\varnothing$である。

$\mathcal{P}\in\mathcal{S}_1$に$\mathcal{P}\setminus\{\{n\}\}$を対応させる写像は、$\mathcal{S}_1$から$[n-1]$のちょうど$k-1$個のブロックからなる分割全体への全単射である。逆写像は$\mathcal{Q}\mapsto\mathcal{Q}\cup\{\{n\}\}$で与えられる。ゆえに$|\mathcal{S}_1|=S(n-1,k-1)$である。

$[n-1]$のちょうど$k$個のブロックからなる分割$\mathcal{Q}$と、$\mathcal{Q}$のブロック$B$の組$(\mathcal{Q},B)$に、$\mathcal{Q}$の$B$を$B\cup\{n\}$で置き換えて得られる分割を対応させる写像は、そのような組の全体から$\mathcal{S}_2$への全単射である。逆写像は、$\mathcal{P}\in\mathcal{S}_2$の$n$を含むブロック$C$を$C\setminus\{n\}$で置き換えたものを$\mathcal{Q}$、$C\setminus\{n\}$を$B$とすることで与えられる。$\mathcal{Q}$の選び方は$S(n-1,k)$通り、$\mathcal{Q}$ごとに$B$の選び方は$k$通りであるから、§D2.2 定理 2.3により組の個数は$k\,S(n-1,k)$であり、$|\mathcal{S}_2|=k\,S(n-1,k)$である。

$\mathcal{S}_1$と$\mathcal{S}_2$は互いに素であるから、§D2.2 定理 2.1により$S(n,k)=|\mathcal{S}_1|+|\mathcal{S}_2|=S(n-1,k-1)+k\,S(n-1,k)$である。▨

証明.$E$を$[n]$から$[k]$への全射全体、$\mathcal{T}$を$[n]$のちょうど$k$個のブロックからなる分割全体とする。$f\in E$に対して

とおく。$f$は全射であるから、$\pi(f)$は$\mathcal{T}$の元である。任意の$\mathcal{P}\in\mathcal{T}$と全単射$h:\mathcal{P}\to[k]$に対し、$a\in[n]$を含む$\mathcal{P}$のブロックを$B_a$として$f_h(a)=h(B_a)$と定めると、$f_h\in E$かつ$\pi(f_h)=\mathcal{P}$である。逆に、$\pi(f)=\mathcal{P}$を満たす$f\in E$は、$B\in\mathcal{P}$上で一定である$f$の値を$h(B)$とする全単射$h:\mathcal{P}\to[k]$を定める。したがって$\pi:E\to\mathcal{T}$は全射であり、各$\mathcal{P}\in\mathcal{T}$の逆像は$\mathcal{P}$から$[k]$への全単射全体と一対一に対応するので、ちょうど$k!$個の元をもつ。

$k!$は正整数であるから、§D2.2 命題 2.2により$|E|=k!|\mathcal{T}|=k!S(n,k)$である。一方、§D2.3 命題 2.1により

である。二つの等式から結論を得る。▨

証明.§D2.5 系 2.6により$[n]$上の同値関係全体と$[n]$の分割全体は同じ元の個数をもち、定義 1.4により後者の個数は$B_n$である。▨

証明.$\mathcal{B}$を$[n+1]$の分割全体の集合とする。$\mathcal{P}\in\mathcal{B}$に対して$n+1$を含む$\mathcal{P}$のブロックを$C(\mathcal{P})$と書き、$e(\mathcal{P})=[n+1]\setminus C(\mathcal{P})$とおく。$n+1\in C(\mathcal{P})$であるから$e(\mathcal{P})\subseteq[n]$であり、$|e(\mathcal{P})|$は$0$以上$n$以下の整数である。$0\le k\le n$に対し$\mathcal{B}_k=\{\mathcal{P}\in\mathcal{B}\mid |e(\mathcal{P})|=k\}$とおくと、$\mathcal{B}$は$\mathcal{B}_0,\dots,\mathcal{B}_n$の互いに素な合併である。

$k$を固定する。$\mathcal{P}\in\mathcal{B}_k$に対し、$A=e(\mathcal{P})$と$\mathcal{Q}=\mathcal{P}\setminus\{C(\mathcal{P})\}$を対応させる。$\mathcal{Q}$のブロックは$C(\mathcal{P})$と交わらず、その合併は$A$であるから、$\mathcal{Q}$は$A$の分割である。逆に、$[n]$の$k$元部分集合$A$と$A$の分割$\mathcal{Q}$に対し$\mathcal{Q}\cup\{[n+1]\setminus A\}$とおくと、$[n+1]\setminus A$は$n+1$を含むので空でなく、これは$\mathcal{B}_k$の元であって、二つの対応は互いに逆である。ゆえに$\mathcal{B}_k$は、$[n]$の$k$元部分集合$A$と$A$の分割$\mathcal{Q}$の組$(A,\mathcal{Q})$全体と一対一に対応する。

$A$の選び方は§D2.2 命題 3.1により$\binom{n}{k}$通りであり、$A$ごとに$\mathcal{Q}$の選び方は、$A$が$k$元集合であることと定義 1.4により$B_k$通りである。§D2.2 定理 2.3により$|\mathcal{B}_k|=\binom{n}{k}B_k$である。$\mathcal{B}_0,\dots,\mathcal{B}_n$は互いに素であるから、§D2.2 定理 2.1により$B_{n+1}=|\mathcal{B}|=\sum_{k=0}^{n}\binom{n}{k}B_k$である。▨

証明. 全単射$u\colon N\to[n]$と$v\colon X\to[k]$をとる。$\Theta(f)=v\circ f\circ u^{-1}$は$N$から$X$への写像全体から$[n]$から$[k]$への写像全体への全単射であり、全単射との合成は単射性と全射性を変えないから、$\Theta$は単射を単射へ、全射を全射へ写す。また$g=\tau\circ f\circ\sigma$と$\Theta(g)=(v\tau v^{-1})\circ\Theta(f)\circ(u\sigma u^{-1})$は同値であり、$\sigma\mapsto u\sigma u^{-1}$は$N$の全単射全体から$[n]$の全単射全体への全単射、$\tau\mapsto v\tau v^{-1}$は$X$の全単射全体から$[k]$の全単射全体への全単射であるから、$\Theta$は三つの関係を両向きに保つ。よって主張の 12 個の個数は$n$と$k$だけで定まる。以下$N=[n]$、$X=[k]$とする。

$\sim_{N,X}$について、$\sigma$と$\tau$を恒等写像にとれば反射律が、$\sigma$と$\tau$を逆写像に取り替えれば対称律が、二組の全単射を合成すれば推移律が得られる。$\sim_N$は$\tau$を恒等写像に限った場合、$\sim_X$は$\sigma$を恒等写像に限った場合であり、同じ議論が通る。全単射との合成は単射性と全射性を変えないから、単射全体と全射全体はこの三つの同値関係で閉じている。

(1)を示す。$n=0$のとき$N\to X$の写像は空写像ただ一つであり、$k^{0}=1$である。$n\ge 1$かつ$k=0$のとき、$1\in N$の行き先が$X=\varnothing$に存在しないので写像はなく、$0^{n}=0$である。$n\ge 1$かつ$k\ge 1$のとき、$1,2,\dots,n$の行き先を順に選ぶ$n$段階の手続きは各段階で$X$の$k$個の元から一つを選ぶものであり、選択列$(f(1),\dots,f(n))$と写像$f$は一対一に対応する。§D2.2 定理 2.3により写像の個数は$k^{n}$である。

(2)を示す。$f$が単射ならば$f$は$N$から$f(N)$への全単射を与えるので$|f(N)|=n$であり、$f(N)\subseteq X$から$n\le k$が従う。ゆえに$n>k$のとき単射は存在せず、その個数は$0$である。$n\le k$のとき、単射$f$に列$(f(1),\dots,f(n))$を対応させると、これは$X$の$k$個の元から$n$個を選んで並べる順列と一対一に対応するから、§D2.2 命題 3.1により単射の個数は$\dfrac{k!}{(k-n)!}$である。

(3)を示す。$E$を全射$N\to X$全体、$\mathcal{T}$を$[n]$のちょうど$k$個のブロックからなる分割全体とする。$f\in E$に対し$\Phi(f)=\{f^{-1}(x)\mid x\in X\}$とおくと、$f$が全射であることから各$f^{-1}(x)$は空でなく、相異なる$x$の逆像は交わらず、その合併は$N$であり、また相異なる$x$の逆像は互いに異なるから、$\Phi(f)$はちょうど$k$個のブロックからなる$[n]$の分割である。$\mathcal{P}\in\mathcal{T}$を固定すると、$\Phi(f)=\mathcal{P}$を満たす$f\in E$は、$a\in N$の属するブロックを$B_a$として$f(a)=h(B_a)$と書くことにより、$\mathcal{P}$から$X$への全単射$h$と一対一に対応する。$\mathcal{P}$の元を並べて$B_1,\dots,B_k$とすると、そのような$h$は$X$の$k$個の元すべてを重複なく並べた列$(h(B_1),\dots,h(B_k))$と一対一に対応するから、§D2.2 命題 3.1によりその個数は$k!$である。とくに$\Phi\colon E\to\mathcal{T}$は全射であり、各$\mathcal{P}\in\mathcal{T}$の逆像はちょうど$k!$個の元をもつ。$k!$は正整数であるから、§D2.2 命題 2.2により$|E|=k!\,|\mathcal{T}|=k!\,S(n,k)$である。

$\sim_N$による同値類を数えるために、写像$f\colon N\to X$に対して各$x\in X$に$m_f(x)=|f^{-1}(x)|$を対応させる族$m_f$を考える。$N$は逆像$f^{-1}(x)$（$x\in X$）の互いに素な合併であるから、§D2.2 定理 2.1により$\sum_{x\in X}m_f(x)=n$である。$g=f\circ\sigma$ならば$g^{-1}(x)=\sigma^{-1}(f^{-1}(x))$であり$\sigma$は全単射であるから$m_g=m_f$である。逆に$m_f=m_g$とすると、各$x\in X$について全単射$\sigma_x\colon g^{-1}(x)\to f^{-1}(x)$がとれ、$N$が$g^{-1}(x)$（$x\in X$）の互いに素な合併であることからこれらを合わせた$\sigma\colon N\to N$は全単射であり、$a\in g^{-1}(x)$に対し$f(\sigma(a))=x=g(a)$となるので$g=f\circ\sigma$である。さらに、非負整数の族$(m_x)_{x\in X}$で$\sum_{x\in X}m_x=n$を満たすものが与えられたとき、$N$を$|A_x|=m_x$を満たす互いに素な部分集合$A_x$（$x\in X$）の合併に分け、$a\in A_x$に対し$f(a)=x$と定めれば$m_f=(m_x)_{x\in X}$である。ゆえに$f\mapsto m_f$は、$\sim_N$による同値類全体から、和が$n$である非負整数の族$(m_x)_{x\in X}$全体への全単射を与える。また$f$が単射であることは各$m_f(x)$が$1$以下であることと同値であり、$f$が全射であることは各$m_f(x)$が$1$以上であることと同値である。

(4)を示す。$k\ge 1$のとき、和が$n$である非負整数の族$(m_x)_{x\in X}$は、$X$の$k$種類の元から重複を許して$n$個を選ぶ選び方（元$x$を$m_x$回選ぶ）と一対一に対応するから、§D2.2 命題 4.1によりその個数は$\binom{k+n-1}{n}$である。$k=0$のときは族が空族に限り、その和は$0$であるから、$n=0$のとき個数は$1$、$n\ge 1$のとき個数は$0$である。他方$\binom{n-1}{n}$は、$n=0$のとき空積により$1$であり、$n\ge 1$のときは分子の積$(n-1)(n-2)\cdots 0$が因子$0$を含むので$0$である。いずれの場合も個数は$\binom{n+k-1}{n}$に等しい。

(5)を示す。各$m_x$が$1$以下で和が$n$である族$(m_x)_{x\in X}$は、$\{x\in X\mid m_x=1\}$により$X$の$n$元部分集合と一対一に対応する。$n\le k$のとき、§D2.2 命題 3.1によりその個数は$\binom{k}{n}$である。$n>k$のとき$X$は$n$元部分集合をもたないので個数は$0$であり、$\binom{k}{n}$の分子の積$k(k-1)\cdots(k-n+1)$は因子$0$を含むので$\binom{k}{n}=0$である。

(6)を示す。数える対象は、各$m_x$が$1$以上で和が$n$である族$(m_x)_{x\in X}$である。$k=0$のとき族は空族に限り、その和は$0$であるから、個数は$n=0$のとき$1$、$n\ge 1$のとき$0$である。$k\ge 1$かつ$n=0$のときは、$1$以上の$k$個の値の和は$k\ge 1$となって$0$にならないので個数は$0$である。$k\ge 1$かつ$n\ge 1$のとき、$m'_x=m_x-1$とおくと、対象は和が$n-k$である非負整数の族$(m'_x)_{x\in X}$と一対一に対応する。$n<k$ならば$n-k<0$であるからそのような族はなく個数は$0$であり、このとき$\binom{n-1}{k-1}$の分子の積$(n-1)(n-2)\cdots(n-k+1)$は$n-k+1\le 0\le n-1$より因子$0$を含むので$\binom{n-1}{k-1}=0$である。$n\ge k$ならば、§D2.2 命題 4.1によりその個数は$\binom{k+(n-k)-1}{n-k}=\binom{n-1}{n-k}$であり、§D2.2 命題 3.1の階乗による表示から$\binom{n-1}{n-k}=\binom{n-1}{k-1}$である。

$\sim_X$による同値類を数えるために、写像$f\colon N\to X$に対して$\Psi(f)=\{f^{-1}(x)\mid x\in X,\ f^{-1}(x)\ne\varnothing\}$とおく。$\Psi(f)$の元は空でなく互いに交わらず、その合併は$N$であるから、$\Psi(f)$は$N$の分割であり、そのブロックの個数は$|X|=k$以下である。$g=\tau\circ f$ならば$g^{-1}(x)=f^{-1}(\tau^{-1}(x))$であり$\tau$は全単射であるから$\Psi(g)=\Psi(f)$である。逆に$\Psi(f)=\Psi(g)$とする。$a,b\in N$に対し、$f(a)=f(b)$であることと$a,b$が$\Psi(f)$の同じブロックに属することは同値であり、$g$についても同様であるから、$\tau_0(f(a))=g(a)$という対応は$f(N)$上の写像として矛盾なく定まり、$f(N)$から$g(N)$への全単射である。$|X\setminus f(N)|=k-|\Psi(f)|=|X\setminus g(N)|$であるから、$X\setminus f(N)$から$X\setminus g(N)$への全単射をとって$\tau_0$と合わせれば全単射$\tau\colon X\to X$が得られ、$g=\tau\circ f$である。さらに、ブロックの個数が$k$以下の$N$の分割$\mathcal{P}$が与えられたとき、単射$h\colon\mathcal{P}\to X$をとり$a$の属するブロックを$B_a$として$f(a)=h(B_a)$と定めれば$\Psi(f)=\mathcal{P}$である。ゆえに$f\mapsto\Psi(f)$は、$\sim_X$による同値類全体から、ブロックの個数が$k$以下である$N$の分割全体への全単射を与える。また$f$が単射であることは$\Psi(f)$のすべてのブロックが一元集合であることと同値であり、$f$が全射であることは$\Psi(f)$のブロックの個数が$k$であることと同値である。

(7)を示す。ブロックの個数が$k$以下である$[n]$の分割をブロックの個数$j$で類別すると、§D2.2 定理 2.1とその個数の定義により、総数は$\sum_{j=0}^{k}S(n,j)$である。

(8)を示す。すべてのブロックが一元集合である$[n]$の分割は、一元集合の全体$\{\{a\}\mid a\in[n]\}$に限り、そのブロックの個数は$n$である。これがブロックの個数$k$以下という条件を満たすことと$n\le k$は同値であるから、求める個数は$[\,n\le k\,]$である。

(9)を示す。ブロックの個数がちょうど$k$である$[n]$の分割の個数は、定義により$S(n,k)$である。

$\sim_{N,X}$による同値類を数えるために、写像$f\colon N\to X$に対して$\Psi(f)$のブロックの大きさを大きい順に並べた列を$\lambda(f)$とおく。$\Psi(f)$のブロックは互いに素で合併が$N$であるから、§D2.2 定理 2.1により大きさの総和は$n$であり、$\lambda(f)$は部分の個数が$k$以下である$n$の整数の分割である。$g=\tau\circ f\circ\sigma$とすると、$\Psi(g)=\{\sigma^{-1}(B)\mid B\in\Psi(f)\}$であって$\sigma$は全単射であるから、$\Psi(g)$と$\Psi(f)$のブロックの大きさは重複を込めて一致し、$\lambda(g)=\lambda(f)$である。逆に$\lambda(f)=\lambda(g)=(\lambda_1,\dots,\lambda_r)$とする。$\Psi(f)$のブロックを大きさの大きい順に$F_1,\dots,F_r$、$\Psi(g)$のブロックを同様に$G_1,\dots,G_r$と並べると$|F_i|=|G_i|=\lambda_i$である。各$i$について全単射$G_i\to F_i$をとり、$\Psi(g)$が$N$の分割であることからこれらを合わせて全単射$\sigma\colon N\to N$を得る。$F_i=f^{-1}(x_i)$、$G_i=g^{-1}(y_i)$を満たす$X$の相異なる元$x_1,\dots,x_r$と相異なる元$y_1,\dots,y_r$をとると、$f\circ\sigma$は$G_i$の各元を$x_i$へ写す。$x_i\mapsto y_i$を$X$の全単射$\tau$へ延長すれば、$\tau\circ f\circ\sigma$は$G_i$の各元を$y_i$へ写すので$g=\tau\circ f\circ\sigma$である。さらに、部分の個数が$k$以下である$n$の整数の分割$(\lambda_1,\dots,\lambda_r)$が与えられたとき、$N$を大きさ$\lambda_1,\dots,\lambda_r$の互いに素な部分集合に分け、$X$の相異なる元$x_1,\dots,x_r$をとって$i$番目の部分集合の元を$x_i$へ写す写像$f$を定めれば$\lambda(f)=(\lambda_1,\dots,\lambda_r)$である。ゆえに$f\mapsto\lambda(f)$は、$\sim_{N,X}$による同値類全体から、部分の個数が$k$以下である$n$の整数の分割全体への全単射を与える。また$f$が単射であることは$\lambda(f)$のすべての部分が$1$であることと同値であり、$f$が全射であることは$\lambda(f)$の部分の個数が$k$であることと同値である。

(10)を示す。部分の個数が$k$以下である$n$の整数の分割の個数は、定義により$p_{\le k}(n)$である。

(11)を示す。すべての部分が$1$である$n$の整数の分割は、$1$を$n$個並べた列に限り、その部分の個数は$n$である。これが部分の個数$k$以下という条件を満たすことと$n\le k$は同値であるから、求める個数は$[\,n\le k\,]$である。