2개의 댓글이 있습니다.

• 
  restart

  전체 가짓수는 2^{n}-1$2^{n}-1$입니다.(1 \le k$1 \le k$이므로) 여기서 어떤 조합에 대해서 a_{i1}$a_{i1}$&a_{i2}$a_{i2}$&…a_{ik}$…a_{ik}$의 값 p$p$가 0$0$이 아닌 가짓수를 뺍시다. U_{i}$U_{i}$을 p$p$의 i$i$번째 비트가 켜져 있게끔 만드는 조합의 집합이라 한다면, 빼야 할 값은 |U_{0} \cup U_{1} \cup … \cup U_{20}|$|U_{0} \cup U_{1} \cup … \cup U_{20}|$입니다. 그런데 f(x)$f(x)$의 정의에 따르면 2^{f(x)}-1$2^{f(x)}-1$는 p$p$에서 x$x$를 포함하게끔 만드는 조합의 가짓수가 되고, 편의상 아래서는 이 값을 f(x)$f(x)$로 부르면
  |U_{0}|=f(1_{2})$|U_{0}|=f(1_{2})$이고 |U_{1}|=f(10_{2})$|U_{1}|=f(10_{2})$이고 |U_{2}|=f(100_{2})$|U_{2}|=f(100_{2})$.. 이런식으로 나갑니다. 또한 |U_{0} \cap U_{1}|=f(11_{2})$|U_{0} \cap U_{1}|=f(11_{2})$이고 |U_{1} \cap U_{2}|=f(110_{2}) ... |U_{0} \cap U_{1} \cap U_{2}| = f(111_{2}) ...$|U_{1} \cap U_{2}|=f(110_{2}) ... |U_{0} \cap U_{1} \cap U_{2}| = f(111_{2}) ...$ 뭐 이런식이 됩니다. g(x)$g(x)$만큼 교집합이 이루어지게 되는 거죠. 이제 포함배제 원리를 적용하면
  |U_{0} \cup U_{1} \cup … \cup U_{20}|=\sum_{x=1}^{2^{20}} (-1)^{g(x)-1}(2^{f(x)}-1)$|U_{0} \cup U_{1} \cup … \cup U_{20}|=\sum_{x=1}^{2^{20}} (-1)^{g(x)-1}(2^{f(x)}-1)$이 되고 전체 가짓수와 빼면 해당 식이 나옵니다.
  2^{f(x)}-1$2^{f(x)}-1$에서 뒷부분 -1$-1$은 다 모으면 _nC_0-_nC_1+_nC_2…_nC_n$_nC_0-_nC_1+_nC_2…_nC_n$꼴로 그냥 없어집니다.

  
  9년 전 link

• 
  JAYS

  U_i$U_i$의 정의를 보니 이해가 됩니다. 자세히 적어주신 덕분에 해결하였습니다. 감사합니다 :)

  
  9년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.