和の法則・積の法則と樹形図

大小 $2$ 個のさいころを同時に投げる。出た目の和が $5$ または $10$ になる場合は何通りあるか。

ある食堂のランチでは、主菜を ハンバーグ・焼き魚・からあげ の $3$ 種類から $1$ つ選び、さらに飲み物を お茶・コーヒー・紅茶・ジュース の $4$ 種類から $1$ つ選ぶ。主菜と飲み物の選び方は全部で何通りあるか。

ある店のランチセットでは、主食を $1$ つ、飲み物を $1$ つ選ぶ。主食はパン $3$ 種類とごはん $2$ 種類の中から $1$ つ選び、飲み物は $4$ 種類の中から $1$ つ選ぶ。ただし、パンとごはんに同じものはないものとする。主食と飲み物の選び方は全部で何通りあるか。

A, B, C, D, E の 5 人が円形のテーブルに座る。回転して一致する座り方は同じものとみなすとき、A と B が隣り合う座り方は何通りあるか。

赤玉 $3$ 個、白玉 $2$ 個、青玉 $2$ 個の合計 $7$ 個の玉を、左から右へ一列に並べる。同じ色の玉は互いに区別しないものとする。このとき、両端の玉が同じ色になる並べ方は何通りあるか。

7 個の文字 $\mathrm{A},\mathrm{A},\mathrm{B},\mathrm{B},\mathrm{B},\mathrm{C},\mathrm{C}$ をすべて 1 列に並べる。左端の文字と右端の文字が同じであり、かつ 2 個の $\mathrm{C}$ が隣り合わないような並べ方は何通りあるか。

ケーキ店で、ショートケーキ、チーズケーキ、モンブランの 3 種類のケーキから合計 $10$ 個を買う。どの種類も少なくとも $1$ 個は買い、モンブランは $4$ 個以下にする。このような買い方は何通りあるか。ただし、同じ種類のケーキは区別しないものとし、どの種類も十分な数があるものとする。

半順序集合 $(Q,\le )$ は、対象を $Q$ の元とし、$p\le q$ のときに限り $p$ から $q$ への射がちょうど $1$ つ存在する（それ以外のときは射が存在しない）圏とみなす。

集合 $\{1,2,3,4\}$ の分割（空でない互いに素な部分集合（ブロック）への分け方）全体を ${\Pi }_4$ とし、分割 $\pi ,\sigma$ について「$\pi$ の各ブロックが $\sigma$ のあるブロックに含まれる」ときに $\pi \le \sigma$ と定める（細分による順序）。この半順序集合 $({\Pi }_4,\le )$ を圏とみなしたとき、射（恒等射も含む）の総数を求めよ。

終端記号 $\{a,b\}$、非終端記号 $\{S,A\}$、開始記号 $S$ をもち、次の 4 つの生成規則からなるチョムスキー標準形の文脈自由文法 $G$ を考える。
$$S\to SA,S\to AS,S\to b,A\to a$$
文字列 $w=aabaa$ について、$G$ における $w$ の構文木（導出木）の個数を求めよ。ここで、構文木の個数は $w$ の最左導出の個数に等しい。

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

出力が $8$ 通りの値 $\{0,1,2,\dots ,7\}$ のどれかになるハッシュ関数 $H$ を考える。$H$ はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に $8$ 通りの値から等確率で選ばれるものとする。

攻撃者は、署名してもらいたい「正当な文書」の変種 $x_1,x_2,x_3$ と、すり替えたい「不正な文書」の変種 $y_1,y_2,y_3$ を用意する。これら $6$ 個の入力は互いに異なる。攻撃者は
$$H(x_i)=H(y_j)$$
を満たす $i,j(1\le i\le 3,1\le j\le 3)$ が少なくとも $1$ 組存在するとき、攻撃に成功するものとする。正当な文書どうし、または不正な文書どうしでハッシュ値が一致しても、それだけでは成功とはみなさない。

攻撃に成功する確率を、既約分数で求めよ。

静止している ${\tau }^{-}$ レプトン（静止質量 $1776.86\mathrm{MeV}/c^2$）が、ちょうど $4$ 個の粒子に崩壊する終状態を考える。終状態の粒子は、次の $17$ 種類から重複を許して選ぶものとする（括弧内は静止質量で、単位は $\mathrm{MeV}/c^2$）。

