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{(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$つの数え方をすることにより等式を証明できた。
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}}\]