alt

6.7~6.8

2026년 11월 18일 공유

이항계수와 비둘기집 원리

개요

  • 콘텐츠 유형: 강의
  • 주제: 이항정리의 조합론적 설명과 파스칼 삼각형, 조합론적 항등식의 증명, 비둘기집 원리의 여러 형태와 응용을 다룬다.
  • 조합론은 세기를 연구하며, 대수식의 계수를 경우의 수로 해석할 수 있다. 비둘기집 원리는 여러 대상이 더 적은 수의 범주에 배정될 때 특정 범주에 대상이 모일 수밖에 없음을 보이는 존재 원리다.

핵심 개념

  • 이항정리
(a+b)n=∑k=0n(nk)akbn−k(a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^k b^{n-k}

각 항의 계수
(nk)\binom{n}{k}
는
nn
개의 인수 중
aa
를 선택하는 위치를 고르는 방법의 수다.
  • 파스칼 삼각형: 양쪽 가장자리는 1이며, 안쪽 수는 바로 위의 두 수를 더해 얻는다. 각 행은 이항계수에 해당한다.
  • 조합론적 항등식과 증명: 세기 과정에서 도출되는 항등식과, 경우를 나누어 세는 논증을 이용한 증명이다.
  • 비둘기집 원리:
    nn
    개의 대상이
    kk
    개의 범주에 배정되고
    n>kn>k
    라면, 적어도 한 범주에는 두 개 이상의 대상이 있다.
  • 일반화: 유한집합
    XX
    에서
    YY
    로 가는 함수에서
    ∣X∣>∣Y∣|X|>|Y|
    이면 서로 다른 두 원소가 같은 함수값을 갖는다. 더 일반적으로, 어떤 함수값은 적어도
    ⌈∣X∣/∣Y∣⌉\lceil |X|/|Y|\rceil
    개의 원소에서 나온다.

상세 노트

이항정리와 조합적 해석

(a+b)n(a+b)^n
은
(a+b)(a+b)
를
nn
번 곱한 식이다. 전개할 때 각 인수에서
aa
또는
bb
를 하나씩 선택해 곱하고, 가능한 모든 선택의 결과를 더한다.
  • aa
    를
    kk
    번 선택하면 나머지
    n−kn-k
    번은
    bb
    를 선택하므로 항은
    akbn−ka^k b^{n-k}
    이다.
  • 이 항을 얻으려면
    nn
    개 위치 중
    aa
    를 선택할
    kk
    개 위치를 정해야 한다. 그 방법의 수는
    (nk)\binom{n}{k}
    다.
  • 따라서 가능한 모든
    k=0,…,nk=0,\ldots,n
    에 대해 항을 더하면 이항정리가 성립한다. 여기서
    a,ba,b
    는 실수이고
    nn
    은 양의 정수다.

파스칼 삼각형과 계수 계산

파스칼 삼각형의 바깥쪽은 1로 채우고, 안쪽 각 수는 바로 위의 두 수를 더한다. 빈자리는 0으로 생각할 수 있다. 첫 행을
n=0n=0
으로 두면 각 행의 위치는
k=0k=0
부터
k=nk=n
까지의 계수
(nk)\binom{n}{k}
를 나타낸다.
예를 들어
n=0,1,2,3,4n=0,1,2,3,4
인 행은 각각 다음과 같다.
1;1,1;1,2,1;1,3,3,1;1,4,6,4,11;\quad 1,1;\quad 1,2,1;\quad 1,3,3,1;\quad 1,4,6,4,1

예제:
(3x−2y)5(3x-2y)^5
에서
x2y3x^2y^3
의 계수를 구한다.
  • a=3x, b=−2y, n=5, k=2a=3x,\ b=-2y,\ n=5,\ k=2
    이므로 해당 항은
    (52)(3x)2(−2y)3\binom{5}{2}(3x)^2(-2y)^3
    이다.
  • (52)=10, (3x)2=9x2, (−2y)3=−8y3\binom{5}{2}=10,\ (3x)^2=9x^2,\ (-2y)^3=-8y^3
    이므로 계수는
    10⋅9⋅(−8)=−72010\cdot9\cdot(-8)=-720
    이다.

조합론적 항등식: 파스칼 항등식

1≤k≤n1\le k\le n
일 때 다음이 성립한다.
(nk−1)+(nk)=(n+1k)\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}

