포함-제외 원칙에 관한 질문
오늘 저는 처음으로 포함-제외 원칙을 알게되었습니다. 나는 그것을 이해했다고 믿지만 그것에 대한 몇 가지 질문을 풀려고 시도했을 때 심하게 갇혔습니다. 나는 그들 중 어느 것도 해결할 수 없었습니다. 난이도를 높이는 것에 대한 몇 가지 질문을 제안 해 주시면 당면한 주제를 잘 이해할 수 있습니까? 질문 중 하나는 다음과 같습니다.https://math.stackexchange.com/questions/2765746/inclusion-exclusion-problem-sitting-arrangement , 그것은 그리스어 경연 수학 책에 있었고 나는 또한이 사이트에서 그것을 찾았습니다.
다른 질문은 인터넷에서 찾을 수 없었기 때문에 번역하겠습니다.
방정식의 해 수 찾기 $x_1+x_2+x_3=100$, 모든 경우 $3\ge i\ge1$, xi는 다음이 포함 된 음수가 아닌 정수입니다. $40\ge x_i$.
나는이 두 가지 질문에 대한 해결책을 찾았습니다. 제가 그것들을 게시하는 이유는 글을 읽는 독자에게 (댓글에서 지적한 바와 같이) 어떤 수준의 질문이 포함되는지 더 잘 이해하기 위해서입니다. 배제 원칙이 나에게 어려움을 준다
답변
두 번째로 번역 된 질문은 실제로 포함-제외가 필요하지 않습니다. 그것은 사용하여 아주 쉽게 완료됩니다https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)학습 할 가치가있는 또 다른 기술입니다 (아직 수행하지 않은 경우).
글을 쓰자 $u_i=40-x_i$, 제한이 $u_i\ge0$을 입력 한 다음 방정식을 다시 작성하여 다음과 같이 해결하십시오.
$$u_1+u_2+u_3=20$$
(이것은 $100=x_1+x_2+x_3=(40-u_1)+(40-u_2)+(40-u_3)=120-(u_1+u_2+u_3)$, 그런 다음 물건을 움직입니다.) 별과 막대는 이제 음이 아닌 트리플의 수를 $20$ 이다
$${22\choose2}={22\cdot21\over2}=231$$
솔직히 말해서 포함-제외를 사용하여이 문제를 해결하는 데 어려움을 겪을 것이라고 생각합니다. 그렇게하는 쉬운 방법이 있는지 궁금합니다.
다음은 두 번째 문제에 대한 포함-제외 접근 방식입니다. $k$ 수입니다 $i\in\{1,2,3\}$ 와 $x_i \ge 41$: \ begin {align} \ sum_ {k = 0} ^ 2 (-1) ^ k \ binom {3} {k} \ binom {100-41k + 3-1} {3-1} & = \ binom { 102} {2} -3 \ binom {61} {2} +3 \ binom {20} {2} \\ & = 5151-3 \ cdot 1830 + 3 \ cdot 190 \\ & = \ color {red} { 231}. \ 단부 정렬 {}$$\binom{100-41k+3-1}{3-1}$$ 부분은 음이 아닌 정수 솔루션의 별과 막대 수에서 비롯됩니다. $x_1+x_2+x_3=100$ 와 $x_i \ge 41$ ...에 대한 $k$ 지정된 $i\in\{1,2,3\}$, 동등하게 음이 아닌 정수 솔루션 $y_1+y_2+y_3=100-41k$.