包除原理の親玉
いくつかの条件のうち、少なくとも1つを満たすパターン数を求めるのに、包除原理が用いられます。
つまり、
（条件から1個選んで、それを満たすパターン数を出す……のComb[n,1]パターンの合計）
-（条件から2個選んで、それを満たすパターン数を出す……のComb[n,2]パターンの合計）
+（条件から3個選んで、それを満たすパターン数を出す……のComb[n,3]パターンの合計）
-……
+(-1)^(n-1)*（条件からn個選んで、それを満たすパターン数を出す……のComb[n,n]パターンの合計）
で求められます。
（Comb[n,r]は二項係数）
これの変形で、ちょうど1つだけ条件を満たすパターン数は
1*（条件から1個選んで、それを満たすパターン数を出す……のComb[n,1]パターンの合計）
-2*（条件から2個選んで、それを満たすパターン数を出す……のComb[n,2]パターンの合計）
+3*（条件から3個選んで、それを満たすパターン数を出す……のComb[n,3]パターンの合計）
-……
+(-1)^(n-1)*n*（条件からn個選んで、それを満たすパターン数を出す……のComb[n,n]パターンの合計）
で求められます。
ここまでは知っていたのですが、昨日、ちょうどm個だけ条件を満たすパターンを求める必要に出くわしました。
なんとなくの直感で
Comb[m,m]*（条件からm個選んで、それを満たすパターン数を出す……のComb[n,m]パターンの合計）
-Comb[m+1,m]*（条件からm+1個選んで、それを満たすパターン数を出す……のComb[n,m+1]パターンの合計）
+ Comb[m+2,m]*（条件からm+2個選んで、それを満たすパターン数を出す……のComb[n,m+2]パターンの合計）
-……
+(-1)^(n-m)*Comb[n,m]*（条件からn個選んで、それを満たすパターン数を出す……のComb[n,n]パターンの合計）
かな、と思ったので、一か八かそれで解答を提出したら合っていたようなんですが、これを改めて証明しようとしてもなかなか難しいです。
初等的な証明はないもんでしょうか？
出会った問題
AtCoder Beginner Contest 423 F - Loud Cicada
n種類の性質のうちの、ちょうどk種類の性質のみを保有する
オブジェクトの数を e_k とします。
また、n種類の性質のうちの、特定のk種類の性質を保有する
(このk種類以外の性質を保有していてもよい)オブジェクトの数を
n_kとし、すべての k-部分集合(これらの部分集合は全部でcomb(n,k)個ある)
に対してn_kを足し合わせたものを N_k とします。
このとき、等式
N_k = Σ[j=k～∞]comb(j,k)*(e_j) --- (★)
が成立しています。
E(x)=Σ[k≧0](e_k)*x^k，
N(x)=Σ[k≧0](N_k)*x^k
とします。そうすると、
N(x)
=Σ[k≧0](N_k)*x^k
=Σ[k≧0](Σ[j≧k]comb(j,k)*e_j)*x^k
=Σ[j≧0](e_j)Σ[k≧0]comb(j,k)*x^k
=Σ[j≧0](e_j)*(1+x)^j
=E(1+x)
となります。
よって、E(x)=N(x-1).
このことからe_kは次のように計算できます。
e_k
=[x^k]E(x)
=[x^k]N(x-1)
=[x^k]Σ[j≧0](N_j)*(x-1)^j
=[x^k]Σ[j≧0](N_j)*Σ[r≧0](comb(j,r)*(x^r)*(-1)^(j-r))
=Σ[j≧0](N_j)*(comb(j,k)*(-1)^(j-k))
=Σ[j≧k](N_j)*(comb(j,k)*(-1)^(j-k))
=N_k-comb(k+1,k)*N_(k+1)+comb(k+2,k)*N_(k+2)- … +(-1)^(n-k)*comb(n,k)*N_n
となります。
等式(★)の厳密な証明が、下記ファイルにあります。
https://www2.math.upenn.edu/~wilf/gfology2.pdf
(ファイルの116ページ 4.2 A generatingfunctionological view of the sieve method)
また次の本にも、E(x)=N(x-1)であることの証明があります。
「 Combinatorial Enumeration 」(Dover)
Ian P.Goulden, David M.Jackson 著
46ページおよび47ページ． (Chap.2 2.2.28.および 2.2.29)
以下からダウンロードが可能です。
https://vdoc.pub/documents/combinatorial-enumeration-4vpn3s5kq2c0
なるほど、形式的冪級数って手がありましたか。
ありがとうございます。
