数え上げ

式変形で解こうとすると沼にハマる。

すべての $x$ について $\sum{f(x)}$ を計算する→ $f(x) = y$ となるような $x$ はいくつあるか？

数え上げる対象をうまく類別できるかどうかを考える

類別する方法 Sを部分文字列として含む文字列は、Sを取り出す位置の列の内、辞書順最小であるもので類別できる

ある列が与えられた時に、一意に決まるような量を考える

xから計算できる量の内、最大/最小のものを考えるとうまく行く？

e.g. 最大公約数　辞書順最小

式を組み合わせと見なす

公式

\sum_{i=1}^{n}{i^2} = \frac{1}{6} n (n+1) (2n+1)

$S_i = \sum_{k=0}^{n}{k^i}$ とおくと、

S_0 = n+1

S_i = \frac{1}{i+1} \left\{ (n+1)^{i+1} - \sum_{j=0}^{i-1}{_{i+1}\mathrm{C}_{j}S_j} \right\}

$H(n,m)$ = 格子上での $(0,0)$ から $(n,m)$ への最短経路の個数と定義すると、

H(n,m)= \sum_{i=0}^{m}{H(n-1,i)}

$S(n,m)$ = $n$ 個のものをちょうど $m$ 個の空でないグループに分割する方法の個数と定義する時、

S(n+1,m+1)= \sum_{i=0}^{n}{_n\mathrm{C}_i}S(i,m) = \sum_{i=m}^{n}{_n\mathrm{C}_i}S(i,m)

\sum_{k=0}^{n} {}_n \mathrm{C}_k = 2^n

\sum_{k=0}^{n} k {}_n \mathrm{C}_k = n 2^{n-1}

$f(S \cup T) = f(S) + f(T) - f(S \cap T)$ を満たすならば、

集合 $S_1, \dots , S_n$ があるとき、

f\left(\overline{\bigcup_{1 \le i \le n} {\overline{S_i}}} \right) = \sum_{T \subseteq \{1, \dots, n\}} (-1)^{|T|} f\left(\bigcap_{i \in T} S_i \right)