판 비교
1번째 줄 근처
추가: ## 개요
추가: 조합(組合, combination)은 수학에서 유한 집합의 원소들 가운데 주어진 개수만큼을 순서를 고려하지 않고 선택하는 경우의 수를 뜻한다. 집합 \( S \)와 자연수 \( k \)가 주어졌을 때, \( S \)의 원소 \( k \)개를 중복 없이 골라 이루어진 부분집합을 \( k \)-조합이라 부른다. 이때 원소의 배열 순서는 상관하지 않으므로, 같은 원소로 이루어진 선택은 하나로 본다[1][2][3].
추가:
추가: ## 작동 방식과 유형
추가:
추가: ### 기본 조합 (중복 없는 조합)
추가:
추가: \( n \)개 원소의 집합에서 \( k \)개를 고르는 경우의 수는 이항 계수로 주어진다.
추가:
추가: \[
추가: \binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!} \qquad (0 \le k \le n)
추가: \]
추가:
추가: 이 공식은 \( n \)개 중 \( k \)개를 골라 순서를 붙여 나열하는 순열 \( P(n,k) = n(n-1)\cdots(n-k+1) \)을 \( k! \)로 나누어 순서의 중복을 제거함으로써 유도된다[2][3].
추가:
추가: #### 주요 항등식
추가:
추가: * 대칭성: \( \binom{n}{k} = \binom{n}{n-k} \) — \( k \)개를 고르는 것과 \( n-k \)개를 버리는 것은 일대일 대응한다.
추가: * 파스칼 규칙: \( \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \) — 특정 원소를 포함하는 경우와 포함하지 않는 경우로 나누어 센 결과다.
추가: * 생성 함수: \( (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k \) — 각 항의 계수가 \( k \)-조합의 수와 일치한다[2][3].
추가:
추가: #### 표기법
추가:
추가: 문헌과 지역에 따라 \( C(n,k) \), \( C_k^n \), \( _nC_k \), \( ^nC_k \), \( C_{n,k} \) 등 다양한 표기가 쓰인다[2][3].
추가:
추가: ### 중복조합 (Combination with repetition)
추가:
추가: 원소를 중복하여 선택할 수 있을 때, \( n \)종류의 원소 가운데 \( k \)개를 중복 허용하여 고르는 경우의 수는 다음과 같다.
추가:
추가: \[
추가: \binom{n+k-1}{k} = \binom{n+k-1}{n-1} = (-1)^k \binom{-n}{k}
추가: \]
추가:
추가: 표기로는 \( \left(\!\!\binom{n}{k}\!\!\right) \) 또는 \( _nH_k \)를 사용한다. 이는 \( a_1 \le a_2 \le \cdots \le a_k \)인 수열을 \( a_1, a_2+1, \dots, a_k+k-1 \)로 대응시켜 \( n+k-1 \)개 중 \( k \)개를 고르는 보통 조합과 일대일 대응시킴으로써 증명된다[2].
추가:
추가: ## 그 밖의 주제
추가:
추가: ### 계산적 측면
추가:
추가: * \( k > n/2 \)일 때는 대칭성 \( \binom{n}{k} = \binom{n}{n-k} \)를 이용해 계산량을 줄인다.
추가: * 팩토리얼 공식 \( n!/(k!(n-k)!) \)은 직관적이지만 큰 \( n \)에서 오버플로나 비효율이 생길 수 있어, 분자·분모를 약분하며 곱하는 \( \frac{n(n-1)\cdots(n-k+1)}{k!} \) 형태가 실용적이다[3].
추가: * 파스칼 삼각형을 구성하면 모든 이항 계수를 재귀적으로 구할 수 있다[3].
추가:
추가: ### 관련 개념
추가:
추가: * 순열(Permutation): 순서를 고려하는 선택. \( P(n,k) = C(n,k) \times k! \) 관계로 연결된다[3].
추가: * 이항 정리: \( (x+y)^n \) 전개 계수가 이항 계수와 일치한다[2][3].
추가: * 다항 계수: 조합을 여러 범주로 일반화한 개념[2].
추가:
추가: 이 문서는 GGWiki AI가 공개 자료(아래 출처)를 조사해 새로 쓴 초안입니다. 틀린 내용은 편집하거나 이의 제기로 알려 주세요.