$$e^{-},e^{+}(0.511),{\mu }^{-},{\mu }^{+}(105.66),{\nu }_e,{\bar{\nu }}_e,{\nu }_{\mu },{\bar{\nu }}_{\mu },{\nu }_{\tau },{\bar{\nu }}_{\tau }(0),$$
$${\pi }^{+},{\pi }^{-}(139.57),{\pi }^0(134.98),p,\bar{p}(938.27),n,\bar{n}(939.57)$$

量子数は次のとおりとする。$e^{-},{\nu }_e$ は電子型レプトン数 $L_e=+1$、${\mu }^{-},{\nu }_{\mu }$ はミュー型レプトン数 $L_{\mu }=+1$、${\tau }^{-},{\nu }_{\tau }$ はタウ型レプトン数 $L_{\tau }=+1$ をもち、それ以外のレプトン数は $0$ である。$p,n$ はバリオン数 $B=+1$ で、レプトン数は $0$ である。${\pi }^{+},{\pi }^{-},{\pi }^0$ は $B=0$ で、レプトン数はすべて $0$ である。反粒子は、電荷・$B$・各レプトン数の符号が粒子と逆である（${\pi }^{+}$ と ${\pi }^{-}$ は互いに反粒子、${\pi }^0$ は自身が反粒子）。電荷は $e^{-},{\mu }^{-},{\tau }^{-},{\pi }^{-},\bar{p}$ が $-1$、$e^{+},{\mu }^{+},{\pi }^{+},p$ が $+1$、そのほかは $0$（電気素量単位）である。

崩壊が許されるための条件は、電荷・バリオン数 $B$・$L_e$・$L_{\mu }$・$L_{\tau }$ がそれぞれ保存されることと、終状態の粒子の静止質量の和が ${\tau }^{-}$ の静止質量より小さいこと（エネルギー保存）だけとする。角運動量や相互作用の種類による制限は考えない。終状態は、粒子の種類とその個数の組（順序は区別しない）で区別する。このとき、許される $4$ 粒子終状態は何通りあるか。

静止している ${\Sigma }^{-}$ 粒子（静止エネルギー $1197.4\mathrm{MeV}$、電荷 $-e$、バリオン数 $1$、レプトン数 $0$）の崩壊を考える。終状態の粒子は、次の表の粒子だけから選ぶものとする（同じ種類の粒子を 2 個以上含んでもよい）。

ここで $p,n,\Lambda$ のバリオン数は $1$、それ以外の粒子のバリオン数は $0$ である。電子型レプトン数 $L_e$ は $e^{-},{\nu }_e$ が $+1$、$e^{+},{\bar{\nu }}_e$ が $-1$、ミュー型レプトン数 $L_{\mu }$ は ${\mu }^{-},{\nu }_{\mu }$ が $+1$、${\mu }^{+},{\bar{\nu }}_{\mu }$ が $-1$ で、他の粒子はどちらも $0$ である。

崩壊が起こりうる条件として、次の 2 つだけを課す。

• 電荷・バリオン数・$L_e$・$L_{\mu }$ がそれぞれ保存する（弱い相互作用による崩壊も考えるので、ストレンジネスは保存しなくてよい）。
• 終状態の粒子の静止エネルギーの和が、${\Sigma }^{-}$ の静止エネルギーより小さい。

角運動量やパリティなど、これ以外の選択則は考えない。終状態は、含まれる粒子の種類と個数の組（並べ方は区別しない）で区別する。終状態の粒子数が $2$ 個または $3$ 個であって、上の条件をすべて満たす終状態は何通りあるか。

3 個のさいころを同時に投げるとき、出た目の和が 10 になる確率を求めよ。

数直線上の原点に点 $\mathrm{P}$ がある。1 個のさいころを投げ、出た目が $1$ または $2$ ならば $\mathrm{P}$ を正の向きに $2$ だけ動かし、それ以外の目ならば $\mathrm{P}$ を負の向きに $1$ だけ動かす。この試行を $6$ 回繰り返す。

$6$ 回目の試行の直後に $\mathrm{P}$ が原点にあり、かつ $1$ 回目から $5$ 回目までのどの試行の直後にも $\mathrm{P}$ が原点にない確率を求めよ。

$0,1,2,3$ の $4$ 種類の数字を、同じ数字を何回使ってもよいものとして並べ、$5$ 桁の正の整数を作る。ただし、最高位の数字は $0$ ではないとする。このような $5$ 桁の整数のうち、次の $2$ つの条件をともに満たすものは何個あるか。

