同じものを含む順列・重複組合せ

赤玉 $3$ 個、白玉 $2$ 個、青玉 $1$ 個の合計 $6$ 個の玉を、横一列に並べる。同じ色の玉どうしは区別しないものとするとき、並べ方は全部で何通りあるか。

6 個の文字 $\mathrm{a},\mathrm{a},\mathrm{a},\mathrm{b},\mathrm{b},\mathrm{c}$ をすべて 1 列に並べる。並べ方は何通りあるか。ただし、同じ文字どうしは区別しないものとする。

赤玉 $3$ 個、白玉 $2$ 個、青玉 $1$ 個の合計 $6$ 個の玉を、横 $1$ 列に並べる。並べ方は全部で何通りあるか求めよ。ただし、同じ色の玉どうしは区別しないものとする。

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

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

方程式 $x+y+z=15$ を満たす正の整数の組 $(x,y,z)$ のうち、$x,y,z$ がすべて奇数であるものは何組あるか。

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

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

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

互いに独立で区別できる $N$ 個の 1 次元量子調和振動子（すべて角振動数 $\omega$）からなる孤立系がある。各振動子のエネルギーは、零点エネルギーを除いて $n\hslash \omega$（$n=0,1,2,\dots$）で、系の全エネルギー（零点エネルギーを除く）は $E=M\hslash \omega$（$M$ は正の整数）である。この系をミクロカノニカル分布で扱い、エントロピーを $S=k_B\log W$（$W$ は全エネルギーが $E$ となる微視的状態の数、$k_B$ はボルツマン定数）で定める。$N,M\gg 1$ としてスターリングの公式 $\log n!\approx n\log n-n$ を用い、$E$ を連続変数とみなすとき、$\frac{1}{T}=\frac{\partial S}{\partial E}$ で定まる温度 $T$ を、$E,N,\hslash ,\omega ,k_B$ を用いて表せ。

互いに相互作用しない区別できる $N$ 個の 1 次元量子調和振動子（角振動数はすべて $\omega$）からなる孤立系（アインシュタイン模型）を考える。各振動子のエネルギー準位は $\left(n+\frac{1}{2}\right)\hslash \omega (n=0,1,2,\dots )$ である。系の全エネルギーが、零点エネルギーを含めて $E=\frac{5}{2}N\hslash \omega$ に固定されているとき、ミクロカノニカル分布にもとづいてこの系の温度 $T$ を求めよ。ただし、$N$ は十分大きく、状態数の計算に現れる階乗にはスターリングの近似 $\log n!\approx n\log n-n$ を使ってよい（$N$ に比べて $1$ は無視してよい）。エントロピーは $S=k_B\log W$（$W$ は状態数、$k_B$ はボルツマン定数）、温度は $\frac{1}{T}=\frac{\partial S}{\partial E}$ で定める。$T$ を $\hslash$, $\omega$, $k_B$ を用いて表せ。

環は単位元 $1$ をもつ可換環とする。$k$ を体とし、多項式環 $S=k[x,y,z,w]$ を各変数の次数を $1$ とする次数付き環とみなす。斉次イデアル $$I=(x^2,xy)$$ に対し、次数付き環 $A=S/I$ のヒルベルト関数を $H_A(n)={\dim }_k{A}_n$（$n$ は $0$ 以上の整数、$A_n$ は $A$ の $n$ 次斉次部分）とする。十分大きいすべての整数 $n$ について $H_A(n)=P(n)$ となる多項式 $P(n)$（ヒルベルト多項式）を求めよ。

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

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

$1,1,2,2,3,3,4,4$ の数字が 1 つずつ書かれた 8 枚のカードがある。これらをよくまぜて、無作為に横 1 列に並べる。同じ数字が書かれたカードどうしがどこでも隣り合わない確率を求めよ。

区別のつかない $12$ 個の玉を、区別のつく $4$ つの箱 $\mathrm{A},\mathrm{B},\mathrm{C},\mathrm{D}$ にすべて入れる。空の箱があってもよいが、どの箱にも玉は $5$ 個以下しか入れられない。このとき、箱 $\mathrm{A}$ に入る玉の個数が箱 $\mathrm{B}$ に入る玉の個数より多くなるような入れ方は何通りあるか。

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

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

区別のできる $7$ 人のプレイヤー $1,2,\dots ,7$ が、同時に経路 $A,B,C$ のうちちょうど 1 つを選ぶ。経路 $A,B,C$ を選んだ人数をそれぞれ $a,b,c$（$a+b+c=7$）とするとき、各プレイヤーの費用は
- 経路 $A$ を選んだプレイヤー: $a$
- 経路 $B$ を選んだプレイヤー: $2b$
- 経路 $C$ を選んだプレイヤー: $c+3$

であり、各プレイヤーは自分の費用を最小にしたい。

このゲームの純粋戦略ナッシュ均衡（7 人それぞれがどの経路を選ぶかの組）の個数を求めよ。

$L=\{f\}$ を 1 変数関数記号 $f$ だけからなる一階の言語とし（等号は論理記号として常に真の等号と解釈する）、$L$ の文
$$\sigma :\forall x(f(f(f(x)))=f(x))$$
を考える。正の整数 $n$ に対して $[n]=\{1,2,\dots ,n\}$ とおき、$[n]$ を台集合とする $L$ 構造（$f$ の解釈 $f^{\mathcal{M}}:[n]\to [n]$ によって決まる。解釈が異なる構造は別のものとして数える）のうち、$\sigma$ のモデルであるものの個数を $a_n$ とする。

また、正の整数 $k$ に対し
$$I_k=\sum _{j=0}^{\lfloor k/2\rfloor }\frac{k!}{2^{j}j!(k-2j)!}$$
とおく。すべての正の整数 $n$ について
$$a_n=\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)I_k{k}^{n-k}$$
が成り立つことを証明せよ。

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

円周上に $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$ 個の点があり、時計回りに順に ${\mathrm{P}}_1,{\mathrm{P}}_2,\dots ,{\mathrm{P}}_8$ と名前が付いている。赤玉 $2$ 個、白玉 $2$ 個、青玉 $2$ 個、黄玉 $2$ 個の合計 $8$ 個の玉を、各点に $1$ 個ずつ置く。ただし、同じ色の玉は互いに区別しない。円周上で隣り合う $2$ 点（${\mathrm{P}}_i$ と ${\mathrm{P}}_{i+1}$ $(i=1,2,\dots ,7)$、および ${\mathrm{P}}_8$ と ${\mathrm{P}}_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$$
がすべて奇数となるような選び方は何通りあるか。