場合の数
二項係数の有名公式一覧と2つの証明方針
二項係数の有名公式を紹介し,それぞれ代数的な方法と組み合わせ的な方法で導きます。
特に3つ目の公式は整数問題にも応用することができる重要な公式です。
モンモールの問題の応用
1987年国際数学オリンピックキューバ大会の第一問の2通りの解法を紹介します。
を不動点をちょうど 個持つ 次の置換の数とする。
このとき, を証明せよ。
ただし, 次の置換とは,集合 から への一対一対応であり, を満たすとき を置換 の不動点と呼ぶ。
分割数の意味と性質・ヤング図形の活躍
分割数:自然数 をいくつかの自然数の和で表す方法の数を の分割数と言う。
数え上げの有名な話題です。自然数の分割にまつわるごく基本的なこと。
全射の個数の証明とベル数
人を区別のある(ちょうど) 個のチームに分ける場合の数は,
の問題は大学入試として適度な難易度です。覚える必要はありませんが,導出できるようになっておきましょう。
写像12相(場合の数の有名問題)
個の玉を 個の箱に入れる場合の数を数える問題を考えます。状況によって12パターンの問題設定が考えられるので写像12相(Twelvefold way)と呼ばれている有名な問題です。
写像という言葉は知らなくても理解できる問題です。後半はかなり難しいので読めるとこまで読んでみてください。
Erdös-Ko-Radoの定理
個の要素からなる集合 から要素数が の部分集合たちを以下の条件を満たすようにできるだけたくさん選びたい。
条件:選んだ部分集合のどの二つを選んでも共通元が存在する。
のとき, 選べる部分集合の限界 は, 個である。
組み合わせの有名な定理です。証明は数学オリンピックの練習問題としては難し目ですが,非常にエレガントです。
Erdös Szekersの定理とその証明
を正の整数とする。各項が相異なる長さ の数列があるとき,以下の二つのうち少なくとも一つは必ず存在する。
1:長さ の部分列で,単調増加なもの
2:長さ の部分列で,単調減少なもの
道順の場合の数を求めるテクニック
定期試験や入試で頻出の「道順の場合の数を求める問題(最短経路問題)」について。有名なテクニックである書き込み方式について解説します。漸化式を使って場合の数を求める,動的計画法の入り口。
8パズル,15パズルの不可能な配置と判定法
8パズル,15パズルにおいて,完成した形から2枚のパネルの場所を交換した状態からスタートしても完成させることはできない。
二項定理の意味と2通りの証明
二項定理とは, 乗の式を展開するための以下のような公式のことです。
二項定理は見た目が少し複雑ですが,慣れてしまえば難しくありません。 二項定理の意味 と, 二項定理の2通りの証明 を解説します。
ランダムウォークの基礎(一次元,高校範囲)
確率 で ポイント, で ポイントとなるゲームを繰り返すような確率モデルを一次元ランダムウォークと言う。
ランダムウォークは入試にも頻繁に登場する&現実の様々な現象の記述に使える重要なモデルです。
Isolation Lemmaとその証明
を の部分集合族とする。
の各要素 に重み を割り当てる。 はそれぞれ独立に の中から一様ランダムに選ぶ。
の重みを と定義する。
このとき,確率 以上で の要素の中で重みを最小にするものはただ一つである。
離散最適化のややマニアックな定理を紹介します。
多項定理の例題と2通りの証明
を展開したときの の係数は
かつ各 が非負なら
(そうでないなら )
多項定理は二項定理の拡張です( のときは二項定理)。前半は具体例,後半は証明です。