(i) 隣り合う位の数字は常に異なる。

(ii) 数字 $0$ を少なくとも $1$ 回含む。

数直線上を動く点 $\mathrm{P}$ が、はじめ原点 $\mathrm{O}$ にある。1 個のさいころを投げて、$1$ または $2$ の目が出たら $\mathrm{P}$ を正の向きに $2$ だけ動かし、$3,4,5,6$ の目が出たら $\mathrm{P}$ を負の向きに $1$ だけ動かす。この試行を $6$ 回繰り返す。$6$ 回の試行を終えたとき $\mathrm{P}$ が原点にあり、かつ $1$ 回目から $6$ 回目までのどの試行の直後にも $\mathrm{P}$ の座標が負にならない確率を求めよ。

男子 $3$ 人、女子 $3$ 人、先生 $1$ 人の計 $7$ 人が、円形のテーブルのまわりに等間隔に並んだ $7$ つの席に座る。回転して一致する座り方は同じものとみなす。次の $2$ つの条件をともに満たす座り方は何通りあるか。

(条件1) 先生の両隣は、男子 $1$ 人と女子 $1$ 人である。

(条件2) 女子どうしはどの $2$ 人も隣り合わない。

数直線上の原点に点 $\mathrm{P}$ がある。1 個のさいころを投げ、3 の倍数の目が出たら $\mathrm{P}$ を正の向きに $2$ だけ動かし、それ以外の目が出たら $\mathrm{P}$ を負の向きに $1$ だけ動かす。この操作を $6$ 回続けて行う。

$6$ 回の操作を終えたとき $\mathrm{P}$ が原点にあり、かつ $1$ 回目から $6$ 回目までのどの操作の直後にも $\mathrm{P}$ の座標が $-2$ 以下になっていない確率を求めよ。

$N\ge 2$ を整数とし、その素因数分解を $N=p_1^{e_1}{p}_2^{e_2}\cdots p_r^{e_r}$（$p_1,\dots ,p_r$ は相異なる素数、$e_1,\dots ,e_r$ は正の整数）とする。$N$ の正の約数全体の集合を $D(N)$ とし、整除関係 $a\mid b$ による半順序集合 $(D(N),\mid )$ を圏 $\mathcal{C}$ とみなす。すなわち $\mathcal{C}$ の対象は $D(N)$ の要素で、$a,b\in D(N)$ に対し $a\mid b$ のとき ${\mathrm{Hom}}_{\mathcal{C}}(a,b)$ はただ 1 つの射 $a\to b$ からなり、そうでないとき空集合である（合成は一意に定まるものとする）。

正の整数 $k$ に対して、$\mathcal{C}$ の射の列 $(f_1,f_2,\dots ,f_k)$ で、各 $1\le j\le k-1$ について $f_j$ の終域と $f_{j+1}$ の始域が一致するもの（合成可能な $k$ 個の射の列）全体の集合を ${\mathcal{C}}_k$ とする（${\mathcal{C}}_1$ は $\mathcal{C}$ の射全体）。このとき
$$|{\mathcal{C}}_k|=\prod _{i=1}^r\left(\genfrac{}{}{0ex}{}{e_i+k+1}{k+1}\right)$$
が成り立つことを示せ。素因数分解の一意性は用いてよい。

A と B の $2$ 人が試合を繰り返し行い、先に $4$ 勝した方を優勝とする（優勝が決まった時点で試合をやめる）。$1$ 回の試合で A が勝つ確率は $\frac{2}{3}$、B が勝つ確率は $\frac{1}{3}$ であり、引き分けはなく、各試合の結果は互いに独立であるとする。

A が優勝し、しかも試合の途中のどの時点においても、それまでの B の勝ち数が A の勝ち数を上回ることが一度もない確率を求めよ。

$1$ から $9$ までの整数が $1$ つずつ書かれた $9$ 枚のカードがある。これらをよくまぜて、縦 $3$ 行・横 $3$ 列に並んだ $9$ つのマスに $1$ 枚ずつ無作為に置く。

$3$ つの行のうち、置かれた $3$ 枚のカードに書かれた数の和が $15$ である行が少なくとも $1$ つある確率を求めよ。

$3$ 進法で表したとき、どの位の数字も $0$ または $1$ である正の整数を、小さい順に $a_1,a_2,a_3,\dots$ とする。たとえば $a_1=1,a_2=3,a_3=4,a_4=9$ である。

