Stanley 数え上げ組合せ論1 演習問題
1. [1-]
$S,T$を互いに素な$1$要素の集合としたとき、$S \cup T$の要素数は？
$2$.(それはそう)
2.[1+]
$\mathrm{(a)}$ $[10]$の部分集合であって少なくとも1つの奇数を含むものは何通り？
偶数と奇数別々に考えて良くて偶数の選び方は$2^5$通り,奇数の選び方は$2^5-1$通りあるから$2^5\cdot(2^5-1) = 992$通り
$\mathrm{(b)}$ $7$人の人を円環状の席に座らせる。各人の両隣が同じ場合同じ並べ方と見なす場合の座らせ方は何通り？
$1$の位置を固定して$6$人を円環状に座らせるのは$6!$通り。これは上の数え方でちょうど$2$回ずつ数えてしまっているから$6!/2 = 360$通り。
$\mathrm{(c)}$ 順列$ w : [6] \rightarrow [6]$で$w(1)\ne2$を満たすものは何通り？
順列全体は$6!$通りあり、そのうち$w(1) = 2$を満たすものは$5!$通りあるから$6!-5!= 600$通り
$\mathrm{(d)}$ $[6]$の順列でちょうど$2$つのサイクルを持つものは何通り？ なおこれは符号なし第1種スターリング数$c(n,k)$を用いて$c(6,2)$と表される。
標準表現で表すことを考える。(サイクル内の要素最大のものを最初に書き、各サイクルは要素最大のものの昇順に並べる。右上がり最大点(left-to-right maximum)の個数がサイクル数と一致する。) $[6]$の中から$i$$(1\le i < 6)$個選ぶ。このとき選んだ$i$個と選ばなかった$6-i$個でサイクルを作ると、標準表示で$2$つのサイクルの順序と、各サイクルの最初の要素は決まるので並べ方は$(i-1)!\cdot(6-i-1)!$通りある。$i$について和を取ると同じものを$2$回数えているから
\[\frac{1}{2}\sum_{i=1}^5 \begin{pmatrix} 6\\ i \end{pmatrix} (i-1)!\cdot(6-i-1)! = \begin{pmatrix}6\\1\end{pmatrix}4! + \begin{pmatrix}6\\2\end{pmatrix}3! + \frac{1}{2}\begin{pmatrix}6\\3\end{pmatrix}2!^2 = 274\]$274$通り。
$\mathrm{(e)}$ $[6]$の分割であってちょうど$3$ブロックになるものは何通り？なおこれは第2種スターリング数を用いて$S(6,3)$と表される。
$S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$と$S(n,1)=1$,$S(n,2)=2^{n-1}-1$,$S(n,n-1)= \binom{n}{2}$を用いて
\[\begin{align*} S(6,3) &= 3\cdot S(5,3)+S(5,2)\\ &=3^2\cdot S(4,3)+5\cdot S(4,2)+S(4,1)\\ &=9\cdot 6+5\cdot 7+1=90 \end{align*}\]$90$通り。
$\mathrm{(f)}$ $4$人の男と$6$人の女がいる。それぞれの男が$1$人の女と結婚するのは何通り？
$1$人目は$6$通り、$2$人目は$5$通り…となるから$(6)_4 = 360$通り
$\mathrm{(g)}$ $10$人をそれぞれ$2$人組の$5$グループに分ける方法は何通り？
人に番号をつける。人$1$と同じグループになる候補は$9$人。選ばれていない人の内番号が最小の人と同じグループになる候補は$7$人。同様に考えると$9!! = 945$通り。また、$10$人を一列に並べ端から$2$人ずつグループを作ると、グループ内の並べ方とグループごとの並べ方を余分に数えているから$10!/(2!^5\cdot 5!)$とも数えられる。
$\mathrm{(h)}$ $2$または$3$のみによる$19$のcompositionは何通り？($n$のcompositionとは$\sum_i \alpha_i = n$となる正整数列$\alpha=(\alpha_1,\dots,\alpha_k)$)
$2,3$の和として$19$を表す方法は$19 = 8\times 2+3$ $= 5\times 2 + 3\times 3$ $= 2\times 2 + 5\times 3$ があるので、$\binom{9}{8}+\binom{8}{5}+\binom{7}{2}=9+56+21=86 $通り。
$\mathrm{(i)}$ MISSISSIPPIを並び替える方法であって、$4$つのSが連続して現れないものは何通り？
並び替える方法は全部で$11!/4!^2 2! = 34650$通り。$4$つのSが連続して現れる方法は、$4$つのSを$1$文字とみなして$8!/4! 2!=840$通り。したがって$34650-840=33810$通り。
$\mathrm{(j)}$ $4$つの$0$,$8$つの$1$からなる列$(a_1,\dots,a_{12})$であって、$0$が隣り合わないものは何通り？
$0$をしきり、$1$をボールだと思うと$4$つのしきりと$8$つのボールを並べる方法であって、しきりの間に正の数のボールを置くものを数えれば良い。$1$つのボールを予め確保しておくと結局$4$つのしきりと、$5$個のボールを自由に並べる場合の数に帰着される。$\binom{9}{4}=126$通り。
$\mathrm{(k)}$ 箱の中に青い靴下が$3$つ、赤い靴下が$3$つ、黄緑色の靴下が$4$つある。$1$つずつ$8$つの靴下を取り出すとき、考えられる場合の数は？(ただし、同じ色の靴下は区別できない)
各色の靴下の数の候補としては$(3,3,2)$,$(3,2,3)$,$(3,1,4)$,$(2,3,3)$,$(2,2,4)$,$(1,3,4) $があるので
\[3\cdot\binom{8}{2,3,3}+2\cdot\binom{8}{1,3,4}+\binom{8}{2,2,4}=2660\]$2660$通り
$\mathrm{(l)}$ 関数$f:[5]\to [5] $であって高々$2$対$1$なもの、すなわち任意の$n\in[5]$について$ \text{#} f^{-1}(n)\le 2$が成り立つものは何通り？
$ \text{#} f^{-1}(n)$の多重集合として考えられるのは$\lbrace1,1,1,1,1\rbrace,\lbrace 2,1,1,1,0\rbrace,\lbrace 2,2,1,0,0\rbrace$の$3$通り。それぞれ$5!,\binom{5}{2}(5)_4,\frac{1}{2}\binom{5}{2,2,1}(5)_3$通り考えられるので$120+10\cdot 120+15\cdot60=2220$通り。
3.
次の恒等式に対し組合せ論的な証明を与えよ。ただし$x,y,n,a,b$は非負整数である。
\[\begin{flalign*} &\mathrm{(a)}[2-] \sum_{k=0}^{n}\binom{x+k}{k} = \binom{x+n+1}{n} & \end{flalign*}\]格子点 $(0,0)$ から $(x+1,n)$ へ移動することを考える。一回の操作では$x$座標または$y$座標の一方が$1$増加する点へ移動する。移動の方法は $\binom{x+n+1}{n}$ 通りある。これらを $x$座標が$x$ から $x+1$へ移動する際の $y$ 座標の値で分類する。それを $k$ とすると、$ 0 \le k \le n$ であり、$(0,0)$ から $(x,k)$ までは $\binom{x+k}{k}$ 通り、 $(x+1,k)$ から $(x+1,n)$ までは$1$通り存在する。従って移動の方法は $\sum_{k=0}^{n}\binom{x+k}{k}$ 通りとも表示できる。
[別の証明]
$[x+n+1]$ の要素数 $n$ の部分集合$S$が与えられたとき、 $ \# (S \cup [x+k]) = k $ となる最大の $k$ が存在する。 $k$ が与えられたとき、$S$ を $[x+k]$から $k$ 個と、$ \lbrace x+k+2,\dots, x+n+1 \rbrace $ を選ぶことにより構成できる。$k$ の定義から$x+k+1$ を選ばないことと、全体で$n$ 個選ぶことに注意する。
[fpsによる証明] $ \sum_{k = 0}^n \binom{n}{k} x^k = (1+x)^n $ を微分し、$x = 1$ を代入することで恒等式を得る。
[組合せ論的な証明] $[n]$ の部分集合$S$と$S$の要素$l$を選ぶことを考える。$ \#S = k $ であるような選び方は $k\binom{n}{k}$ 通りであるから、左辺を得る。要素$l$を固定すると、 $[n]\setminus \lbrace l\rbrace$ それぞれについて$S$に入れるかどうか$2$通りあるから右辺を得る。
[別の証明] 両辺を$2^n$で割る。これは$[n]$の部分集合の要素数の平均が$n/2$であることを表す式だが、各部分集合はその補集合とペアにできるため正しい。
\[\begin{flalign*} &\mathrm{(c)}[3] \sum_{k=0}^{n}\binom{2k}{k}\binom{2(n-k)}{n-k} = 4^n & \end{flalign*}\][fpsによる証明] $8.\mathrm{(a)}$で求めるように $\sum_{n\ge0}\binom{2n}{n}x^n = 1/\sqrt{1-4x} $である。 これを$f(x) =\sum_n f_n x^n $と置くと左辺から
\[[x^n]f(x)^2 = \sum_{k=0}^n f_k f_{n-k} = \sum_{k=0}^{n}\binom{2k}{k}\binom{2(n-k)}{n-k}\]また、右辺から
\[[x^n]f(x)^2 = [x^n]1/(1-4x) = 4^n\]したがって成り立つ。
[組合せ論的な証明] $(2n)! = 2^n n!(2n-1)!! $であるから、式は
\[\sum_{k=0}^n \binom{n}{k} (2k-1)!!(2(n-k)-1)!! = 2^n n!\]と変形できる。 これを証明する。$[n]$の部分集合$Y$に対し、$\pm Y=\lbrace i\in \mathbb{Z} :|k|\in Y \rbrace$ とする。$\pm Y$を頂点集合とする有向グラフであって、互いに交わりがなく全ての$\lbrace k,-k\rbrace$間に辺が存在するようなサイクルからなるものを考える。各$k$について、$\lbrace k,-k\rbrace$間の辺の張る向きを選ぶと、これは$2^n$通りある。$s(k) ,t(k) $を$\lbrace k,-k\rbrace$間の辺の始点と終点とする。$[n]$の順列$\pi$に対して、$t(k)$から$s(\pi(k))$への辺を張ると、これにより上記の有向グラフを構成できる。したがって$2^n n!$通りのグラフがある。さて、グラフの数を別の方法で数えてみよう。$[n]$の部分集合$Y$のペアリングを$\pm Y$の要素数$2$の集合たちへの分割とする。$[n]$のペアリング$\sigma$が$[n]$の部分集合$Y$と互換的であるとは、$|j| \in Y$かつ$\lbrace j,k \rbrace \in \sigma $ならば$|k|\in Y$が成り立つことをいう。$|Y|=i$のとき、$Y$と互換的な$[n]$のペアリングは($\pm Y$の分割が$(2i-1)!!$通り、$\pm ([n]\setminus Y)$の分割が$(2(n-i)-1)!!$通りあるから)$(2i-1)!! (2(n-i)-1)!! $通りある。グラフ上のサイクル$\gamma$に対し、$m(\gamma) = \min \lbrace |k| :k$は$\gamma$ 上の頂点$\rbrace $とする。$i$を$t(m(\gamma)) = m(\gamma) $となるようなサイクル$\gamma$に属する正の頂点数の個数とする。そのような正の頂点の集合を$Y$とすると、$\binom{n}{i} $通りの選び方がある。グラフから$k,-k$間の辺を削除すると、残った辺は$Y$と互換的な$[n]$のペアリングを定める。逆に$[n]$の部分集合$Y$と、$Y$と互換的な$[n]$のペアリング$\sigma$の組$(\sigma,Y) $から次のようにグラフを構成できる。まず$\min Y$を始点、$\min Y $とのペア$j$を終点とする辺を張る。次に$j$から$-j$への辺を張る。$-j$についても同様の操作を行い、サイクル$\gamma$ができるまで続ける。次に$\pm Y \setminus \gamma$について同様の操作を行い、$\pm Y$上の全ての頂点がサイクルに属するまで続ける。$[n]\setminus \pm Y$上の頂点についても、$-\min([n]-Y)$から初め同様の操作を行うことによりグラフを構成できる。 従ってグラフを$2$つの数え方をすることにより等式を証明できた。
\[\begin{flalign*} &\mathrm{(e)}[1] \quad 2\binom{2n-1}{n} = \binom{2n}{n} &\end{flalign*}\]式変形による証明は自明である。右辺は $[2n]$ から要素数 $n$ の部分集合$S$を選ぶ場合の数である。 $2n \in S$ の場合 $\binom{2n-1}{n-1}$ 通り, $2n \notin S$ の場合$\binom{2n-1}{n}$ 通りあるから左辺を得る。
4.[2]
$j,k \in \mathbb{Z}$について以下の式を示せ
\[\sum_{n \ge 0}\frac{(2n-j-k)!x^n}{(n-j)!(n-k)!(n-j-k)!n!} = \left[ \sum_{n\ge 0}\frac{x^n}{n!(n-j)!} \right] \left[ \sum_{n\ge 0}\frac{x^n}{n!(n-k)!} \right]\]ただし、分母に負の階乗が現れる項は$0$とする。
右辺は
\[\sum_{n\ge 0}\sum_{i = 0}^n \frac{x^n}{i!(i-j)!(n-i)!(n-i-k)!}\]と書ける。$n!(n-j-k)!$を掛けて整理すると、結局
\[\binom{2n-j-k}{n-k} = \sum_{i=0}^n \binom{n}{i}\binom{n-j-k}{n-i-k}\]を示せば良いが、これはExample 1.1.17で示したヴァンデルモンドの畳み込みである。
ところで、第1種変形ベッセル関数$I_j(x) = \sum_{n\ge 0}\frac{1}{n!(n+j)!}\left(x/2\right)^{2n+j} $を用いると
\[\sum_{n\ge 0}\frac{x^n}{n!(n-j)!} = x^{\frac{j}{2}}I_j\left(2\sqrt{x}\right)\]と書ける。（だから何？）
5.[2]
\[\sum_{n_1,\dots,n_k \ge 0} \min(n_1,\dots,n_k) x_1^{n_1} \cdots x_k^{n_k} = \frac{x_1 \cdots x_k}{(1-x_1)\cdots (1-x_k)(1-x_1 x_2 \cdots x_k)}\]を示せ。
右辺は
\[(1+x_1+x_1^2+\cdots)\cdots(1+x_k+x_k^2+\cdots)\left((x_1\cdots x_k) +(x_1\cdots x_k)^2 + \cdots \right)\]と表される。これを展開して$ x_1^{n_1} \cdots x_k^{n_k}$を作るには、最も右の括弧の前から$\min(n_1,\dots,n_k)$個までの項を選ぶ必要があり、ここを決めると他の項の選び方は一意に定まる。これを表現すると左辺になる。
7.[2]
\[e^{x+\frac{x^2}{2}} = \sum_{n \ge 0} f(n) \frac{x^n}{n!}\]とする。このとき$ \sum_{i = 0}^n (-1)^{n-i}\binom{n}{i}f(i) $を求めよ。
この式はEGF(指数型母関数)の合成の形になっている。
\[\begin{align*} \left(\sum_{n \ge 0} f(n) \frac{x^n}{n!}\right) \left(\sum_{n \ge 0} \frac{(-x)^n}{n!}\right) &= \sum_{n\ge 0}\sum_{i = 0}^n (-1)^{n-i} \binom{n}{i} f(i) \frac{x^n}{n!} \end{align*}\]ここで左辺は$ \exp(x+x^2/2) \exp(-x) = \exp(x^2/2) $ と表されるから求めるものは$n$が奇数のとき$0$、偶数のとき$\frac{2^{-n/2}}{(n/2)!}$となる。
8.
$\mathrm{(a)}[2-]$
\[\frac{1}{\sqrt{1-4x}} = \sum_{n\ge0}\binom{2n}{n}x^n\]を示せ。
\[\begin{align*} \frac{1}{\sqrt{1-4x}} &= \sum_{n\ge 0}\binom{-\frac{1}{2}}{n!}(-4x)^n \\ &= \sum_{n\ge 0}\frac{(2n-1)\cdot(2n-3)\cdot\cdots\cdot 1}{n!}(2x)^n\\ &= \sum_{n\ge 0}\frac{1}{n!} \frac{(2n)!}{(2n)!!}(2x)^n\\ &= \sum_{n\ge 0}\binom{2n}{n}x^n \end{align*}\]$\mathrm{(b)}[2-]$ $\sum_{n\ge 0}\binom{2n-1}{n}x^n$を求めよ。
$\binom{2n-1}{n}=\binom{2n}{n}/2 $より
\[\sum_{n\ge 0}\binom{2n-1}{n}x^n = \frac{1}{2\sqrt{1-4x}}\]9.
$f(m,n)$ を $(0,0)$ から $(m,n)\in \mathbb{N}\times \mathbb{N}$ まで$(1,0),(0,1),(1,1)$のステップで遷移するパスの場合の数とする。
$\mathrm{(a)}[1+]$
\[\sum_{m\ge 0}\sum_{n \ge 0}f(m,n)x^m y^n = (1-x-y-xy)^{-1}\]を示せ。
左辺は$1+(x+y+xy)+(x+y+xy)^2+\cdots$ と表されるから従う。
$\mathrm{(b)}[3-]$
$ \sum_{n\ge 0}f(n,n)x^n $ の簡潔でexplicitな式を求めよ。
$ x^n y^n = x^k y^k (xy)^{n-k} $ であるから
\[f(n,n) = \sum^n _{k = 0} \binom{n+k}{n-k,k,k}\]と表される。
\[\begin{align*} \sum_{n\ge 0}f(n,n)x^n &= \sum_{n\ge 0}\sum^n _{k = 0} \binom{n+k}{n-k,k,k}x^n \\ &= \sum_{n\ge 0}\sum^n _{k = 0}\binom{n+k}{2k}\binom{2k}{k}x^n \\ &= \sum_{k \ge 0}\binom{2k}{k}\sum_{n \ge k}\binom{n+k}{2k}x^n \\ &= \sum_{k\ge 0}\binom{2k}{k}x^k \sum_{n'\ge 0}\binom{n'+2k}{n'}x^{n'} \\ &= \sum_{k\ge 0}\binom{2k}{k} \frac{x^k}{(1-x)^{2k+1}} \\ &= \frac{1}{1-x} \sum_{k\ge 0}\binom{2k}{k} \left[ \frac{x}{(1-x)^2} \right]^k \\ &= \frac{1}{1-x} \left( 1-\frac{4x}{(1-x)^2} \right)^{-1/2} \\ &= \frac{1}{\sqrt{1-6x+x^2}} \end{align*}\]13.
$p$を素数とし、$a\in \mathbb{P}$とする。（$ \mathbb{P} $は正整数全体の成す集合）$a^p-a$が$p$で割り切れることを組合せ論的に示せ。
$p$組 $(n_1,\dots,n_p)$ であって、$n_i \in [a]$ かつ$n_i$ がすべて等しくはないようなもの全体からなる集合$S$を考える。ここで $\# S = a^p - a$ である。2つの組を、巡回シフトにより一方から他方へ変形出来るとき同一視する。$p$は素数であり、$S$ の要素はすべて等しくはないから、この同値関係により各同値類はちょうど$p$個の要素からなる。従って$p \mid \# S$ である。
20.[2]
各要素が$0$または$1$の$m \times n$行列であって、各行および列に$1$が偶数個あるものは何通り？奇数個の場合は？
$n+m-1$個の条件を満たしている場合、残りの条件は$n,m$の偶奇が異なり奇数個の$1$についての制約を考えているときのみ満たさない。従ってその場合$0$通りである。それ以外の場合について考える。$i$行$j$列$(1\le i < m$,$1\le j < n)$の要素を決めたとき、$i$行目$(1\le i < m)$の条件から$m$行$j$列$(1\le j<n)$の要素が、$j$列目$(1\le j < n)$の条件から$i$行$n$列$(1\le i<m)$の要素が一意に決まる。さらに、$m$行目の条件から$m$行$n$列の要素が一意に決まり、このとき$n$列目の条件も満たす。従って$i$行$j$列$(1\le i < m$,$1\le j < n)$の要素を決めるとちょうど一つの条件を満たす行列が存在する。従って$2^{(m-1)(n-1)}$通りある。
26.[2]
$\overline{c}(m,n)$を$n$の分割であって、最大のパートが高々$m$であるものの数とする。
\[\sum_{n \ge 0}\overline{c}(m,n)x^n = \frac{1-x}{1-2x+x^{m+1}}\]を示せ。
$\overline{c}(m,0) = 1$とする。$1\le n \le m$のとき$\overline{c}(m,n) = 2^{n-1}$である（$n$個のボールを一列に並べたとき、ボールの間に仕切りをいれるかどうかに対応）。$n > m$のとき、最後のボールの直前に仕切りを入れるとき$\overline{c}(m,n-1)$通り、入れないとき、最後のパートが$m+1$以上になる分を差し引いて$\overline{c}(m,n-1)-\overline{c}(m,n-m-1)$通りあるから$\overline{c}(n,m) =$ $ 2\overline{c}(m,n-1) - \overline{c}(m,n-m-1) $という漸化式が成り立つ。この漸化式から、母関数は上式になる。
29.[2]
$k,n \in \mathbb{P}$と、$n$の$k$パートのcomposition$(a_1,\dots,a_k)$について
\[\sum a_1 \cdots a_k = \binom{n+k-1}{2k-1}\]を示せ。
左辺は$[x^n] (0 + x + 2x^2 + \cdots)^k$と表される。 これを計算すると
\[\begin{align*} [x^n] (0 + x + 2x^2 + \cdots)^k &= [x^n] \left\lbrace x \left( \frac{1}{1-x} \right)' \right\rbrace ^k \\ &= [x^n] \frac{x^k}{(1-x)^{2k}} \\ &= [x^{n-k}] (1-x)^{-2k} \\ &= \binom{2k+n-k-1}{n-k} \\ &= \text{RHS} \end{align*}\]となる。
[組合せ論的な証明]
$n$個の白いボールを一列に並べる。ボール間の隙間に仕切りを入れ$k$個のグループに分け、各グループからちょうど一つのボールを黒く塗る操作を考えると、その場合の数は左辺と一致する。また、$n+k-1$個の白いボールを一列に並べ、$2k-1$個選ぶ。選ばれたボールを、左から黒いボール、仕切り、…、黒いボールと交互に変更していくと、この操作は上記の操作と一対一に対応するから場合の数は$\binom{n+k-1}{2k-1}$となる。