2019-04-04

次数の条件がついたなもり木のより善い数え方

CODE FESTIVAL 2017 Elimination Tournament (名前が長い！) の F 問題の想定解よりも善い解法です． atcoder.jp

問題概要

以下の条件を満たすような $N$ 頂点の無向グラフは何通りあるか．(頂点は区別する)

グラフは単純で連結

頂点 $i$ の次数は $d_i$

$d_i$ の総和が $2(N-1)$ のとき(つまり，グラフが木のとき)，答えは $\frac{(N-2)!}{(d_1 - 1)!(d_2 - 1)! \cdots (d_N - 1)!}$ である．

では， $d_i$ の総和が $2N$ のとき(つまり，グラフが俗に言う「なもり木」*1のとき) はどうか？

想定解は $O(N^{3})$ ですが，実は $O(N^{2})$ で解くことができます．

*1:「なもり」という漫画家がおり，Twitterでのアイコンがグラフに似ていることから．

2019-03-08

奇分割と異分割の間の1対1対応

算数

ブログを書く練習がてら軽く．

分割って？

正の整数 $n$ の，いくつかの正の整数の和としての表し方を「分割」といい，個々の正の整数を「因子」という．たとえば， $5$ の分割は

${ \displaystyle 5 \\ 4 + 1 \\ 3 + 2 \\ 3 + 1 + 1 \\ 2 + 2 + 1 \\ 2 + 1 + 1 + 1 \\ 1 + 1 + 1 + 1 + 1 \\ }$

の $7$ 通り．因子を並べ替えただけの分割(たとえば $1+1+2+3+3$ と $3+1+2+1+3$ ) は同一視する*1．

分割の中でも特に，因子がすべて奇数のもの(e.g. $9+5+5+1$ )を「奇分割」，因子が相異なるもの(e.g. $5+9+6+3$ )を「異分割」と呼ぶ．実は任意の $n$ について， $n$ の奇分割と異分割は同数である．オイラーはこのことを母関数から示し，その式は「オイラーの分割恒等式」と名付けられているが，ここでは小学生でも理解できるよう，簡単な1対1対応を与えることにする．