場合の数

二項定理とは，

$(a+b)^n$ を展開したときの $a^kb^{n-k}$ の係数は ${}_n\mathrm{C}_k$ である

という定理。

$0$ の階乗は $0!=1$ と定義する。なぜなら，そう定義すると都合がよいから。

2つの事象 $A,B$ が同時には起こらないとする。$A$ の起こり方が $m$ 通り，$B$ の起こり方が $n$ 通りあるとき，$A$ または $B$ の起こり方は $m+n$ 通りである。

${}_m\mathrm{P}_n=m(m-1)\cdots (m-n+1)$

（$m$ から順々に1減らしながら $n$ 個の整数のかけ算をする）

1. 求めたい「$n$ 回目の確率」を $a_n$ とおく
2. $a_n$ と $a_{n-1}$ の関係を漸化式で表す
3. 漸化式を解く

異なる $n$ 種類のものから、重複を許して $r$ 個取り出して並べる順列の個数は $n^r$

$n$ 種類のものから重複を許して $r$ 個選ぶ場合の数は ${}_{n+r-1}\mathrm{C}_r$ 通り。

$(a+b+c)^n$ を展開したときの $a^pb^qc^r$ の係数は，$\dfrac{n!}{p!q!r!}$

（ただし，$p+q+r=n$ かつ $p,q,r$ は $0$ 以上）

異なる $n$ 個のものを数珠順列で並べるとき，並べ方の総数は

$$\dfrac{(n-1)!}{2}\text{通り}$$

「が」「く」「す」と書かれたカードが1枚ずつ、「こ」と書かれたカードが2枚、「う」と書かれたカードが3枚ある。これら8枚のカードを無作為に並べ、文字列を作ることを考える。

以下の問いに答えよ。

(1) 文字列が「こうこうすうがく」となる確率を求めよ。

(2) 文字列に「がく」が含まれる確率を求めよ。

(3) 文字列に「すうがく」が含まれる確率を求めよ。

(4) 文字列に「すうがく」が含まれるとき、文字列が「こうこうすうがく」である確率を求めよ。

${}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r}$

$$\begin{aligned} &|A_1\cup A_2\cup\cdots\cup A_n|\\ &=\sum_{i}|A_i|\\ &\quad -\sum_{i < j}|A_i\cap A_j|\\ &\quad +\sum_{i < j < k}|A_i\cap A_j\cap A_k|\\ &\quad -\cdots\\ &\quad +(-1)^{n-1}|A_1\cap\cdots\cap A_n| \end{aligned}$$

$n\geqq 2$ とする。$1$ から $n$ までの整数を並び替えてできる順列のうち，すべての $i$ について「$i$ 番目が $i$ でない」を満たすものの個数 $a_n$ は

$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$

カタラン数とは， $$c_n=\dfrac{{}_{2n}\mathrm{C}_{n}}{n+1}$$ で定義される数 $c_n$ のこと。

モンモールの問題を知っていれば公式を用いて $p_n(k)$ を求めることができます。そうすればただの恒等式の証明問題に帰着されます。式がゴツくてしんどいですが数学的帰納法を用いて証明できます。

正の整数 $n$ をいくつかの正の整数の和で表す方法の数を $n$ の分割数と言う。

数学オリンピックで主客転倒とは，総和を，別の視点から場合分けし直すことで求めるテクニックです。double countingともいいます。

任意の非負整数 $p,q,n$ に対して，

$\displaystyle\sum_{k=0}^n{}_p\mathrm{C}_k\cdot {}_q\mathrm{C}_{n-k}={}_{p+q}\mathrm{C}_n$

という恒等式が成立する。これをヴァンデルモンドの畳み込みと言う。 ただし，$p < k$ のとき ${}_p\mathrm{C}_k=0$ と定義する。

• 任意の自然数 $n$ に対して
  $\:S(n,1)=S(n,n)=1\:$

• 任意の $n,k\:(k\geq 2, n \geq k+1)$ に対して
  $S(n,k)=S(n-1,k-1)+kS(n-1,k)$

$n$ 個の要素からなる集合 $\{1,2,\cdots,n\}$ から要素数が $k$ の部分集合たちを以下の条件を満たすようにできるだけたくさん選びたい。

条件：選んだ部分集合のどの二つを選んでも共通元が存在する。

$n\geq 2k$ のとき， 選べる部分集合の限界 $N$ は，$N={}_{n-1}\mathrm{C}_{k-1}$ 個である。

$a,b$ を正の整数とする。各項が相異なる長さ $ab+1$ の数列があるとき，以下の二つのうち少なくとも一つは必ず存在する。

1. 長さ $a+1$ の部分列で，単調増加なもの
2. 長さ $b+1$ の部分列で，単調減少なもの

1. 「必勝形でない状態」からうまく石を取れば「必勝形」になるので自分の手番終了後は常に「必勝形」になる。

2. 「必勝形」からどのように石を取っても「必勝形でない状態」になるので相手の手番終了後は常に「必勝形でない状態」になる。

3. 石がない状態（終了状態）は「必勝形」なので，終了状態は自分の手番終了後に来るはず！

$q \to 1$ で元の概念に一致するようにパラメーター $q$ を追加した概念を $q$-類似という。

$q$-整数，$q$-階乗，$q$-二項係数を順に $$\begin{aligned} [n]_q &= \dfrac{1-q^n}{1-q}\\ [n]_q! &= [n]_q [n-1]_q \cdots [2]_q [1]_q\\ \binom{n}{k}_q &= \dfrac{[n]_q!}{[k]_q! [n-k]_q!} \end{aligned}$$ と定義されていた。