このとき、和 $$a_1+a_2+a_3+\cdots +a_{100}$$ を $10$ 進法で求めよ。

円周上に等間隔に並んだ $9$ か所の位置に、赤・青・黄の $3$ 色の玉を $1$ 個ずつ置く。各色の玉は何個でも使えて、使わない色があってもよい。ただし、隣り合う $2$ か所には異なる色の玉を置く。

回転して一致する置き方は同じものとみなすとき（裏返して一致するものは区別する）、置き方は全部で何通りあるか。

頂点集合 $V=\{s,a_1,a_2,a_3,a_4,b_1,b_2,b_3\}$ と、次の $10$ 本の辺からなる単純無向グラフ $G$ を考える。
$$E=\{s{a}_1,a_1{a}_2,a_2{a}_3,a_3{a}_4,a_{4}s,a_1{a}_3,s{b}_1,b_1{b}_2,b_2{b}_3,b_{3}s\}$$
$G$ で隣接していない相異なる $2$ 頂点の組 $\{u,v\}$ に対し、$G$ に辺 $uv$ を $1$ 本加えた単純グラフを $G+uv$ と書く。

ここで、オイラー路とはすべての辺をちょうど $1$ 回ずつ通る道（始点と終点は一致してもしなくてもよい）であり、ハミルトン閉路とはすべての頂点をちょうど $1$ 回ずつ通る閉路である。

隣接していない $2$ 頂点の組 $\{u,v\}$ のうち、
- $G+uv$ がオイラー路をもつものの個数を $p$、
- $G+uv$ がハミルトン閉路をもつものの個数を $q$、
- $G+uv$ がオイラー路とハミルトン閉路の両方をもつものの個数を $r$

とする。組 $(p,q,r)$ をこの順に求めよ。

1 個のさいころを 5 回続けて投げ、出た目を順に $a_1,a_2,a_3,a_4,a_5$ とする。積 $a_1{a}_2{a}_3{a}_4{a}_5$ が $60$ の倍数になる確率を求めよ。

横一列に並んだ $6$ 枚の板を、左から順に $1$ 枚ずつ、赤・青・黄・緑の $4$ 色のうちいずれか $1$ 色で塗る。ただし、次の $2$ つの条件をともに満たすように塗る。

(条件1) 隣り合う $2$ 枚の板は異なる色で塗る。

(条件2) $4$ 色すべてを少なくとも $1$ 回は使う。

板はすべて区別し、塗り方は各板の色の組で区別する。このような塗り方は全部で何通りあるか。

1 から 30 までの整数の中から、異なる 4 個の整数を選ぶ。選んだ 4 個のうち、どの 2 個の差も 3 以上であり、さらに最大のものと最小のものの差が 20 以下であるような選び方は何通りあるか。

1 個のさいころを 4 回続けて投げ、出た目を順に $a_1,a_2,a_3,a_4$ とする。積 $a_1{a}_2{a}_3{a}_4$ が $12$ の倍数になる確率を求めよ。

$\mathrm{a},\mathrm{a},\mathrm{a},\mathrm{b},\mathrm{b},\mathrm{b},\mathrm{c},\mathrm{c}$ の $8$ 個の文字をすべて $1$ 列に並べる。同じ文字どうしがどこも隣り合わない並べ方は何通りあるか。

1 個のさいころを 4 回続けて投げ、出た目を順に $a_1,a_2,a_3,a_4$ とする。積 $a_1{a}_2{a}_3{a}_4$ が $60$ の倍数になる確率を求めよ。

アルファベット $\Sigma =\{a,b\}$ 上の正規表現
$$r=(a+ab+abb{)}^{\ast }$$
を考え、$r$ が表す言語を $L(r)$ とする（$+$ は和集合、${}^{\ast }$ はクリーネ閉包を表す）。

長さ $8$ の文字列 $w\in {\Sigma }^{\ast }$ のうち、次の 2 つの条件をともに満たすものの個数を求めよ。

• $w\in L(r)$
• $w$ に含まれる $b$ の個数が偶数である（$0$ 個も偶数とみなす）

$A=\{1,2,3,4,5,6,7\}$ とする。$A$ 上の同値関係 $R$ のうち、次の $2$ つの条件をともに満たすものの個数を求めよ。

• $(1)$ どの同値類も $2$ 個以上の元を含む
• $(2)$ $1$ と $2$ は $R$ に関して同値でない（すなわち $(1,2)\notin R$）

