離散数学・組合せ論

区別のつかない $8$ 個の玉を、$\text{A},\text{B},\text{C},\text{D}$ の $4$ 人に配る。$1$ 個ももらわない人がいてもよいが、$\text{A}$ がもらう玉の個数は $2$ 個以下とする。すべての玉を配りきるとき、配り方の総数を求めよ。

ある店では、チョコレート・クッキー・キャンディ・ゼリーの 4 種類のお菓子を売っている。同じ種類のお菓子は区別しない。ゼリーは残りが 1 個しかなく、ほかの 3 種類は十分な数がある。この 4 種類から合わせて 8 個を選ぶ選び方は何通りあるか。ただし、選ばない種類があってもよい。

りんご・みかん・ももの 3 種類の果物から、合わせて 9 個を選んで袋に詰める。同じ種類の果物は区別しない。どの果物も十分な個数があり、選ばない種類があってもよい。ただし、ももは 2 個以下しか選べない。このような選び方は何通りあるか。母関数を用いて求めよ。

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 人は互いに区別できるものとする。どの夫婦も隣り合わないような並び方は何通りあるか。

横一列に並んだ $7$ つの席に、左から順に $1$ 番から $7$ 番までの $7$ 人の生徒が $1$ 人ずつ座っている。この $7$ 人を $4$ つのチームに分ける。ただし、次の条件を満たすようにする。

• どのチームにも少なくとも $1$ 人が入る。
• チームどうしは区別しない（だれとだれが同じチームかだけを考える）。
• 隣り合う席に座っている $2$ 人（$i$ 番と $i+1$ 番、$1\le i\le 6$）は、同じチームに入らない。

このようなチームの分け方は何通りあるか。

横一列に並んだ $7$ つの席に、$7$ 人が $1$ 人ずつ座っている。左から $i$ 番目の席の人を $P_i$ $(1\le i\le 7)$ とする。この $7$ 人全員を、空でない $4$ つのグループに分ける（グループどうしは区別しない）。ただし、隣り合う席の $2$ 人 $P_i,P_{i+1}$ $(1\le i\le 6)$ は同じグループに入れないものとする。このような分け方は何通りあるか。

区別できる $7$ 人を、区別しない $3$ つのグループに分ける。どのグループも $1$ 人以上とする。$7$ 人のうちの $1$ 人である A さんが「自分 $1$ 人だけのグループ」にならないような分け方は何通りあるか。

$x$ の多項式
$$x(x+1)(x+2)(x+3)(x+4)$$
を展開したときの $x^2$ の係数を求めよ。

5 人 $A,B,C,D,E$ を、区別のない 2 つの円卓に分けて座らせる。どちらの円卓にも 1 人以上が座り、5 人全員がどちらかの円卓に座るものとする。各円卓では、回転して一致する座り方は同じとみなす。時計回りに見た並び順が異なる座り方は異なるものとする（裏返して一致しても同じとはみなさない）。このような座り方は全部で何通りあるか。

集合 $\{1,2,3,4,5\}$ の置換（$\{1,2,3,4,5\}$ から自分自身への全単射）$\sigma$ を、互いに素な巡回置換の積に分解する。ただし、不動点も長さ $1$ の巡回として数える。巡回の個数がちょうど $2$ 個であるような置換 $\sigma$ の個数を求めよ。

座標平面上で、原点 $(0,0)$ から点 $(6,6)$ まで、1 歩ごとに $x$ 軸の正の向きに $1$ 進む（右へ $1$）か、$y$ 軸の正の向きに $1$ 進む（上へ $1$）かのどちらかで進む最短経路を考える。このうち、経路上のすべての格子点 $(x,y)$ が $y\le x$ を満たすもの（直線 $y=x$ より上側に一度も出ないもの）の個数を求めよ。

座標平面上で、原点 $(0,0)$ から点 $(5,5)$ まで、1 歩ごとに $x$ 軸の正の向きに $1$ 進むか、$y$ 軸の正の向きに $1$ 進むかのどちらかで移動する経路（最短経路）を考える。このうち、途中で通る格子点 $(x,y)$ がすべて $y\le x$ を満たす経路は何通りあるか求めよ。

