ブログ名

競技プログラミングやお歌のお話をする高菜です。

2024-03-31から1日間の記事一覧

平面内にの pairwise disjoint な長方形3個の配置の分類(品目定理)とそのグラフ理論的証明

変な用語を普及させてしまってまた怒られそうなので、後世の方が「品目定理ってなんですか!?」になったときのために一応残しておきましょう。 主張 平面内にの pairwise disjoint な長方形3個の配置 が与えられているとします。このときこれは垂直な直線ま…

忘れがちな公式

負の二項定理みたいなやつ $$ \frac 1 { (1 - x ) ^ { 1 + n } } = \sum _ { i \ge 0 } \binom { n + i } i x ^ i $$ 重複組み合わせ $$ \left \lbrace x \in \mathbb{N}^k \ \middle \vert \ x _ 1 + \dots + x _ k = n \right \rbrace = \binom { n + k - …