$10$ 人のプレイヤー $1,2,\dots ,10$ が円形に並んでおり、プレイヤー $i$ の隣人はプレイヤー $i-1$ と $i+1$ である（添字は $10$ を法として考え、プレイヤー $0$ はプレイヤー $10$、プレイヤー $11$ はプレイヤー $1$ を表す）。各プレイヤー $i$ は同時に $1$ 回だけ、行動 $x_i\in \{0,1\}$ を選ぶ。プレイヤー $i$ の利得は、2 人の隣人のうち自分と異なる行動を選んだ人数とする。すなわち
$$u_i(x_1,\dots ,x_{10})=|x_i-x_{i-1}|+|x_i-x_{i+1}|$$
である。この $10$ 人ゲームの純粋戦略のナッシュ均衡（行動の組 $(x_1,\dots ,x_{10})$）の個数を求めよ。

$+1$ と書かれたカード $13$ 枚と、$-2$ と書かれたカード $6$ 枚の、合計 $19$ 枚のカードがある。同じ数が書かれたカードは区別しない。これらをすべて横 $1$ 列に並べ、左端のカードから順に書かれた数を足していく。左から $1$ 枚目までの和、$2$ 枚目までの和、…、$19$ 枚目までの和がすべて正となる並べ方は何通りあるか。

$1$ 個のさいころを $10$ 回続けて投げる。$k=1,2,\dots ,10$ に対して、$1$ 回目から $k$ 回目までに出た目の和を $S_k$ とする。$10$ 個の数 $S_1,S_2,\dots ,S_{10}$ のうち、$7$ の倍数であるものがちょうど $2$ 個である確率を求めよ。

円周上に $6$ つの箱 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D},\mathrm{E},\mathrm{F}$ がこの順に並んでおり、$\mathrm{A}$ と $\mathrm{B}$、$\mathrm{B}$ と $\mathrm{C}$、$\mathrm{C}$ と $\mathrm{D}$、$\mathrm{D}$ と $\mathrm{E}$、$\mathrm{E}$ と $\mathrm{F}$、$\mathrm{F}$ と $\mathrm{A}$ がそれぞれ隣り合っている。互いに区別のつかない $15$ 個の玉を、これらの箱にすべて入れる。空の箱があってもよいが、隣り合う $2$ つの箱がともに空になってはならない。このような玉の入れ方は何通りあるか。ただし、箱は互いに区別でき、各箱に入れられる玉の個数に上限はないものとする。

円周上に等間隔に $8$ つの位置があり、それぞれの位置に赤・青・黄のいずれかの色の玉を $1$ 個ずつ置く。各色の玉は十分な個数があり、同じ色の玉どうしは区別しない。次の $2$ つの条件をともに満たす置き方は何通りあるか。ただし、回転して一致する置き方は同じものとみなし、裏返して一致するだけのものは異なるものとみなす。

$(1)$ 隣り合う $2$ つの位置には、異なる色の玉を置く。

$(2)$ 赤・青・黄の $3$ 色すべてを少なくとも $1$ 回ずつ使う。

$1$ から $20$ までの整数の中から異なる $5$ 個を選び、小さい順に $a_1<a_2<a_3<a_4<a_5$ とする。隣り合う $2$ 数の差
$$a_2-a_1,a_3-a_2,a_4-a_3,a_5-a_4$$
がすべて奇数となるような選び方は何通りあるか。

1 個のさいころを $5$ 回続けて投げ、出た目を順に $a_1,a_2,a_3,a_4,a_5$ とする。積 $a_1{a}_2{a}_3{a}_4{a}_5$ が $72$ の倍数となる確率を求めよ。

$x,y,z$ はいずれも $1$ 以上 $100$ 以下の整数とする。$x^2+y^2+z^2$ が $7$ で割り切れるような整数の組 $(x,y,z)$ の個数を求めよ。

正の整数 $n$ に対し、$n!$ が $3^k$ で割り切れるような $0$ 以上の整数 $k$ の最大値を $e(n)$ とする。$1\leqq n\leqq 500$ を満たす整数 $n$ のうち、$$n-2e(n)=4$$ が成り立つものの個数を求めよ。

$2^{12}$ 未満の正の整数 $N$ のうち、次の 2 つの条件をともに満たすものを考える。

• $N$ を $2$ 進法で表したとき、数字 $1$ がちょうど $4$ 個現れる。
• $N$ は $7$ で割り切れる。

このような $N$ すべての総和を求めよ。