이를 조합적으로 증명하기 위해
nn
개의 원소를 가진 집합
XX
에
XX
에는 없는 원소
aa
를 더해
Y=X∪{a}Y=X\cup\{a\}
를 만든다.
YY
의
kk
원소 부분집합을
aa
의 포함 여부에 따라 나눈다.
  • aa
    를 포함하지 않는 부분집합은
    XX
    에서 고른
    kk
    원소 부분집합이므로
    (nk)\binom{n}{k}
    개다.
  • aa
    를 포함하는 부분집합은
    XX
    에서
    k−1k-1
    개를 고른 뒤
    aa
    를 더한 것이므로
    (nk−1)\binom{n}{k-1}
    개다.
  • 두 경우는 서로 겹치지 않고 모든
    kk
    원소 부분집합을 포함한다. 따라서 두 개수를 더하면
    (n+1k)\binom{n+1}{k}
    가 된다.

비둘기집 원리

nn
개의 비둘기를
kk
개의 집에 넣고
n>kn>k
라면, 적어도 한 집에는 비둘기가 두 마리 이상 있다. 이 원리는 어떤 대상이 존재한다는 사실을 보일 뿐, 그 대상을 찾는 방법이나 그런 대상의 총개수까지 알려주지는 않는다.
대우를 이용한 증명: 모든 집에 비둘기가 최대 한 마리씩만 있다고 가정하면, 전체 비둘기 수는 최대
kk
마리다. 따라서 비둘기 수가
n>kn>k
라는 조건과 모순이다. 그러므로 적어도 한 집에는 두 마리 이상이 있어야 한다.
이름 조합 예시
사람 10명의 이름에서 이름은 Alice, Bernard, Charles 중 하나이고 성은 Lee, Ptoff, Ning 중 하나라고 하자. 가능한 이름 조합은
3×3=93\times3=9
개뿐이다. 10명을 9개 조합에 배정하므로, 적어도 두 사람은 이름과 성이 모두 같다.
함수와 집합을 이용한 형태
유한집합
X,YX,Y
와 함수
f:X→Yf:X\to Y
에 대해
∣X∣>∣Y∣|X|>|Y|
라면, 서로 다른
x1,x2∈Xx_1,x_2\in X
가 있어
f(x1)=f(x2)f(x_1)=f(x_2)
이다.
이는 비둘기를
XX
의 원소, 비둘기집을
YY
의 원소로 보고, 각
xx
를 함수값
f(x)f(x)
에 배정하는 것과 같다.
연속된 번호가 있는 과목 예시
서로 다른 컴퓨터과학 과목 151개의 번호가 1부터 300까지라고 하자. 각 과목 번호
cic_i
마다
cic_i
와
ci+1c_i+1
을 대응시키면 총 302개의 수가 생기며, 이 수들은 1부터 301까지의 범위에 있다. 따라서 302개의 수를 301개의 가능한 값에 대응시킨 셈이므로, 적어도 두 수가 같다.
같은 종류의 수끼리는 과목 번호가 서로 다르므로 중복될 수 없다. 따라서 같은 값을 만드는 두 수는 서로 다른 종류에서 하나씩 나와야 한다. 즉 어떤
i,ji,j
에 대해
ci=cj+1c_i=c_j+1
이며, 두 과목의 번호는 연속된다.
비둘기집 원리의 일반화
유한집합
X,YX,Y
에 대해
∣X∣=n, ∣Y∣=m|X|=n,\ |Y|=m
이고
f:X→Yf:X\to Y
라고 하자. 그러면 어떤
y∈Yy\in Y
는 적어도
k=⌈nm⌉k=\left\lceil\frac{n}{m}\right\rceil

개의 원소에서 함수값으로 나온다.
예를 들어
∣X∣=5, ∣Y∣=3|X|=5,\ |Y|=3
이면
k=⌈5/3⌉=2k=\lceil5/3\rceil=2
이므로, 적어도 두 원소가 같은 함수값을 갖는다.
증명 개요: 각
y∈Yy\in Y
에 대응하는 원소가 최대
k−1k-1
개라고 가정하면,
XX
의 원소 수는 최대
m(k−1)m(k-1)
이다. 따라서
n≤m(k−1)n\le m(k-1)
, 즉
n/m≤k−1n/m\le k-1
이어야 한다. 그러나
k=⌈n/m⌉k=\lceil n/m\rceil
이면
k−1<n/m≤kk-1<n/m\le k
이므로 모순이다. 따라서 어떤 함수값은 적어도
kk
개의 원소에서 나온다.
공개 노트 모두 보기