数え上げ組合せ論

3. $|A|=m$、$|B|=n$ とし、全単射 $\{1,\dots,m\}\to A\to B\to\{1,\dots,n\}$ を合成すれば $\{1,\dots,m\}$ と $\{1,\dots,n\}$ の間の全単射を得るので、要素数の一意性により $m=n$ である。
4. $|A|=m$、$|B|=n$ とし、全単射 $\varphi\colon\{1,\dots,m\}\to A$、$\psi\colon\{1,\dots,n\}\to B$ をとる。$\{1,\dots,m+n\}\to A\cup B$ を、$i\le m$ なら $\varphi(i)$、$i>m$ なら $\psi(i-m)$ と定めると、$A\cap B=\emptyset$ なのでこれは全単射である。一般の場合は集合の個数 $\ell$ に関する帰納法による。
5. $|A|=m$、$|B|=n$ とし、$\varphi,\psi$ を上と同じとする。$\{1,\dots,mn\}\to A\times B$ を、$i-1=(q-1)n+(r-1)$（$1\le q\le m$、$1\le r\le n$）と整数の除法で一意に表して $i\mapsto(\varphi(q),\psi(r))$ と定めると、除法の一意性により全単射である。$m=0$ または $n=0$ のときは両辺とも $0$ である。一般の場合は集合の個数 $\ell$ に関する帰納法による。$\square$

右辺を、各 $x\in A$ の寄与の和として書き直す。$|A_I|=\sum_{x\in A}\mathbf{1}_{A_I}(x)$ なので
$$\sum_{I\subset[m]}(-1)^{|I|}|A_I|=\sum_{x\in A}\sum_{I\subset[m]}(-1)^{|I|}\mathbf{1}_{A_I}(x)=\sum_{x\in A}\sum_{I\subset J(x)}(-1)^{|I|},$$
ここで $J(x):=\{i\in[m]\mid x\in A_i\}$ であり、$x\in A_I$ と $I\subset J(x)$ が同値であることを用いた。$J(x)=\emptyset$ なら内側の和は $1$（$I=\emptyset$ の項のみ）である。$J(x)\ne\emptyset$ なら $j_0\in J(x)$ を 1 つ固定し、$I\mapsto I\triangle\{j_0\}$（$j_0$ を含めば除き、含まなければ加える）を考えると、これは $J(x)$ の部分集合全体の上の全単射で $|I|$ の偶奇を変えるので、$\sum_{I\subset J(x)}(-1)^{|I|}=0$ である。よって右辺は $J(x)=\emptyset$ となる $x$、すなわちどの $A_i$ にも属さない $x$ の個数に等しい。$\square$

すべての $i$ で $|S_i|< n/m$ と仮定すると、次の矛盾を得る。
$$n\le|S|\le\sum_{i=1}^m|S_i|< m\cdot\frac{n}{m}=n.$$
ここで $|S|\le\sum|S_i|$ は、$S$ の各元が少なくとも 1 つの $S_i$ に属することによる。$\square$

$n=1$ では剰余列はすべて $0$ で $P_1=1$ である。$n\ge2$ とし、$v_i=(F_i\bmod n,\ F_{i+1}\bmod n)$ とおく。$v_0,\dots,v_{n^2}$ は $n^2$ 通りの状態の中の $n^2+1$ 個の組なので、thm-enumerative-combinatorics-cover（鳩の巣原理）により $0\le a< b\le n^2$ で $v_a=v_b$ となるものがある。状態遷移 $T(x,y)=(y,x+y)$ は法 $n$ で逆写像 $T^{-1}(u,v)=(v-u,u)$ をもつ。$v_a=v_b$ に逆遷移を $a$ 回施すと $v_0=v_{b-a}$ を得る。そこから同じ遷移を繰り返せば、すべての $i\ge0$ で $v_i=v_{i+b-a}$ となる。従って $b-a$ は剰余列の正周期であり、最小正周期も $b-a\le n^2$ 以下である。$\square$