ある窓口で 1 枚 500 円の券を売っている。窓口に並んだ 10 人の客のうち、5 人は 500 円硬貨 1 枚で支払い、残りの 5 人は 1000 円札 1 枚で支払う。1000 円札で支払う客には、その場で 500 円硬貨 1 枚のおつりを渡す。窓口のレジには、はじめ硬貨が 1 枚も入っていない。客を区別せず、10 人の支払い方の並び（500 円硬貨を A、1000 円札を B として、A を 5 個、B を 5 個並べた長さ 10 の列）だけを考えるとき、どの客にも必ずおつりを渡せるような並びは何通りあるか求めよ。

正六角形の板の $6$ つの頂点のそれぞれを、赤・青・白の $3$ 色のうちいずれか $1$ 色で塗る（使わない色があってもよい）。板を中心のまわりに回転して互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

円板を中心から $6$ 等分して、$6$ 個の合同な扇形をつくる。それぞれの扇形を白か黒のどちらか $1$ 色で塗る（どちらかの色を使わなくてもよい）。円板を中心のまわりに回転して重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、円板の裏返しによる同一視は行わない。

正方形の $4$ つの頂点のそれぞれを、赤・青・黄の $3$ 色のうちいずれか $1$ 色で塗る（使わない色があってもよい）。正方形をその中心のまわりに回転させて互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

頂点集合を $\{1,2,3,4\}$、辺集合を $\{\{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\}\}$ とする単純グラフ $G$ を考える。$G$ のラプラシアン行列 $L=D-A$（$D$ は次数行列、$A$ は隣接行列）を用いて、行列木定理により $G$ の全域木の個数を求めよ。

頂点集合を $\{1,2,3,4\}$、辺集合を
$$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\},\{1,3\}\}$$
とする単純グラフを $G$ とする。$G$ のラプラシアン行列 $L=D-A$（$D$ は次数行列、$A$ は隣接行列）を用い、行列木定理によって $G$ の全域木の個数を求めよ。

頂点集合を $\{1,2,3,4\}$、辺集合を
$$\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{3,4\}\}$$
とする単純グラフ $G$ を考える。行列木定理を用いて、$G$ の全域木の個数を求めよ。

頂点集合を $\{a,b,c,d\}$、辺集合を $$\{ab,bc,cd,da,ac\}$$ とする単純グラフ $G$ を考える。$G$ は長さ $4$ の閉路 $abcd$ に対角線 $ac$ を 1 本加えたグラフである。$k$ を正の整数とし、$G$ の頂点を $k$ 色以下で塗り分ける方法の数を $P_G(k)$ とする。ここで「塗り分ける」とは、辺で結ばれた 2 頂点が異なる色になるように、各頂点に $k$ 色のうちの 1 色を割り当てることであり、色は区別する（使わない色があってもよい）。彩色多項式 $P_G(k)$ を $k$ の式で求めよ。

頂点集合を $\{a,b,c,d\}$ とし、辺集合を
$$\{ab,bc,cd,da,ac\}$$
とする単純グラフ $G$ を考える。$k$ を正の整数とする。区別のつく $k$ 色を使い、辺で結ばれた 2 頂点が異なる色になるように $G$ の各頂点を塗る方法の数（すべての色を使う必要はない）を $P_G(k)$ とする。$P_G(k)$ を $k$ の式で表せ。

頂点集合を $\{a,b,c,d\}$ とし、辺集合を
$$\{ab,bc,cd,da,ac\}$$
とする単純グラフ $G$（正方形 $abcd$ に対角線 $ac$ を加えたグラフ）を考える。$k$ を正の整数とし、$k$ 色以下を使って $G$ の各頂点に色を塗る。辺で結ばれた $2$ 頂点が必ず異なる色になる塗り方の総数を $P_G(k)$ とする（色は区別し、使わない色があってもよい）。彩色多項式 $P_G(k)$ を $k$ の式で求めよ。

0 以上の整数 $n$ に対して、数列 $\{a_n\}$ を
$$a_0=2,a_1=5,a_n=5a_{n-1}-6a_{n-2}(n\ge 2)$$
で定める。母関数 $A(x)=\sum _{n=0}^{\infty }{a}_n{x}^n$ を $x$ の有理式で表し、部分分数分解することで、一般項 $a_n$ を $n$ の式で求めよ。

0 以上の整数 $n$ に対して、数列 $\{a_n\}$ を
$$a_0=1,a_1=4,a_n=5a_{n-1}-6a_{n-2}(n\ge 2)$$
で定める。母関数 $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ を用いて、一般項 $a_n$ を $n$ の式で求めよ。

