이항계수의 성질 (파스칼의 삼각형)
쉽게 풀면
이항계수 nCk는 "n개 중 k개를 고르는 방법의 수"입니다. 이 값들을 n=0부터 한 줄씩 삼각형 모양으로 늘어놓으면 아주 신기한 패턴이 보입니다. 맨 위와 양 옆은 항상 1이고, 나머지 칸은 바로 위 두 수를 더한 값과 같습니다. 예를 들어 5번째 줄의 가운데 근처 수는 4번째 줄의 이웃한 두 수를 더해서 나옵니다. 또한 각 줄은 좌우 대칭을 이루고(nCk = nC(n-k)), 한 줄에 있는 모든 수를 다 더하면 항상 2의 거듭제곱(2ⁿ)이 됩니다. 이런 규칙들 덕분에 복잡한 계산 없이도 이항계수 사이의 관계를 빠르게 파악할 수 있습니다.
왜 중요한가
이항계수의 성질은 조합론, 확률론, 알고리즘 분석 등 여러 분야에서 복잡한 식을 단순화하는 도구로 쓰입니다. 예를 들어 어떤 값의 상한이나 근사치를 구할 때, 매번 계승(factorial)을 직접 계산하는 대신 대칭성이나 파스칼의 규칙 같은 이미 알려진 관계를 이용하면 훨씬 빠르게 결론에 도달할 수 있습니다. 이 때문에 확률분포(특히 이항분포)의 성질을 증명하거나, 알고리즘의 시간복잡도를 경우의 수로 표현할 때 배경 지식으로 자주 등장합니다. 코딩이론이나 그래프 이론처럼 언뜻 무관해 보이는 분야에서도 조합적 개수를 세는 과정에 이항계수 항등식이 반복적으로 활용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 복잡해 보이는 조합적 계산을, 이항계수가 가진 규칙적인 성질을 이용해 더 간단한 형태로 바꾸었다는 뜻입니다. 조합론이나 알고리즘 복잡도 분석 논문에서 경우의 수를 다루는 기초 배경으로 자주 인용됩니다.
확률·통계 논문에서는 이항분포와 같은 확률모형의 성질을 증명할 때 이항계수의 합이나 대칭 관계를 보조 도구로 사용하는 경우가 많습니다. 계산 과정을 매번 처음부터 전개하지 않고, 이미 알려진 항등식을 인용해 논증을 압축하는 방식입니다.
코딩이론이나 정보이론 분야의 논문에서는 이항계수가 특정 구간에서 커지고 작아지는 성질(단조성)이나 근사식을 활용해, 조합적으로 정의된 값의 범위를 이론적으로 보이는 데 사용합니다.
조금 더 깊게 보면
이항계수의 성질을 더 깊이 들여다보면, 파스칼의 규칙 외에도 반데르몽드 항등식(Vandermonde's identity)처럼 서로 다른 이항계수의 곱을 합으로 표현하는 관계, 그리고 큰 n에 대해 이항계수를 근사적으로 다루는 스털링 근사(Stirling's approximation)와의 연결이 자주 언급됩니다. 논문에서 "이항계수의 상한을 근사한다"는 표현이 나오면 대체로 이런 근사 도구를 활용해 정확한 계승 계산을 피하고 있다는 뜻으로 이해하면 됩니다. 또한 이항계수는 파스칼 삼각형뿐 아니라 다항식 전개나 생성함수(generating function)의 계수로도 나타나므로, 조합론 논문에서는 생성함수 표현과 함께 등장하는 경우도 흔합니다.
주의할 점
이항계수의 성질은 이항정리와 헷갈리기 쉽지만 서로 다릅니다. 이항정리는 (a+b)ⁿ을 전개했을 때 각 항의 계수가 이항계수임을 보여주는 공식이고, 이항계수의 성질은 그 계수들 사이에 성립하는 대칭성·합·점화 관계 같은 규칙을 다룹니다.