頂点を巡回群 $G=\mathbb{Z}/432\mathbb{Z}$ で表し、各色の頂点集合を $V_R,V_W,V_B,V_Y$ とする。$U\subset G$ と $t\in G$ に対し $U[t]=\{u+t\mid u\in U\}$ とおく。任意の $U,W\subset G$ について、各組 $(u,w)\in U\times W$ に $u=w+t$ となる $t$ がただ 1 つ対応するので、次の二重計数が成り立つ。
$$\sum_{t\in G}|U\cap W[t]|=|U|\,|W|.$$
$V_R\cap V_W=\emptyset$ なので、$t\ne0$ の $431$ 個のシフトのどれか $i$ で $r:=|V_R\cap V_W[i]|\ge\lceil108^2/431\rceil=28$ となる（thm-enumerative-combinatorics-cover の考え方）。$U=V_R\cap V_W[i]$ とおくと $U\cap V_B=\emptyset$ なので、同様にある $j\ne0$ で $s:=|U\cap V_B[j]|\ge\lceil r\cdot108/431\rceil\ge8$ となる。$W=U\cap V_B[j]$ とおくと $W\cap V_Y=\emptyset$ なので、ある $k\ne0$ で $|W\cap V_Y[k]|\ge\lceil s\cdot108/431\rceil\ge3$ となる。この最後の共通部分から相異なる 3 点 $z_1,z_2,z_3$ をとる。$z_\ell$ は赤、$z_\ell-i$ は白、$z_\ell-j$ は青、$z_\ell-k$ は黄である（$\ell=1,2,3$）。各組の 3 点は円周上で相異なるため非退化であり、各シフトを戻す操作は回転なので 4 個の三角形は互いに合同である。$\square$

$[n+1]$ の $k$ ブロックへの分割を、元 $n+1$ の入り方で分ける。$\{n+1\}$ が単独でブロックをなすものは、残り $[n]$ の $k-1$ ブロックへの分割と 1 対 1 に対応し $S(n,k-1)$ 個ある。そうでないものは、$[n]$ の $k$ ブロックへの分割と、$n+1$ を入れるブロックの選択（$k$ 通り）の組と 1 対 1 に対応し、積の法則から $k\,S(n,k)$ 個ある。和の法則（prop-enum-sum-product-rule）により主張を得る。$\square$

全射 $f\colon[n]\to[k]$ に対し、ファイバー $f^{-1}(1),\dots,f^{-1}(k)$ は $[n]$ の $k$ ブロックへの分割（順序付き）を与える。逆に、$[n]$ の $k$ ブロックへの分割と、ブロックから $[k]$ への全単射（$k!$ 通り）を与えれば全射が 1 つ定まり、これらは互いに逆の対応である。積の法則により全射は $k!\,S(n,k)$ 個ある。
次に $A$ を写像 $[n]\to[k]$ 全体（$|A|=k^n$、積の法則）、$A_i:=\{f\mid i\notin f([n])\}$ とおく。$I\subset[k]$ に対し $A_I$ は $[n]$ から $[k]\setminus I$ への写像全体なので $|A_I|=(k-|I|)^n$ であり、全射全体は $A\setminus\bigcup_iA_i$ である。thm-enum-inclusion-exclusion を用い、$|I|=j$ の $I$ が $\binom{k}{j}$ 個あることから主張の式を得る。$\square$

$[n+1]$ の置換 $\sigma$ から $n+1$ を取り除く（$n+1$ が不動点ならその巡回置換を消し、そうでなければ $\sigma^{-1}(n+1)\mapsto\sigma(n+1)$ とつなぐ）と $[n]$ の置換 $\sigma'$ を得る。逆に $[n]$ の置換 $\sigma'$ から、$n+1$ を新しい不動点として加える（巡回置換の個数が 1 増える、$c(n,k-1)$ 通り）か、$n+1$ をある元 $a\in[n]$ の直後に挿入する（$\sigma(a)=n+1$、$\sigma(n+1)=\sigma'(a)$。巡回置換の個数は変わらず、$a$ の選び方は $n$ 通り）ことで、$k$ 個の巡回置換をもつ $[n+1]$ の置換がちょうど 1 回ずつ得られる。よって $c(n+1,k)=n\,c(n,k)+c(n,k-1)$ である。すべての置換は巡回置換の個数で分類されるので、和の法則から $\sum_kc(n,k)=n!$ である。$\square$

