られます。つまり、
（条件から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個だけ条件を満たすパターンを求める必
要に出くわしました。
（出会った問題） AtCoder Beginner Contest 423 F - Loud Cicada
なんとなくの直感で、
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]パターンの合計）
かな、と思ったので、一か八かそれで解答を提出したら合っていたようなんですが、これを改
めて証明しようとしてもなかなか難しいです。
初等的な証明はないもんでしょうか？
ａｔ さんからのコメントです、（令和７年９月１８日付け）
ｎ種類の性質のうちの、ちょうどｋ種類の性質のみを保有するオブジェクトの数を e_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
となります。
等式(★)の厳密な証明が、下記ファイルにあります。
(ファイルの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)
以下からダウンロードが可能です。
DD++ さんからのコメントです、（令和７年９月１９日付け）
なるほど、形式的冪級数って手がありましたか。ありがとうございます。
以下、工事中！
