수학 에서조합 (組合,문화어 :영어 :combination )은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는이항 계수 로 주어진다.
5개 원소의 집합의 3원소 부분집합의 수는( 5 3 ) = 10 {\displaystyle \textstyle {\binom {5}{3}}=10} 집합 S {\displaystyle S} 자연수 k {\displaystyle k} S {\displaystyle S} (중복 없는)k {\displaystyle k} (영어 :k {\displaystyle k} S {\displaystyle S} k {\displaystyle k} 부분집합 을 일컫는다. 만약
S = { s 1 , s 2 , … , s n } {\displaystyle S=\{s_{1},s_{2},\dots ,s_{n}\}} 가n {\displaystyle n} 유한 집합 이며,0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} S {\displaystyle S} k {\displaystyle k} 이항 계수
( n k ) = n ( n − 1 ) ⋯ ( n − k + 1 ) k ! = n ! k ! ( n − k ) ! {\displaystyle {\binom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}={\frac {n!}{k!(n-k)!}}} 와 같다. 이항 계수( n k ) {\displaystyle \textstyle {\binom {n}{k}}}
조합의 수의 공식은조합론 의 방법으로 쉽게 유도할 수 있다.n {\displaystyle n} k {\displaystyle k} k {\displaystyle k} ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} k {\displaystyle k} k {\displaystyle k} k − 1 {\displaystyle k-1} n {\displaystyle n}
( n k ) k ! {\displaystyle {\binom {n}{k}}k!} 가지가 있다. 다른 한편, 첫 번째 자리에 놓을 원소를n {\displaystyle n} n − 1 {\displaystyle n-1}
n ( n − 1 ) ⋯ ( n − k + 1 ) {\displaystyle n(n-1)\cdots (n-k+1)} 이다. 세는 법이 다를 때 얻는 수가 같아야 하므로 원하는 공식을 얻는다.
이항 계수 들의파스칼의 삼각형 이항 계수 항등식
( n k ) = ( n n − k ) {\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}} ( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) {\displaystyle {\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}} 역시 조합론에서 직관적으로 해석할 수 있다. 전자는k {\displaystyle k} n − k {\displaystyle n-k} 일대일 대응 함을 나타낸다. 후자는k {\displaystyle k} n − 1 {\displaystyle n-1} k {\displaystyle k} n − 1 {\displaystyle n-1} k − 1 {\displaystyle k-1}
이항 계수 는 다음과 같이생성 함수 를 사용하여 정의할 수 있다.
( 1 + x ) n = ∑ k = 0 n ( n k ) x k {\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}} 조합론의 관점에서, 다항식( 1 + x ) n {\displaystyle (1+x)^{n}} n {\displaystyle n} 1 + x {\displaystyle 1+x} x {\displaystyle x} x {\displaystyle x} k {\displaystyle k} ( n k ) {\displaystyle \textstyle {\binom {n}{k}}} x k {\displaystyle x^{k}} ( n k ) {\displaystyle \textstyle {\binom {n}{k}}}
5개의 원소의 집합의 크기 3의 중복집합의 수는( 7 3 ) = 35 {\displaystyle \textstyle {\binom {7}{3}}=35} 집합 S {\displaystyle S} 자연수 k {\displaystyle k} S {\displaystyle S} k {\displaystyle k} 영어 :k {\displaystyle k} S {\displaystyle S} k {\displaystyle k} 중복집합 이다.n {\displaystyle n} S = { s 1 , s 2 , … , s n } {\displaystyle S=\{s_{1},s_{2},\dots ,s_{n}\}} k {\displaystyle k}
( n + k − 1 k ) = ( n + k − 1 n − 1 ) = ( − 1 ) k ( − n k ) {\displaystyle {\binom {n+k-1}{k}}={\binom {n+k-1}{n-1}}=(-1)^{k}{\binom {-n}{k}}} 이다. 중복조합의 수( n + k − 1 k ) {\displaystyle \textstyle {\binom {n+k-1}{k}}}
중복조합의 수가( n + k − 1 k ) {\displaystyle \textstyle {\binom {n+k-1}{k}}} { a 1 , ⋯ , a k } {\displaystyle \{a_{1},\cdots ,a_{k}\}} { 1 , … , n } {\displaystyle \{1,\dots ,n\}} k {\displaystyle k}
a 1 ≤ a 2 ≤ ⋯ ≤ a k {\displaystyle a_{1}\leq a_{2}\leq \cdots \leq a_{k}} 라면,
{ a 1 , a 2 + 1 , … , a k + k − 1 } {\displaystyle \{a_{1},a_{2}+1,\dots ,a_{k}+k-1\}} 는{ 1 , … , n + k − 1 } {\displaystyle \{1,\dots ,n+k-1\}} k {\displaystyle k} { 1 , … , n + k − 1 } {\displaystyle \{1,\dots ,n+k-1\}} k {\displaystyle k}
{ b 1 , … , b k } {\displaystyle \{b_{1},\dots ,b_{k}\}} b 1 < b 2 < ⋯ < b k {\displaystyle b_{1}<b_{2}<\cdots <b_{k}} 이 주어졌을 때,
{ b 1 , b 2 − 1 , … , b k − k + 1 } {\displaystyle \{b_{1},b_{2}-1,\dots ,b_{k}-k+1\}} 는{ 1 , … , n } {\displaystyle \{1,\dots ,n\}} k {\displaystyle k} { 1 , … , n } {\displaystyle \{1,\dots ,n\}} k {\displaystyle k} { 1 , … , n + k − 1 } {\displaystyle \{1,\dots ,n+k-1\}} k {\displaystyle k} 일대일 대응 을 정의한다. 따라서 이들의 수는 같다. 후자의 수가( n + k − 1 k ) {\displaystyle \textstyle {\binom {n+k-1}{k}}}
이와 다른기하학 적 증명이 존재한다.( n + k − 1 k ) {\displaystyle \textstyle {\binom {n+k-1}{k}}} n − 1 {\displaystyle n-1} k {\displaystyle k} n + k − 1 {\displaystyle n+k-1} { 1 , … , n } {\displaystyle \{1,\dots ,n\}} k {\displaystyle k} n − 1 {\displaystyle n-1} n {\displaystyle n} n {\displaystyle n} i {\displaystyle i} i {\displaystyle i} k {\displaystyle k} k {\displaystyle k} n = 3 {\displaystyle n=3} k = 5 {\displaystyle k=5}
| ◯ ◯ ◯ | ◯ ◯ {\displaystyle |{\bigcirc }{\bigcirc }{\bigcirc }|{\bigcirc }{\bigcirc }} 은 중복집합{ 2 , 2 , 3 , 3 , 3 } {\displaystyle \{2,2,3,3,3\}}
◯ | ◯ ◯ ◯ | ◯ {\displaystyle {\bigcirc }|{\bigcirc }{\bigcirc }{\bigcirc }|{\bigcirc }} 은 중복집합{ 1 , 2 , 2 , 2 , 3 } {\displaystyle \{1,2,2,2,3\}} { 1 , … , n } {\displaystyle \{1,\dots ,n\}} k {\displaystyle k} n − 1 {\displaystyle n-1} k {\displaystyle k} ( n + k − 1 k ) {\displaystyle \textstyle {\binom {n+k-1}{k}}}
중복조합의 수의생성 함수 는 다음과 같다.
( 1 − x ) − n = ∑ k = 0 ∞ ( − n k ) ( − x ) k = ∑ k = 0 ∞ ( n + k − 1 k ) x k {\displaystyle (1-x)^{-n}=\sum _{k=0}^{\infty }{\binom {-n}{k}}(-x)^{k}=\sum _{k=0}^{\infty }{\binom {n+k-1}{k}}x^{k}} 좌변의( 1 − x ) − 1 {\displaystyle (1-x)^{-1}} 멱급수 로 전개하면1 + x + x 2 + ⋯ {\displaystyle 1+x+x^{2}+\cdots } n {\displaystyle n} x m i {\displaystyle x^{m_{i}}} i = 1 , … , n {\displaystyle i=1,\dots ,n} i {\displaystyle i} m i {\displaystyle m_{i}} 중복집합 을 선택하는 방법과일대일 대응 한다.n {\displaystyle n} x k {\displaystyle x^{k}}
m 1 + ⋯ + m n = k {\displaystyle m_{1}+\cdots +m_{n}=k} 인 경우이다. 즉, 크기k {\displaystyle k} x k {\displaystyle x^{k}} ( n + k − 1 k ) {\displaystyle \textstyle {\binom {n+k-1}{k}}}