0 以上の整数 $n$ に対して、数列 $\{a_n\}$ を
$$a_0=2,a_1=1,a_n=a_{n-1}+6a_{n-2}(n\ge 2)$$
で定める。母関数 $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ を用いて、一般項 $a_n$ を $n$ の式で求めよ。

数列 $\{a_n{\}}_{n\ge 0}$ を
$$a_0=1,a_n=\sum _{k=1}^{n}k{a}_{n-k}(n\ge 1)$$
で定める。無限級数
$$\sum _{n=0}^{\infty }\frac{a_n}{4^n}$$
の値を求めよ。ただし、この級数が収束することは認めてよい。

数列 $\{a_n{\}}_{n\ge 0}$ を
$$a_0=1,a_n=\sum _{k=1}^{n}k{a}_{n-k}(n\ge 1)$$
で定める。無限級数
$$\sum _{n=0}^{\infty }\frac{a_n}{4^n}$$
は収束する。その和を求めよ。

数列 $\{a_n{\}}_{n\ge 0}$ を次のように定める。$$a_0=1,a_n=\sum _{k=1}^{n}k{a}_{n-k}(n\ge 1)$$ このとき、無限級数 $$\sum _{n=0}^{\infty }\frac{a_n}{4^n}$$ は収束する。その和を求めよ。

正の整数 $n$ を、順序を考えずに正の整数の和として表したものを $n$ の分割という（例えば $4$ の分割は $4,3+1,2+2,2+1+1,1+1+1+1$ の $5$ 個）。$8$ の分割のうち、どの部分も $3$ 以下であるものの個数を求めよ。ただし、母関数
$$\frac{1}{(1-x)(1-x^2)(1-x^3)}$$
の $x^8$ の係数として求めること。

正の整数 $n$ を、順序を考えずに正の整数の和として表す方法を $n$ の分割といい、その個数を $p(n)$ で表す。たとえば $4=3+1=2+2=2+1+1=1+1+1+1$ より $p(4)=5$ である（$4$ そのものも 1 つの分割として数える）。$p(n)$ は母関数
$$\prod _{k=1}^{\infty }\frac{1}{1-x^k}=\sum _{n=0}^{\infty }p(n)x^n$$
の $x^n$ の係数でもある。$p(7)$ を求めよ。

正の整数 $n$ を、順序を考えずに 1 個以上の正の整数の和として表したものを $n$ の分割といい、分割の個数を $p(n)$ で表す。たとえば $4=3+1=2+2=2+1+1=1+1+1+1$ より $p(4)=5$ である。分割数の母関数は
$$\sum _{n\ge 0}p(n)x^n=\prod _{k\ge 1}\frac{1}{1-x^k}(p(0)=1)$$
で与えられる。$p(7)$ を求めよ。

$1$ から $6$ までの番号がついた $6$ 通の手紙と、同じく $1$ から $6$ までの番号がついた $6$ 枚の封筒がある。各封筒に手紙をちょうど $1$ 通ずつ入れる。どの手紙も、自分と同じ番号の封筒に入らないような入れ方は何通りあるか。

5 人がそれぞれ 1 つずつプレゼントを持ち寄り、5 個のプレゼントを 5 人に 1 個ずつ配り直す。どの人も自分が持ってきたプレゼントを受け取らないような配り方は何通りあるか求めよ。

$6$ 人がそれぞれ宛先の異なる手紙を $1$ 通ずつ書き、宛名を書いた封筒も $6$ 枚用意した。$6$ 通の手紙を $6$ 枚の封筒に $1$ 通ずつ入れるとき、どの手紙も正しい宛名の封筒に入らない入れ方は何通りあるか求めよ。

正方形の $4$ つの頂点を、赤・青・緑の $3$ 色のうちどれか $1$ 色で塗る。使わない色があってもよく、同じ色を何回使ってもよい。正方形の中心のまわりの回転（$0^{\circ },90^{\circ },180^{\circ },270^{\circ }$）で重なる塗り方は同じものとみなす。

回転の群が頂点に引き起こす置換の巡回指数 $Z(s_1,s_2,s_3,s_4)$ を作り、それを用いて異なる塗り方の総数を求めよ。

正六角形の 6 つの頂点に、赤または青のどちらか 1 色を塗る。赤を 3 個、青を 3 個塗る塗り方は何通りあるか。ただし、正六角形の中心のまわりの回転（$0^{\circ },60^{\circ },120^{\circ },180^{\circ },240^{\circ },300^{\circ }$ の 6 通り）で重なる塗り方は同じものとみなし、裏返しは考えない。巡回指数を用いて求めよ。

