세연이 공부방수학 과목 ▾

개념지도 / 대학 맛보기 / 이산수학·컴퓨터

조합론 심화 (구경)

combinatorics 대학 앞으로

비둘기집 원리, 포함배제, 생성함수 이름만

한 문장 직관 — 이것만 남으면 성공

조합론은 "세는 법"을 연구한다. 세는 게 쉬워 보이지만 가장 어려운 문제들이 여기 있다.

많이 해보면 이론값에 가까워진다세는 것이 가장 어려운 문제가 되기도 한다.
이론182731044513683이 나온 비율 = 10/50 = 0.2000이론값 1/6 = 0.1667 · 차이 0.0333

적게 던지면 들쭉날쭉하다. 큰 수의 법칙 — 횟수를 늘리면 비율이 안정된다.

왜 중요한가

세기의 예술. 올림피아드의 절반

예시

13명 중 같은 달 생일 반드시 2명(비둘기집)

백지에 해볼 것 A4 한 장

'반 30명 중 같은 생일 있을 확률 70%' 계산하고 실제 반 명단으로 확인

확인 질문 — 답하면 통과

다음으로 어떻게 이어지는가

확률, 알고리즘 분석.

먼저 알아야 할 것 순열·조합·이항정리