一般の包除原理

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

4 種類の文字 $a,b,c,d$ から重複を許して 6 個を選び、1 列に並べて長さ 6 の文字列をつくる（たとえば $aabcdd$ や $dcbaab$ など）。このような文字列のうち、$a,b,c,d$ の 4 種類の文字がすべて少なくとも 1 回ずつ現れるものは何通りあるか。

4 組の夫婦、合計 8 人が横 1 列に並ぶ。8 人は互いに区別できるものとする。どの夫婦も隣り合わないような並び方は何通りあるか。

互いに区別できる 6 個の玉を、互いに区別できない 3 個の箱に入れる。どの箱にも少なくとも 1 個の玉が入るような入れ方は何通りあるか。

2 項関係記号 $R$ だけからなる一階の言語（等号を含む）を考える。台集合を $A=\{1,2,3,4\}$ に固定し、$R$ の解釈 $R^{\mathcal{M}}\subseteq A\times A$ を 1 つ定めるごとに構造 $\mathcal{M}=(A,R^{\mathcal{M}})$ が 1 つ定まるものとする（同型な構造でも $R^{\mathcal{M}}$ が異なれば別の構造として数える）。次の文 $\phi$ を考える。
$$\phi :\forall x\neg R(x,x)\wedge \forall x\forall y(R(x,y)\to R(y,x))\wedge \forall x\exists yR(x,y)$$
$\mathcal{M}\models \phi$ となる構造 $\mathcal{M}$（すなわち $R^{\mathcal{M}}$）の個数を求めよ。

$n$ を正の整数とし、$n$ 変数のブール関数とは写像 $f:\{0,1{\}}^n\to \{0,1\}$ のこととする。$f$ が第 $i$ 変数に本質的に依存するとは、ある $a_1,\dots ,a_{i-1},a_{i+1},\dots ,a_n\in \{0,1\}$ が存在して
$$f(a_1,\dots ,a_{i-1},0,a_{i+1},\dots ,a_n)\ne f(a_1,\dots ,a_{i-1},1,a_{i+1},\dots ,a_n)$$
となることをいう。

3 変数のブール関数 $f:\{0,1{\}}^3\to \{0,1\}$ のうち、3 つの変数 $x_1,x_2,x_3$ のすべてに本質的に依存するものの個数を求めよ。

正の整数 $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 ,8$ の $8$ 個の数を、それぞれちょうど $1$ 回ずつ使って左から右へ $1$ 列に並べる。このような並べ方 $8!$ 通りのうち、どの $i$ $(1\le i\le 7)$ についても「$i$ のすぐ右隣に $i+1$ がある」ことが起こらないものは何通りあるか。

集合 $\{1,2,3,4,5,6,7,8\}$ を、空でない $3$ つのブロックに分割する（ブロックの順序は区別しない）。そのうち、どのブロックも連続する $2$ つの整数 $i,i+1$ $(1\le i\le 7)$ を同時に含まないような分割は何通りあるか。

整数 $x_1,x_2,x_3,x_4$ の組 $(x_1,x_2,x_3,x_4)$ で、
$$x_1+x_2+x_3+x_4=20,0\le x_i\le 7(i=1,2,3,4)$$
を満たすものの個数を求めよ。

2 項関係記号 $R$ だけをもつ等号付きの一階の言語を考える。台集合を $A=\{1,2,3,4,5\}$ に固定する。部分集合 $S\subseteq A\times A$ を 1 つ選ぶごとに、$R$ を $S$ と解釈し、等号を $A$ 上の通常の等しさと解釈した構造 ${\mathcal{M}}_S=(A,S)$ が定まる。次の 4 つの文を考える。
$${\sigma }_1:\forall x\forall y(\neg (x=y)\to (R(x,y)\vee R(y,x)))$$
$${\sigma }_2:\forall x\forall y(R(x,y)\to \neg R(y,x))$$
$${\sigma }_3:\forall x\exists yR(x,y)$$
$${\sigma }_4:\forall x\exists yR(y,x)$$
${\mathcal{M}}_S\models {\sigma }_1\wedge {\sigma }_2\wedge {\sigma }_3\wedge {\sigma }_4$ となる部分集合 $S\subseteq A\times A$ は何個あるか。ただし、同型な構造であっても、$S$ が部分集合として異なれば別のものとして数える。

$99$ を、相異なる $3$ つの正の奇数の和として表す方法は何通りあるか。ただし、和の順序だけが異なるもの（たとえば $1+3+95$ と $95+3+1$）は同じ表し方とみなす。

集合 $\{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$ の右隣は考えない。）

頂点集合を $\{a,b,c,a^{\prime },b^{\prime },c^{\prime }\}$ とし、辺集合を
$$\{ab,bc,ca,a^{\prime }{b}^{\prime },b^{\prime }{c}^{\prime },c^{\prime }{a}^{\prime },a{a}^{\prime },b{b}^{\prime },c{c}^{\prime }\}$$
とする単純グラフ $G$（三角柱の頂点と辺がつくるグラフ）を考える。$k$ を正の整数とし、$k$ 色の中から各頂点に 1 色を割り当てる方法のうち、辺で結ばれた 2 頂点が必ず異なる色になるもの（適切な彩色）の個数を $P_G(k)$ とする。$P_G(k)$ を $k$ の多項式として求めよ。

集合 $\{1,2,3,4,5,6,7,8\}$ を、空でない 4 個の部分集合（ブロック）に分ける方法のうち、どのブロックも連続する 2 つの整数 $i,i+1$ ($1\le i\le 7$) を同時には含まないものは何通りあるか。ただし、ブロックの順序は区別しない。

$1,2,3,4,5,6,7$ を 1 列に並べる順列 $({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_7)$ のうち、どの $j$ ($1\le j\le 6$) についても ${\sigma }_{j+1}={\sigma }_j+1$ とならないもの、すなわち「ある整数 $i$ のすぐ右隣に $i+1$ が来る」箇所が 1 つもないものの個数を求めよ。

分割 $\lambda =(4,3,2,1)$ に対するシューア関数 $s_{\lambda }$ を単項対称関数 $m_{\mu }$ の一次結合で
$$s_{(4,3,2,1)}=\sum _{\mu ⊢10}{K}_{(4,3,2,1),\mu }{m}_{\mu }$$
と表す。このとき係数 $K_{(4,3,2,1),(2,2,2,2,2)}$（すなわち、形 $(4,3,2,1)$ で内容が $(2,2,2,2,2)$ の半標準ヤング盤の個数）を求めよ。