正方形の $4$ つの頂点のそれぞれに、赤・青・緑の $3$ 色のうちどれか $1$ 色を塗る（使わない色があってもよい）。正方形の中心のまわりの回転（$0^{\circ },90^{\circ },180^{\circ },270^{\circ }$）で互いに重なる塗り方は同じものとみなし、裏返しで重なるものは区別する。頂点に引き起こされる置換の巡回指数を作り、それを用いて異なる塗り方の総数を求めよ。

4 人 $A,B,C,D$ に、4 つの仕事 $1,2,3,4$ を 1 人に 1 つずつ割り当てる（どの仕事もちょうど 1 人に割り当てる）。ただし、次の割り当ては禁止されている。

• $A$ は仕事 $1$ と仕事 $2$ を担当できない。
• $B$ は仕事 $2$ を担当できない。
• $C$ は仕事 $3$ と仕事 $4$ を担当できない。
• $D$ は仕事 $4$ を担当できない。

禁止された割り当てを 1 つも含まない割り当て方は何通りあるか。行を人 $A,B,C,D$、列を仕事 $1,2,3,4$ とする $4\times 4$ の盤で、禁止されたマスの集まりを盤 $B$ とみなし、そのルーク数 $r_k$ を用いて求めよ。

4 人の学生 A, B, C, D に、4 つの係 $1,2,3,4$ を 1 人 1 つずつ割り当てる（どの係もちょうど 1 人が担当する）。ただし、次の割り当ては禁止されている。

• A は係 $1$ と係 $2$ を担当できない。
• B は係 $2$ を担当できない。
• C は係 $3$ と係 $4$ を担当できない。
• D は係 $4$ を担当できない。

行を学生、列を係とする $4\times 4$ の表で、禁止されたマスの集まりを盤 $B$ とし、盤 $B$ に、どの 2 個も同じ行・同じ列にないように $k$ 個のルークを置く方法の数を $r_k$ とする。$r_k$ を求めて、禁止をすべて避ける割り当て方の総数を求めよ。

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

$$\sigma (1)\ne 1,\sigma (1)\ne 2,\sigma (2)\ne 1,\sigma (3)\ne 3,\sigma (4)\ne 4$$

ただし、$4\times 4$ のマス目の第 $i$ 行第 $j$ 列のマスを $(i,j)$ で表し、$\sigma (i)=j$ を「マス $(i,j)$ を使う」と考えるものとする。禁止されるマスは $(1,1),(1,2),(2,1),(3,3),(4,4)$ の $5$ 個である。

集合 $\{1,2,\dots ,8\}$ の置換 $\sigma$（$\{1,\dots ,8\}$ から自分自身への全単射）のうち、
$$\sigma (1)\ne 1,\sigma (2)\ne 2,\sigma (3)\ne 3,\sigma (4)\ne 4$$
をすべて満たすものの個数を求めよ。ただし $\sigma (5),\dots ,\sigma (8)$ には条件をつけない。

0 以上の整数 $n$ に対して、数列 $\{a_n\}$ を
$$a_0=2,a_n=3a_{n-1}+2^n(n\ge 1)$$
で定める。母関数 $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ を用いて、一般項 $a_n$ を $n$ の式で求めよ。

0 以上の整数 $a,b,c$ の組 $(a,b,c)$ で、
$$a+b+c=10,a\text{ は偶数},b\le 3$$
を満たすものの個数を求めよ。

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

1 以上 2000 以下の整数のうち、3 でも 5 でも 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$ が奇数であることは同値である」ことを証明せよ。

$n$ を正の整数とする。頂点集合を $\{a_1,a_2,a_3,b_1,b_2,\dots ,b_n\}$ とし、辺集合を
$$\{a_i{b}_j\mid 1\le i\le 3,1\le j\le n\}\cup \{a_1{a}_2\}$$
とする単純グラフ $G$ を考える（完全二部グラフ $K_{3,n}$ に辺 $a_1{a}_2$ を 1 本加えたグラフ）。$k$ を正の整数とし、区別のつく $k$ 色を用意する。$G$ の各頂点に $k$ 色のいずれか 1 色を塗り、辺で結ばれた 2 頂点が必ず異なる色になるようにする（使わない色があってもよい）。このような塗り方の総数、すなわち $G$ の彩色多項式 $P(G,k)$ を $k$ と $n$ の式で求めよ。

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

