離散数学・組合せ論の問題

頂点 $h,v_1,v_2,\dots ,v_6$ からなり、辺集合が
$$\{v_1{v}_2,v_2{v}_3,v_3{v}_4,v_4{v}_5,v_5{v}_6,v_6{v}_1\}\cup \{h{v}_1,h{v}_2,\dots ,h{v}_6\}$$
である単純グラフ $W$（車輪グラフ）を考える。$k$ を正の整数とし、$W$ の $k$ 色以下による適切な彩色（各頂点に $k$ 色のいずれかを割り当て、辺で結ばれた 2 頂点が異なる色になるもの）の個数を $P_W(k)$ とする。$P_W(k)$ を $k$ の式で求めよ。

集合 $\{1,2,3,4,5,6,7\}$ からそれ自身への全単射（置換）$\sigma$ のうち、次の 2 つの条件をともに満たすものの個数を求めよ。

• すべての $i$ $(1\le i\le 7)$ について $\sigma (i)\ne i$
• すべての $i$ $(1\le i\le 6)$ について $\sigma (i)\ne i+1$

（たとえば $7$ 人の生徒 $1,\dots ,7$ が席替えをするとき、生徒 $i$ が元の席 $i$ にも右隣の席 $i+1$ にも座らないような座り方の数に当たる。席 $7$ の右隣は考えない。）

正の整数 $n$ に対し、集合 $\{1,2,\dots ,n\}$ 上の置換（$\{1,2,\dots ,n\}$ からそれ自身への全単射）$\sigma$ で、すべての $i(1\le i\le n)$ について $\sigma (i)\ne i$ を満たすもの（攪乱順列）の個数を $D_n$ とする。

包除原理を用いて、正の整数 $n$ について「$D_n$ が偶数であることと、$n$ が奇数であることは同値である」ことを証明せよ。

集合 $\{1,2,\dots ,10\}$ の分割（空でない互いに素なブロックへの分け方。ブロックの順序は区別しない）を考える。分割が非交差であるとは、$a<b<c<d$ を満たす $a,b,c,d\in \{1,\dots ,10\}$ で、$a,c$ が同じブロックに属し、$b,d$ がそれとは異なる同じブロックに属するようなものが存在しないことをいう。

$\{1,2,\dots ,10\}$ の非交差分割のうち、どのブロックも 2 個以上の要素を含む（要素 1 個だけのブロックを持たない）ものの個数を求めよ。

4 種類の文字 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}$ を使って、長さ $6$ の文字列を作る。同じ文字を何回使ってもよく、使わない文字があってもよい。このような文字列のうち、$4$ 種類の文字がすべて少なくとも $1$ 回ずつ現れるものの個数を求めよ。