$(0,0)$ から $(n,n)$ への単位ステップの経路は、$2n$ ステップのうち上向きの $n$ ステップの位置を選ぶことで定まるので、全部で $\binom{2n}{n}$ 本ある。このうち Dyck 路でないもの（悪い経路）を数える。悪い経路は $y>x$ となる格子点を通り、ステップが単位なので直線 $y=x+1$ 上の点を通る。その最初の点を $P$ とし、$P$ より後の部分を直線 $y=x+1$ に関して折り返す（$(x,y)\mapsto(y-1,x+1)$、右ステップと上ステップが入れ替わる）と、$(0,0)$ から $(n-1,n+1)$ への経路で、直線 $y=x+1$ に最初に $P$ で到達するものが得られる。逆に $(0,0)$ から $(n-1,n+1)$ への任意の経路は、$y-x$ が $0$ から $2$ まで $\pm1$ ずつ変化するので直線 $y=x+1$ に到達し、最初の到達点より後を折り返せば悪い経路に戻る。この 2 つの対応は互いに逆なので、悪い経路の個数は $(0,0)$ から $(n-1,n+1)$ への経路の個数 $\binom{2n}{n+1}$ に等しい。よって $C_n=\binom{2n}{n}-\binom{2n}{n+1}$ である。
さらに $\binom{2n}{n+1}=\dfrac{(2n)!}{(n+1)!\,(n-1)!}=\dfrac{n}{n+1}\binom{2n}{n}$ なので $C_n=\bigl(1-\frac{n}{n+1}\bigr)\binom{2n}{n}=\frac{1}{n+1}\binom{2n}{n}$ である（$n=0$ では $\binom{0}{1}=0$ として成り立つ）。$\square$

長さ $n+1$ の Dyck 路 $\pi$ をとる。最初のステップは右向きである（上向きなら $(0,1)$ で $y>x$ になる）。$\pi$ が $(0,0)$ の後に最初に対角線上の点に到達する点を $(i+1,i+1)$（$0\le i\le n$）とする。その直前の点は $(i+1,i)$ である（$(i,i+1)$ は対角線より上）。$(1,0)$ から $(i+1,i)$ までの部分は対角線に触れないので、その格子点は $y\le x-1$ を満たし、$(-1,0)$ だけ平行移動すると長さ $i$ の Dyck 路になる。$(i+1,i+1)$ から $(n+1,n+1)$ までの部分は、平行移動すると長さ $n-i$ の Dyck 路である。逆に、長さ $i$ の Dyck 路 $\alpha$ と長さ $n-i$ の Dyck 路 $\beta$ から、「右、$\alpha$（$(1,0)$ だけ移動）、上、$\beta$（$(i+1,i+1)$ だけ移動）」とつなげば、最初の対角線復帰点が $(i+1,i+1)$ である長さ $n+1$ の Dyck 路がちょうど 1 つ得られる。積の法則と、$i$ に関する和の法則から主張を得る。$\square$

和の法則と積の法則（prop-enum-sum-product-rule）から $|Z_n|=\sum_{i+j=n}|X_i|\,|Y_j|=\sum_{i=0}^{n}a_ib_{n-i}$ であり、これは形式的冪級数の積 $A(t)B(t)$ の $t^n$ の係数の定義そのものである。$\square$

$p\not\le q$ では $0$ とし、対角では $\mu_P(p,p)=1$ とする。$p< q$ では次の再帰式を用いる。
$$\mu_P(p,q)=-\sum_{p\le r< q}\mu_P(p,r).$$
右辺の各区間 $[p,r]$ は $[p,q]$ より真に小さい有限集合なので、区間の要素数に関する帰納法で値が一意に定まる。こうして得られる値は整数であり、再帰式の移項により定義の区間和を満たす。従って存在し、同じ再帰を満たすどの関数も帰納法で一致する。$\square$

$a\not\le b$ ならある $i$ で $a_i\not\le b_i$ なので右辺は $0$ である。$a\le b$ では、右辺を $\nu(a,b)$ と書くと、有限区間の直積上の和を分離して次を得る。
$$\sum_{a\le c\le b}\nu(a,c)=\prod_{i=1}^r\Bigl(\sum_{a_i\le c_i\le b_i}\mu_{P_i}(a_i,c_i)\Bigr)=\prod_{i=1}^r\delta_{a_i,b_i}=\delta_{a,b}.$$
よって Möbius 関数の一意性（prop-enumerative-combinatorics-mobius-existence）により主張が従う。$\square$