$4\times 4$ のマス目（16 個の正方形のマスからなる正方形の盤）に、区別のつかない 4 個の石を、どの 2 個も同じマスに入らないように置く。盤を回転または裏返し（正方形の対称移動、全部で 8 通り）によって重ね合わせられる置き方は同じものとみなすとき、異なる置き方は何通りあるか。

頂点集合を $\{1,2,3,4,5,6,7\}$ とする完全グラフ $K_7$ から、$3$ 本の辺 $\{1,2\}$, $\{3,4\}$, $\{5,6\}$ を取り除いて得られる単純グラフを $G$ とする。$G$ の全域木の個数を求めよ。ただし、頂点にはラベルがついており、辺集合が異なる全域木は区別する。

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

正四面体の 6 本の辺のそれぞれを、赤・青・黄の 3 色のうちいずれか 1 色で塗る（使わない色があってもよい）。正四面体の回転によって互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

頂点 $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$ の式で求めよ。

整数 $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)$$
を満たすものの個数を求めよ。

$n$ を正の整数とする。3 種類の文字 $\mathrm{A},\mathrm{B},\mathrm{C}$ を重複を許して $n$ 個並べてできる長さ $n$ の文字列のうち、$\mathrm{A}$ の個数が偶数（0 個を含む）であり、かつ $\mathrm{B}$ の個数が奇数であるものの個数を $w_n$ とする。$w_n$ を $n$ の式で求めよ。

赤い玉 4 個と青い玉 6 個（同じ色の玉どうしは区別しない）の計 10 個を、円周上に等間隔に並べた 10 か所に 1 個ずつ置き、ひもを通して輪（ブレスレット）を作る。輪の回転および裏返しによって互いに重ね合わせられる並べ方は同じものとみなすとき、異なる輪は何通りできるか。

数列 $\{b_n{\}}_{n\ge 0}$ を
$$b_0=1,b_1=2,b_n=3b_{n-1}-b_{n-2}(n\ge 2)$$
で定める。また、0 以上の整数 $n$ に対して
$$a_n=\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n+k}{2k}\right)$$
とおく。すべての 0 以上の整数 $n$ に対して $a_n=b_n$ が成り立つことを、母関数（有理数係数の形式的冪級数）を用いて証明せよ。

ただし、形式的冪級数環 $\mathbb{Q}[[x]]$ において、0 以上の整数 $m$ に対する等式
$$\frac{1}{(1-x{)}^{m+1}}=\sum _{j=0}^{\infty }\left(\genfrac{}{}{0ex}{}{j+m}{m}\right)x^j$$
が成り立つことと、定数項が $0$ でない形式的冪級数は $\mathbb{Q}[[x]]$ で逆元をもつことは用いてよい。また、0 以上の整数 $p,r$ が $p<r$ を満たすときは $\left(\genfrac{}{}{0ex}{}{p}{r}\right)=0$ と約束する。

カタラン数 $C_0,C_1,C_2,\dots$ を
$$C_0=1,C_{n+1}=\sum _{i=0}^n{C}_i{C}_{n-i}(n\text{は 0 以上の整数})$$
で定める。0 以上の整数 $n$ について、$C_n$ が奇数であるための必要十分条件は、ある 0 以上の整数 $j$ を用いて $n=2^j-1$ と表されることであることを証明せよ（$2^0=1$ とし、$n=0$ は $j=0$ の場合にあたる）。

$n$, $k$ を正の整数とし、$\phi$ をオイラー関数（正の整数 $d$ に対し、$1\le s\le d$ で $\gcd (s,d)=1$ を満たす整数 $s$ の個数）とする。このとき
$$\sum _{d\mid n}\phi (d)k^{n/d}$$
は $n$ で割り切れることを、バーンサイドの補題を用いて証明せよ。ここで ${\sum }_{d\mid n}$ は $n$ の正の約数 $d$ すべてについての和を表す。

ただし、バーンサイドの補題（有限群 $G$ が有限集合 $X$ に作用するとき、軌道の個数は $\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$ に等しい。$\mathrm{Fix}(g)=\{x\in X:gx=x\}$）と、整数 $a,b$（少なくとも一方は $0$ でない）に対して $ax+by=\gcd (a,b)$ を満たす整数 $x,y$ が存在することは用いてよい。

