6.7~6.8
2026년 11월 18일 공유
이항계수와 비둘기집 원리
개요
- 콘텐츠 유형: 강의
- 주제: 이항정리의 조합론적 설명과 파스칼 삼각형, 조합론적 항등식의 증명, 비둘기집 원리의 여러 형태와 응용을 다룬다.
- 조합론은 세기를 연구하며, 대수식의 계수를 경우의 수로 해석할 수 있다. 비둘기집 원리는 여러 대상이 더 적은 수의 범주에 배정될 때 특정 범주에 대상이 모일 수밖에 없음을 보이는 존재 원리다.
핵심 개념
- 이항정리
각 항의 계수
는
개의 인수 중
를 선택하는 위치를 고르는 방법의 수다.- 파스칼 삼각형: 양쪽 가장자리는 1이며, 안쪽 수는 바로 위의 두 수를 더해 얻는다. 각 행은 이항계수에 해당한다.
- 조합론적 항등식과 증명: 세기 과정에서 도출되는 항등식과, 경우를 나누어 세는 논증을 이용한 증명이다.
- 비둘기집 원리: 개의 대상이개의 범주에 배정되고라면, 적어도 한 범주에는 두 개 이상의 대상이 있다.
- 일반화: 유한집합 에서로 가는 함수에서이면 서로 다른 두 원소가 같은 함수값을 갖는다. 더 일반적으로, 어떤 함수값은 적어도개의 원소에서 나온다.
상세 노트
이항정리와 조합적 해석
은
를
번 곱한 식이다. 전개할 때 각 인수에서
또는
를 하나씩 선택해 곱하고, 가능한 모든 선택의 결과를 더한다.- 를번 선택하면 나머지번은를 선택하므로 항은이다.
- 이 항을 얻으려면 개 위치 중를 선택할개 위치를 정해야 한다. 그 방법의 수는다.
- 따라서 가능한 모든 에 대해 항을 더하면 이항정리가 성립한다. 여기서는 실수이고은 양의 정수다.
파스칼 삼각형과 계수 계산
파스칼 삼각형의 바깥쪽은 1로 채우고, 안쪽 각 수는 바로 위의 두 수를 더한다. 빈자리는 0으로 생각할 수 있다. 첫 행을
으로 두면 각 행의 위치는
부터
까지의 계수
를 나타낸다.예를 들어
인 행은 각각 다음과 같다.
예제:
에서
의 계수를 구한다.- 이므로 해당 항은이다.
- 이므로 계수는이다.
조합론적 항등식: 파스칼 항등식
일 때 다음이 성립한다.
이를 조합적으로 증명하기 위해
개의 원소를 가진 집합
에
에는 없는 원소
를 더해
를 만든다.
의
원소 부분집합을
의 포함 여부에 따라 나눈다.- 를 포함하지 않는 부분집합은에서 고른원소 부분집합이므로개다.
- 를 포함하는 부분집합은에서개를 고른 뒤를 더한 것이므로개다.
- 두 경우는 서로 겹치지 않고 모든 원소 부분집합을 포함한다. 따라서 두 개수를 더하면가 된다.
비둘기집 원리
개의 비둘기를
개의 집에 넣고
라면, 적어도 한 집에는 비둘기가 두 마리 이상 있다. 이 원리는 어떤 대상이 존재한다는 사실을 보일 뿐, 그 대상을 찾는 방법이나 그런 대상의 총개수까지 알려주지는 않는다.대우를 이용한 증명: 모든 집에 비둘기가 최대 한 마리씩만 있다고 가정하면, 전체 비둘기 수는 최대
마리다. 따라서 비둘기 수가
라는 조건과 모순이다. 그러므로 적어도 한 집에는 두 마리 이상이 있어야 한다.이름 조합 예시
사람 10명의 이름에서 이름은 Alice, Bernard, Charles 중 하나이고 성은 Lee, Ptoff, Ning 중 하나라고 하자. 가능한 이름 조합은
개뿐이다. 10명을 9개 조합에 배정하므로, 적어도 두 사람은 이름과 성이 모두 같다.함수와 집합을 이용한 형태
유한집합
와 함수
에 대해
라면, 서로 다른
가 있어
이다.이는 비둘기를
의 원소, 비둘기집을
의 원소로 보고, 각
를 함수값
에 배정하는 것과 같다.연속된 번호가 있는 과목 예시
서로 다른 컴퓨터과학 과목 151개의 번호가 1부터 300까지라고 하자. 각 과목 번호
마다
와
을 대응시키면 총 302개의 수가 생기며, 이 수들은 1부터 301까지의 범위에 있다. 따라서 302개의 수를 301개의 가능한 값에 대응시킨 셈이므로, 적어도 두 수가 같다.같은 종류의 수끼리는 과목 번호가 서로 다르므로 중복될 수 없다. 따라서 같은 값을 만드는 두 수는 서로 다른 종류에서 하나씩 나와야 한다. 즉 어떤
에 대해
이며, 두 과목의 번호는 연속된다.비둘기집 원리의 일반화
유한집합
에 대해
이고
라고 하자. 그러면 어떤
는 적어도
개의 원소에서 함수값으로 나온다.
예를 들어
이면
이므로, 적어도 두 원소가 같은 함수값을 갖는다.증명 개요: 각
에 대응하는 원소가 최대
개라고 가정하면,
의 원소 수는 최대
이다. 따라서
, 즉
이어야 한다. 그러나
이면
이므로 모순이다. 따라서 어떤 함수값은 적어도
개의 원소에서 나온다.