$a,b$ の非零座標の合併を $J$ とすると、$[a,b]$ の各列は $J$ の外で $0$ である。従ってこの区間は $\prod_{i\in J}[a_i,b_i]$ と順序同型であり、鎖の値（ex-enumerative-combinatorics-chain）と直積の公式（prop-enum-mobius-product）を適用すればよい。$J=\emptyset$ の場合も区間は一点で、値は $1$ になる。$\square$

上の明示式の右辺を候補関数とし、区間和の条件を直接調べる。$a=b$ のときは $k=0$ で値 $1$ なので、対角の条件を満たす。$a< b$ とし、$b_t>a_t$ となる最大の添字 $t$ をとる。$t$ より大きい座標は区間内で $a_i=b_i$ に固定される。$0\le i< t$ の座標 $c_i$ を固定して、第 $t$ 座標を $a_t$ から $b_t$ まで動かす。先の座標に $c_i-a_i\ge2$ があれば、候補関数の値は第 $t$ 座標によらずすべて $0$ である。そうでなければ、$c_t=a_t$ と $c_t=a_t+1$ の項だけが非零になり、この 2 項は反対符号をもつ。従って固定した先の座標ごとの和は $0$ であり、それらを足した区間全体の和も $0$ である。比較不能対の値 $0$ と合わせると、候補は定義を満たし、一意性により Möbius 関数である。$\square$

まずすべての差が $0$ または $1$ の場合を、差が $1$ の座標数 $k$ で帰納する。$k=0$ は対角値 $1=(-1)^0$ である。$k\ge1$ のとき、区間内の $c$ は差座標集合の部分集合 $U=\{i\mid c_i=a_i+1\}$ に対応する。$|U|=r$ の $c$ は $\binom{k}{r}$ 個であり、$U$ が真部分集合なら帰納法により $\mu(a,c)=(-1)^r$ である。再帰式と二項定理（二項係数の記事）を用いると、次を得る。
$$\mu(a,b)=-\sum_{r=0}^{k-1}\binom{k}{r}(-1)^r=(-1)^k.$$
次に差が $2$ 以上の座標がある場合を、有限な総差 $d=\sum_i(b_i-a_i)$ で強い帰納法により扱う。$d=2$ のこの場合は差が $2$ の座標が 1 つだけなので、鎖の再帰から値は $0$ である。一般に $c_i=a_i+\min(1,b_i-a_i)$ とおき、$[a,b]$ のうち $a\le u\le c$ でない点の集合を $U$ とする。$a< c$ で、$[a,c]$ の和は、先に求めた $0/1$ 差の場合の二項展開により $0$ になる。$u\in U$ なら少なくとも 1 つの座標で $u_i-a_i\ge2$ である。さらに $u\ne b$ なら $\sum_i(u_i-a_i)< d$ なので、帰納法により $\mu(a,u)=0$ である。従って定義の和を $[a,c]$ と $U$ に分けると、$0=0+\mu(a,b)$ となり、求める値は $0$ である。この二段の計算は、符号相殺の証明とは別に、再帰式が明示式を強制することを示す。$\square$

各 $x\in A$ について $\sum_{p_0\le q\le f(x)}\mu_P(p_0,q)=\delta_{p_0,f(x)}$ である。$\bigcup_{x\in A}[p_0,f(x)]$ は有限なので、この等式を $x$ について足して有限和の順序を交換できる。
$$\sum_{x\in A}\delta_{p_0,f(x)}=\sum_{x\in A}\sum_{p_0\le q\le f(x)}\mu_P(p_0,q)=\sum_{q\ge p_0}\mu_P(p_0,q)\sum_{\substack{x\in A\\ q\le f(x)}}1.$$
これが求める式である。$\square$

$J$ の有限性と $J$ の外の集合が空であることは、直前の定義から従う（$A$ が有限で各点に対する添字が有限個だから）。従って thm-enum-inclusion-exclusion を、添字が $J$ の有限族へ適用すればよい。Möbius 関数との対応を直接見るには、$P=\{0,1\}^{<\infty}$ と $f(x)=(\mathbf{1}_{S_i}(x))_{i\ge1}$、$p_0=0$ を使う。$q$ の台 $I=\{i\mid q_i=1\}$ に対して、$q\le f(x)$ は $x\in S_I$ と同値であり、$\mu_P(0,q)=(-1)^{|I|}$ である。そこで thm-enumerative-combinatorics-poset-count を使っても同じ等式が得られる。$\square$