$4\times 4$ のマス目（$16$ 個の正方形のマス）から、ちょうど $4$ マスを選んで黒く塗り、残りの $12$ マスを白く塗る。マス目全体（正方形）の対称変換、すなわち中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の回転と、$4$ 本の対称軸（縦・横の中線 $2$ 本と対角線 $2$ 本）に関する裏返しの計 $8$ 個の変換のいずれかで互いに重ね合わせられる塗り方は同じものとみなす。このとき、異なる塗り方は何通りあるか。

0 以上の整数 $n$ に対して、数列 $\{a_n\}$ を
$$a_0=1,a_1=3,a_n=4a_{n-1}-4a_{n-2}+2^n(n\ge 2)$$
で定める。母関数 $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$ を用いて、一般項 $a_n$ を $n$ の式で表せ。

集合 $\{1,2,3,4,5,6,7\}$ の置換（$\{1,\dots ,7\}$ から自分自身への全単射）$\sigma$ を考える。$\sigma$ を互いに素な巡回置換の積に分解する。このとき、不動点も長さ $1$ の巡回として数える。分解に現れる巡回の個数がちょうど $3$ であり、しかも $1$ と $2$ が同じ巡回に属するような $\sigma$ は何個あるか。

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

$3\times 3$ のマス目（正方形の盤）の $9$ 個のマスのうち、ちょうど $4$ 個を黒で、残りの $5$ 個を白で塗る。正方形の対称変換群（中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の回転と、$4$ 本の対称軸に関する裏返しの、合わせて $8$ 個の変換からなる二面体群）によって互いに重ね合わせられる塗り方は同じものとみなす。異なる塗り方は何通りあるか。

集合 $\{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 組の夫婦、合計 8 人がプレゼント交換をする。各人はちょうど 1 つのプレゼントを用意し、8 個のプレゼントを 8 人に 1 個ずつ配り直す（すなわち、配り方は 8 人の集合の置換に対応する）。ただし、どの人も自分自身が用意したプレゼントも、自分の配偶者が用意したプレゼントも受け取らないものとする。このような配り方は何通りあるか。

数列 $\{a_n{\}}_{n\ge 0}$ を
$$a_0=1,a_n=\sum _{k=1}^n{k}^2{a}_{n-k}(n\ge 1)$$
で定める。無限級数
$$\sum _{n=0}^{\infty }\frac{a_n}{5^n}$$
は収束することが示せる。その和を求めよ。

正八面体の $8$ つの面を、赤・青・緑の $3$ 色で塗る。ただし、赤の面がちょうど $2$ 枚、青の面がちょうど $3$ 枚、緑の面がちょうど $3$ 枚となるように塗る。正八面体の回転（空間内の向きを保つ合同変換で正八面体を自分自身に重ねるもの、全部で $24$ 個）によって互いに移り合う塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。

頂点集合を $\{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 つもないものの個数を求めよ。

立方体の 12 本の辺のうち、ちょうど 6 本を赤、残りの 6 本を青で塗る。立方体の回転によって互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

頂点集合を $\{1,2,\dots ,8\}$ とする完全グラフ $K_8$ から、4 本の辺 $\{1,2\},\{3,4\},\{5,6\},\{7,8\}$ を取り除いて得られる単純グラフを $G$ とする。$G$ の全域木の個数を求めよ。ただし、頂点はすべて区別し、辺集合が異なる全域木は異なるものとして数える。

左括弧「(」7 個と右括弧「)」7 個を 1 列に並べた長さ 14 の文字列で、正しく対応のとれた括弧列（どの位置までを見ても「(」の個数が「)」の個数以上であり、全体では両者が等しいもの）を考える。括弧列の左から $j$ 文字目までに含まれる「(」の個数から「)」の個数を引いた値を $j$ 文字目での深さとし、$j=1,2,\dots ,14$ にわたる深さの最大値を、その括弧列の入れ子の深さという。入れ子の深さが 3 以下である正しい括弧列の個数を求めよ。

$n$ を正の整数とする。座標平面上で、原点 $(0,0)$ から点 $(2n,0)$ まで、1 歩ごとに $(1,1)$ または $(1,-1)$ だけ進む経路のうち、途中で $y$ 座標が一度も負にならないものを考える（このような経路をディック経路という）。ディック経路 $P$ に対し、$P$ が通る点 $(i,0)$ で $1\le i\le 2n$ を満たすものの個数を $r(P)$ とする（$x$ 軸に戻る回数。終点 $(2n,0)$ も数える）。

$$S_n=\sum _{P}r(P{)}^2$$

とおく。ただし、和は長さ $2n$ のディック経路 $P$ すべてにわたってとる。$S_n$ を $n$ の式で表せ。