조합

수학에서 조합(合合, )은 서로 다른 구성원을 갖는 집합에서 항목을 선택하는 것으로, 순열과는 달리 선택 순서가 중요하지 않습니다.예를 들어, 사과, 오렌지, 배 등 세 가지 과일이 주어졌을 때, 이 세트에서 추출할 수 있는 두 가지 조합은 사과와 배, 사과와 오렌지, 또는 배와 오렌지의 세 가지입니다.좀 더 형식적으로, 집합 S의 k-조합은 S의 k개의 서로 다른 원소들의 부분집합이므로, 각각의 조합이 동일한 원소를 갖는 경우에만 두 조합이 동일합니다. (각 집합의 원소들의 배열은 중요하지 않습니다.)집합에 n개의 요소가 있는 경우, C $C(n,k)$ ) $C(n,k)$ {\ $displaystyle$ C $(n,k)}$ $C_{k}^{n}$ $C_{k}^{n}$ {\ $displaystyle C_{$ k}^{ $n$ 로 표시되는 k-조합의 수는 이항 계수와 같습니다.

{\binom {n}{k}}={\frac {n(n-1)\nb(n-k+1)}{k(k-1)\nb1}},

$\textstyle {\frac {n!}{k!(n-k)!}}$ ! $\textstyle {\frac {n!}{k!(n-k)!}}$ ! ( $\textstyle {\frac {n!}{k!(n-k)!}}$ - $\textstyle {\frac {n!}{k!(n-k)!}}$ ) ! ${\$ {\ $frac {n!$ $} {k!(n-k)!$ $}}}$ k $k\leq n$ $k\leq n$ ${\displaystyle$ k $\leq$ n $k\leq n$ 일 $k\leq n$ 마다, k $k>n$ > $k>n$ ${\displaystyle$ k> $n$ 일 때 0입니다. 이 공식은 n개의 멤버로 이루어진 집합 S의 각 k-조합이 k $!$ {\ $displaystyle$ k $!}$ 개의 순열을 $P_{k}^{n}=C_{k}^{n}\times k!$ $P_{k}^{n}=C_{k}^{n}\times k!$ $P_{k}^{n}=C_{k}^{n}\times k!$ n $=$ $C$ k $n$ × $P_{k}^{n}=C_{k}^{n}\times k!$ k $!$ {\ $displaystyle P_{k}^{n}$ $=$ C_{k $}^{n$ }\ $C_{k}^{n}=P_{k}^{n}/k!$ k $C_{k}^{n}=P_{k}^{n}/k!$ {\ $displaystyle C_{k}^{n$ } $=$ P_{ $k}^{{$ k}^{{}} $n}/k$ ^[1]집합 S의 모든 k-조합의 집합은 종종 ( $\textstyle {\binom {S}{k}}$ {\ $displaystyle \textstyle$ {\ $binom {S}{k$ 로 $\textstyle {\binom {S}{k}}$ 표시됩니다.

조합은 반복하지 않고 한 번에 k개의 것을 조합한 것입니다.반복이 허용되는 조합을 지칭하기 위해 k-조합과 반복, k-다중 ^[2]집합 또는 ^[3]k-선택이라는 용어가 자주 ^[4]사용됩니다.만약 위의 예에서, 어떤 한 종류의 과일이라도 두 개를 먹을 수 있다면, 두 개의 사과, 두 개의 오렌지, 그리고 두 개의 배와 같은 세 개의 두 가지 선택이 더 있을 것입니다.

비록 3개의 과일 세트가 전체 조합 목록을 작성할 만큼 충분히 작았지만, 이것은 세트의 크기가 증가함에 따라 실용적이지 않게 됩니다.예를 들어, 포커 핸드는 52 카드 덱(n = 52)의 카드들의 5-조합(k = 5)으로 묘사될 수 있습니다.손의 5장의 카드는 모두 다르며, 손에 든 카드의 순서는 상관없습니다.이러한 조합은 2,598,960개이며 임의로 한 손을 그릴 확률은 1/2,598,960입니다.

k-조합횟수

n개 요소의 주어진 집합 S에서 k-조합의 수는 종종 C $C(n,k)$ ) $C(n,k)$ {\ $displaystyle$ C $(n,k$ $C(n,k)$ $C_{k}^{n}$ ${\$ ${}_{n}C_{k}$ ${}_{n}C_{k}$ {\ $displaystyle {}_{n}C_{k$ ${}^{n}C_{k}$ ${}^{n}C_{k}$ {\ $displaystyle {}^{n}C_{k$ , $C_{n,k}$ k {\ $displaystyle C_{n,$ k $C_{n,k}$ }, $C_{n}^{k}$ $C_{n}^{k}$ {\ $displaystyle$ C_{n}{ $n$ }와 $C_{n,k}$ $C_{k}^{n}$ 으로 표시됩니다 $.$ $}^{k}}($ ^[5]마지막 형식은 프랑스어, 루마니아어, 러시아어^[6]^[7], 중국어 및 폴란드어^{[citation needed]} 텍스트에서 표준 형식입니다.)그러나 동일한 숫자는 다른 많은 수학적 맥락에서 발생하며, 이는 ( ${\tbinom {n}{k}}$ k ${\tbinom {n}{k}}$ {\ $displaystyle$ {\ $tbinom {n}{k}}($ 흔히 "n choose k"로 읽힙니다 ${\tbinom {n}{k}}$ 로 표시됩니다. 특히 이항식에서 계수로 발생하므로 이항 계수라는 이름이 붙습니다.모든 자연수 k에 대해 ( ${\tbinom {n}{k}}$ {\ $displaystyle$ {\ $tbinom {n}{k}}}$ 을 ${\tbinom {n}{k}}$ ${\tbinom {n}{k}}$ 를) 관계식으로 한 번에 정의할 수 있습니다.

{\displaystyle(1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k}}

는 것이 분명합니다.

{\binom {n}{0}}={\binom {n}}=1,

그리고 더 나아가,

{\binom {n}{k}}=0

포크 > n

이 계수들이 S에서 k-조합을 계산한다는 것을 알기 위해서는 먼저 S의 원소로 표시된 n개의 구별되는_s 변수 X의 집합을 고려하고 S의 모든 원소로 곱을 확장할 수 있습니다.

\prod _{s\in S}(1+X_{s});

S의 모든 부분 집합에 해당하는 두 개의 다른 항이 있으며ⁿ, 각 부분 집합은 해당 변수_s X의 곱을 제공합니다.이제 곱이_s (1 + X)ⁿ가 되도록 모든 X를 무표지 변수 X와 같게 설정하면 S에서 각 k-조합에 대한 항이 X가^k 되어 결과에서 해당 거듭제곱의 계수가 이러한 k-조합의 수와 같아집니다.

이항 계수는 다양한 방법으로 명시적으로 계산할 수 있습니다.(1 + X)ⁿ까지의 확장을 위해 모든 확장 값을 얻으려면 (이미 주어진 기본적인 경우 외에도) 재귀 관계를 사용할 수 있습니다.

{\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}

(1 + X) = (1 + X) (1 + X) (1 + X)로 이어지는 0 < k < n에 대하여; 이것은 파스칼의 삼각형의 구성으로 이어집니다.

개별 이항 계수를 결정하려면 공식을 사용하는 것이 더 실용적입니다.

{\binom {n}{k}}={\frac {n(n-1)(n-1)(n-1)\cdots(n-k+1)}{k!}}.

분자는 n의 k-순열, 즉 S의 k개의 개별 요소의 시퀀스의 수를 제공하는 반면 분모는 순서가 무시될 때 동일한 k-조합을 제공하는 그러한 k-순열의 수를 제공합니다.

k가 n/2를 초과할 때, 위 공식은 분자와 분모에 공통된 인자를 포함하고, 이를 취소하면 관계가 나타납니다.

{\binom {n}{k}}={\binom {n}{n-k}}

0 ≤ k ≤ n인 경우.이는 이항식에서 명확하게 나타나는 대칭을 표현하며, 또한 (n - k)-조합인 그러한 조합의 상보를 취함으로써 k-조합의 관점에서 이해될 수 있습니다.

마지막으로 이러한 대칭성을 직접적으로 나타내는 공식이 있으며, 기억하기 쉬운 장점이 있습니다.

{\binom {n}{k}}={\frac {n!}{k!(n-k)!}},

여기서 n!은 n의 계승을 나타냅니다.분모와 분자에 (n - k)!를 곱하여 앞의 공식에서 구하므로 그 공식보다 계산 효율이 확실히 떨어집니다.

마지막 공식은 S의 모든 원소들의 n! 순열을 고려하여 직접적으로 이해할 수 있습니다.이러한 각 순열은 첫 번째 k 요소를 선택하여 k 조합을 제공합니다.여러 가지 중복 선택이 있습니다. 처음 k개의 원소를 서로 결합하고 최종 (n - k)개의 원소를 서로 결합하면 동일한 조합이 생성됩니다. 이것은 공식에서 나눗셈을 설명합니다.

위의 공식으로부터 파스칼의 삼각형의 인접한 수들 사이의 관계를 세 방향 모두 따라갑니다.

{\displaystyle {\binom {n}{k}}={\display{case}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\display{\text{n-1}{k}}{\frac {n}{n-k}}&\displaystyle {\text{n}{k-1}}{k<n\{\binom {n-1}}{k-1}}{\frac {n}{k}}&displaystyle {\text{if}},k>0\end{case}}}.

기본 ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ 사례 ( ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ 0 ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ ) = ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ = ( ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ {\ $displaystyle$ {\ $tbinom {n}{0$ }} = ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ 1 = {\ $tbinom {n}{n$ 와 함께, 이는 동일한 집합(파스칼 삼각형의 행)의 모든 수의 조합, 성장하는 크기의 집합의 k-조합 및 고정된 크기의 n - k의 상보를 갖는 조합의 연속적인 계산을 허용합니다.

조합 세기 예제

구체적인 예로, 표준 52장 카드 덱에서 가능한 5장의 카드 핸드 수를 다음과 ^[8]같이 계산할 수 있습니다.

{\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}=2{,}598{,}960}.

또는 공식을 요인 단위로 사용하여 분자 내 요인을 분모 내 요인의 일부에 대해 취소할 수 있으며, 그 후 나머지 요인의 곱셈만 필요합니다.

{\display{alignat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\times {47!}}}{5\time 4\time 3\time 2\time {\time {1}}\time {\time {47!}}\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\[5pt]&={\frac {(26\times {2}}\times {17\times {3}}\times {\times {5}}\times {12\times {4}}{\times {5}}\times {\times {4}}\times {\times {3}}\[5pt]&={26\times 17\times 10\times 49\times.imes 12}\[5pt]&=2{,}598{,}960.\end{alignedat}

첫번째와 같은 또 다른 대안적인 계산은 글쓰기를 기반으로 합니다.

{n \choose k}={\frac {(n-1)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-1)}{3}}\times \cdots \times {\frac {(n-(k-1))}}{k}},

이에 해당되는

{52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}=2{,}598{,}960.

52 ÷ $1$ × $51$ ÷ $2$ ÷ $50$ ÷ $3$ × $49$ ÷ $4$ × $48$ 5 5의 $순서$ 로 평가할 때, 이는 정수 연산만으로 계산할 수 있습니다.그 이유는 각 분할이 발생할 때 생성되는 중간 결과가 그 자체로 이항 계수이므로 나머지가 발생하지 않기 때문입니다.

단순화를 수행하지 않고 요인 단위로 대칭 공식을 사용하면 다음과 같은 계산이 가능합니다.

{\display{align}{52 \choose 5}&={\frac {n!} {k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\[6pt]&={\tfrac {80,658,175,170,943,878,571,189,636,856,403,766,975,289,505,440,883,277,824,000,000}{120\times 258,623,241,511,168,180,642,964,355,632,389,120,000,000}\[6pt]&=2{,598{,560}.\end{aligned}

k-조합 열거하기

n개 요소의 주어진 집합 S의 모든 k-조합을 어떤 고정된 순서로 열거할 수 있으며, 이는 k-조합의 집합과 함께 ( ${\tbinom {n}{k}}$ k ${\tbinom {n}{k}}$ {\ $displaystyle$ {\ $tbinom {n}{k}}$ 개 ${\tbinom {n}{k}}$ 정수의 ${\tbinom {n}{k}}$ 구간에서 빗변을 설정합니다.예를 들어, S = {1, 2, ..., n }와 같이 S 자체가 순서화되었다고 가정하면, k-조합을 순서화하는 데는 (위의 그림에서와 같이) 가장 작은 원소를 먼저 비교하거나 가장 큰 원소를 먼저 비교하는 두 가지 자연스러운 가능성이 있습니다.후자의 옵션은 S에 새로운 가장 큰 요소를 추가하면 열거의 초기 부분이 변경되지 않고 이전의 k-조합 다음에 큰 집합의 새로운 k-조합을 추가할 수 있다는 장점이 있습니다.이 과정을 반복하면 더 큰 집합의 k-조합으로 열거를 무한히 확장할 수 있습니다.또한 정수의 간격을 0에서 시작하도록 하면, 열거의 주어진 장소 i에서 k-조합은 i로부터 쉽게 계산될 수 있으며, 그렇게 얻은 비사법은 조합수 체계로 알려져 있습니다.컴퓨터 ^[9]^[10]수학에서는 "순위"/"순위" 또는 "순위"라고도 합니다.

k개의 조합을 열거하는 방법은 여러 가지가 있습니다.한 가지 방법은 2보다 작은ⁿ 모든 이진수를 방문하는 것입니다.n이 작은 경우에도 매우 비효율적이지만(예: n = 20의 경우 약 백만 개의 숫자를 방문해야 하는 반면 k = 10의 경우 최대 허용 k 조합 수가 약 186,000개임), 0 비트가 아닌 숫자를 선택합니다.이러한 숫자에서 이 1비트의 위치는 {1, ..., n}^[11] 집합의 특정 k-조합입니다. 또 다른 간단하고 빠른 방법은 {0}부터 시작하여 선택된 원소의 k 인덱스 번호를 추적하는 것입니다.k-1}(0 기준) 또는 {1.. k}(1 기준)를 처음 허용된 k-조합으로 설정한 후 n-1(0 기준) 또는 n(1 기준)보다 낮거나 n(1 기준)보다 작은 마지막 인덱스 번호 x를 증가시켜 다음에 허용된 k-조합으로 반복적으로 이동한 후 재설정하는 인덱스가 있는 경우 1을 뺀 값x 뒤의 색인 번호를 {x+1, x+2, ...}(으)로 변경합니다.

반복이 있는 조합 수

반복이 있는 k-조합, 또는 k-다중조합, 또는 크기 n의 집합 S에서 크기 k의 다중 부분집합은 반드시 구분되지 않는 S의 k개의 요소 집합에 의해 주어지는데, 여기서 순서는 고려되지 않습니다. 두 수열은 하나가 항을 순열함으로써 다른 것으로부터 얻을 수 있다면 동일한 다중집합을 정의합니다.즉, 중복(즉, 대체)을 허용하지만 다른 순서(예: {2,1,2} = {1,2,2})를 무시하는 n개 요소 집합에서 k개 요소의 샘플입니다.S의 각 원소에 인덱스를 연결하고 S의 원소를 개체 유형으로 생각하면 다중 부분 집합에서 유형 i의 원소 개수를 $x_{i}$ {\ $displaystyle$ x_ ${i}$ 로 $x_{i}$ $x_{i}$ 수 있습니다.크기 k의 다중 부분집합의 수는 디오판토스 ^[12]방정식의 음이 아닌 정수의 수이다.

x_{1}+x_{2}+\ldots +x_{n}=k.

S가 n개의 원소를 가질 경우, 이러한 k-다중 부분집합의 수는 다음과 같이 표시됩니다.

\left(\!\!{\binom {n}{k}}\!\!\right),

k-소문자 집합을 계산하는 이항 계수와 유사한 표기법입니다.이 식(다중 선택)^[13]은 이항 계수로 나타낼 수도 있습니다.

\left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}

이 관계는 별과 ^[14]막대로 알려진 표현을 사용하여 쉽게 증명될 수 있습니다.

증명

위 디오판토스 방정식의 해는 $x_{1}$ 1 $x_{1}$ {\ $displaystyle x_{1}}$ 개의 $x_{1}$ 별, 구분자( $x_{2}$ ), $x_{2}$ 2 $x_{2}$ {\ $displaystyle x_{2}}$ 개의 $x_{2}$ 별, 다른 구분자 등으로 $x_{1}$ 수 있습니다.이 표현에서 별의 총 개수는 k개이고 막대의 개수는 n - 1개입니다(n개의 부분으로 분리하려면 n-1개의 구분자가 필요하므로).따라서 k + n - 1 (또는 n + k - 1) 기호의 문자열(별과 막대)은 문자열에 k개의 별이 있는 경우 해에 해당합니다.모든 해는 k + n - 1 위치 중 k를 선택하여 별을 배치하고 나머지 위치를 막대로 채우는 방법으로 나타낼 수 있습니다.예를 들어, $x_{1}+x_{2}+x_{3}+x_{4}=10$ x $x_{1}+x_{2}+x_{3}+x_{4}=10$ + $x_{1}+x_{2}+x_{3}+x_{4}=10$ $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ + $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ 3 + x $x_{1}+x_{2}+x_{3}+x_{4}=10$ + $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ 의 $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ x $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ = $, x_{2$ } = $2,x_{3$ } = 0 $,$ x_{4} = 5 {\ $displaystyle x_{1}$ + $x_$ } + x_ $x_{1}+x_{2}+x_{3}+x_{4}=10$ } + $x_{1}+x_{2}+x_{3}+x_{4}=10$ { $3}$ = 0, $x_$ ${\$ displaystyle x_{ $2$ } + $x_{3$ } + $x_{4}$ } $=10}($ n $=$ 4 및 k $=$ 10)은 다음과 같이 나타낼 수 있습니다 $.$

{\display style \bigstar \bigstar \bigstar \bigstar \bigstar \bigstar \bigstar \bigstar \bigstar .}

이러한 문자열의 수는 13개의 위치에 10개의 별을 배치하는 방법의 수이며 ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ ( ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ 10 ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ = ( ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ ) = ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ ${\textstyle$ {\ $binom {13}{10$ }} = {\ $binom {13}{3$ }} = $286,},$ 이는 4개의 원소를 가진 집합의 10개의 다중 부분 집합의 수이다.

이항 계수의 경우와 마찬가지로, 이러한 다중 선택 식 사이에는 여러 가지 관계가 있습니다.예를 들어, $n\geq 1,k\geq 0$ $n\geq 1,k\geq 0$ $n\geq 1,k\geq 0$ $n\geq 1,k\geq 0$ $n\geq 1,k\geq 0$ $n\geq 1,k\geq 0$ {\ $displaystyle$ n $\geq$ 1 $,k\geq$ 0 $n\geq 1,k\geq 0$

\left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).

이 정체성은 위의 ^[16]표현에서 별들과 막대들을 교환하는 것에서 비롯됩니다.

다중 부분 집합 카운트 예제

예를 들어, 선택할 메뉴에 4종류의 도넛(n = 4)이 있고 3개의 도넛(k = 3)을 원한다면, 반복되는 도넛을 선택하는 방법의 수는 다음과 같이 계산될 수 있습니다.

\left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.

이 결과는 집합 S = {1,2,3,4}의 모든 3-다중 부분 집합을 나열하여 확인할 수 있습니다.이는 다음 ^[17]표에 표시됩니다.두 번째 열에는 실제로 선택한 도넛이 나열되어 있고, 세 번째 열에는 $x_{1}+x_{2}+x_{3}+x_{4}=3$ $x_{1}+x_{2}+x_{3}+x_{4}=3$ 1 $x_{1}+x_{2}+x_{3}+x_{4}=3$ + $x_{1}+x_{2}+x_{3}+x_{4}=3$ + $x_{1}+x_{2}+x_{3}+x_{4}=3$ 3 + $x_{1}+x_{2}+x_{3}+x_{4}=3$ $x_{1}+x_{2}+x_{3}+x_{4}=3$ 의 음이 아닌 정수 $[x_{1},x_{2},x_{3},x_{4}]$ 해 [ $[x_{1},x_{2},x_{3},x_{4}]$ 1 $[x_{1},x_{2},x_{3},x_{4}]$ $[x_{1},x_{2},x_{3},x_{4}]$ $[x_{1},x_{2},x_{3},x_{4}]$ $[x_{1},x_{2},x_{3},x_{4}]$ $[x_{1},x_{2},x_{3},x_{4}]$ $x_{1}+x_{2}+x_{3}+x_{4}=3$ $[x_{1},x_{2},x_{3},x_{4}]$ 4 $[x_{1},x_{2},x_{3},x_{4}]$ {\ $displaystyle [x_{1}, x_{2}, x_{3}, x_{4}$ = $x_{1}+x_{2}+x_{3}+x_{4}=3$ {\ $displaystyle x_{1}$ + $x_{2}$ + $x_{3}$ + $x_{4$ ]가 표시됩니다. $}=3}$ 이며 마지막 열에는 해를 나타내는 별과 막대가 표시됩니다.

아니요.	3세트	등식해	별과 막대
1	{1,1,1}	[3,0,0,0]	$\bigstar \bigstar \bigstar$
2	{1,1,2}	[2,1,0,0]	$\bigstar \bigstar \bigstar$
3	{1,1,3}	[2,0,1,0]	$\bigstar \bigstar \bigstar$
4	{1,1,4}	[2,0,0,1]	$\bigstar \bigstar \bigstar$
5	{1,2,2}	[1,2,0,0]	$\bigstar \bigstar \bigstar$
6	{1,2,3}	[1,1,1,0]	$\bigstar \bigstar \bigstar$
7	{1,2,4}	[1,1,0,1]	$\bigstar \bigstar \bigstar$
8	{1,3,3}	[1,0,2,0]	$\bigstar \bigstar \bigstar$
9	{1,3,4}	[1,0,1,1]	$\bigstar \bigstar \bigstar$
10	{1,4,4}	[1,0,0,2]	$\bigstar \bigstar \bigstar$
11	{2,2,2}	[0,3,0,0]	$\bigstar \bigstar \bigstar$
12	{2,2,3}	[0,2,1,0]	$\bigstar \bigstar \bigstar$
13	{2,2,4}	[0,2,0,1]	$\bigstar \bigstar \bigstar$
14	{2,3,3}	[0,1,2,0]	$\bigstar \bigstar \bigstar$
15	{2,3,4}	[0,1,1,1]	$\bigstar \bigstar \bigstar$
16	{2,4,4}	[0,1,0,2]	$\bigstar \bigstar \bigstar$
17	{3,3,3}	[0,0,3,0]	$\bigstar \bigstar \bigstar$
18	{3,3,4}	[0,0,2,1]	$\bigstar \bigstar \bigstar$
19	{3,4,4}	[0,0,1,2]	$\bigstar \bigstar \bigstar$
20	{4,4,4}	[0,0,0,3]	$\bigstar \bigstar \bigstar$

모든 k에 대한 k-조합의 수

모든 k에 대한 k-조합의 수는 n개 원소 집합의 부분 집합의 수이다.이 숫자가 2라는ⁿ 것을 알 수 있는 몇 가지 방법이 있습니다.조합의 ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ , ∑ ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ≤ ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ( ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ n ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ ) ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ = ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ n {\ $textstyle$ \ $sum _{0\leq$ { $k}\leq$ {n $}}{\binom {$ n}{k}}= $2^{$ n ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$ 이며, 이는 파스칼의 삼각형에서 이항 계수의 n번째 행(0에서 제외)의 합입니다.이러한 조합(부분 집합)은 0에서 2ⁿ - 1까지 세는 기본 2개 숫자 집합의 1자리로 열거되며, 여기서 각 숫자 위치는 n 집합의 항목입니다.

1부터 3까지 번호가 매겨진 3장의 카드에는 빈 세트를 포함하여 8개의 다른 조합(부분 집합)이 있습니다.

\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\} =2^{3}=8

다음과 같은 부분집합(같은 순서로)을 밑수 2와 같이 나타냄:

0 – 000
1 – 001
2 – 010
3 – 011
4 – 100
5 – 101
6 – 110
7 – 111

확률: 랜덤 조합 표본 추출

주어진 집합 또는 목록에서 임의의 조합을 선택하는 다양한 알고리즘이 있습니다.기각 샘플링은 표본 크기가 큰 경우 매우 느립니다.크기 n의 모집단으로부터 k-조합을 효율적으로 선택하는 한 가지 방법은 모집단의 각 요소에 걸쳐 반복하는 것입니다.각 단계에서 k - ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ # ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ - ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ # ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ 이 ${\$ {\ $frac {k-\#{\text{samples$ visited $}}}{n-\#{\text{samples$ visited $}}}}($ 저장고 샘플링 참조).다른 하나는 ( $\textstyle {\binom {n}{k}}$ k $\textstyle {\binom {n}{k}}$ ${\$ {\ $binom {n}{k}}}$ 보다 $\textstyle {\binom nk}$ $\textstyle {\binom {n}{k}}$ 작은 임의의 음이 아닌 정수를 선택하고 조합수 체계를 사용하여 조합으로 변환하는 것입니다.

사물을 통에 넣는 방법의 수

조합은 선택된 빈에 들어가는 항목과 선택되지 않은 빈에 들어가는 항목의 두 세트의 선택으로도 생각할 수 있습니다.이것은 모든 항목이 정확히 하나의 빈으로 가야 한다는 제약 조건과 함께 임의의 수의 빈으로 일반화될 수 있습니다.개체를 빈에 넣는 방법의 수는 다항식 계수로 표시됩니다.

{n \choose k_{1},k_{2},\ldots,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}

여기서 n은 아이템의 개수, m은 빈의 개수, $k_{i}$ {\ $displaystyle k_{$ i $k_{i}$ }는 빈에 들어가는 아이템의 개수입니다.

이 방정식이 성립하는 이유를 알 수 있는 한 가지 방법은 먼저 개체에 임의로 1부터 n까지 번호를 매기고, $,$ $1,2,\ldots ,k_{1}$ …, $1,2,\ldots ,k_{1}$ 1 {\ $displaystyle$ 1, $2,\$ ldots $,k_{1}},$ $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ + $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ …, $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ 2 $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ {\ $displaystyle k_{1}+1, k_{1}+2,\ldots,k_{2}}$ 를 $k_{1}+1,k_{1}+2,\ldots ,k_{2}$ 순서대로 두 번째 빈에 넣는 것입니다.n $!{\displaystyle$ n $!}$ 개의 $n!$ 구별되는 숫자가 $있지만$ , 많은 숫자가 동일합니다. 왜냐하면 빈 안에 있는 항목의 순서가 중요하지 않기 때문입니다.각 빈의 내용을 조합할 때마다 항목을 빈에 넣는 동일한 방식이 생성됩니다.결과적으로 모든 동등성 클래스는 $k_{1}!\,k_{2}!\cdots k_{m}!$ ! $k_{1}!\,k_{2}!\cdots k_{m}!$ $k_{1}!\,k_{2}!\cdots k_{m}!$ ! $k_{1}!\,k_{2}!\cdots k_{m}!$ ⋯ k $k_{1}!\,k_{2}!\cdots k_{m}!$ m ! {\ $displaystyle$ k_ ${1$ } !\, $k_{$ 2} !\ $cdots k_{$ m} !}개의 서로 다른 숫자로 $k_{1}!\,k_{2}!\cdots k_{m}!$ 되며, 동등성 클래스의 $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ 는 $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ ! $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ k $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ ! k $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ ! ⋯ $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ m $\textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}$ ! ${\displaystyle$ \textstyle ${\frac {n!$ $}{k_{1}!\,k_{2}!\cdots k_{m}!$ $}}}$ .

이항 계수는 k개의 항목이 선택된 빈에 들어가고 $n-k$ n $n-k$ - $n-k$ 의 {\ $displaystyle n-k}$ 개의 $n-k$ 항목이 선택되지 않은 빈에 들어가는 특수한 경우입니다.

{\binom {n}{k}}={n \choose k,n-k}={\frac {n!} {k!(n-k)!}}.

참고 항목

메모들

^ Reichl, Linda E. (2016). "2.2. Counting Microscopic States". A Modern Course in Statistical Physics. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0.
^ 마주르 2010, 페이지 10
^ Ryser 1963, p. 7은 순서 없는 선택이라고도 언급됩니다.
^ (2010년 브루알디처럼) 두 가지 상황 중 하나를 지칭하기 위해 조합이라는 용어를 사용할 경우, 집합 또는 다중 집합이 논의되고 있는지 여부를 명확히 하기 위해 주의를 기울여야 합니다.
^ 우스펜스키 1937, 페이지 18
^ High School Textbook for full-time student (Required) Mathematics Book II B (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. ISBN 978-7-107-19616-4.
^ 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press). People's Education Press. p. 21.
^ 마주르 2010, 페이지 21
^ Lucia Moura. "Generating Elementary Combinatorial Objects" (PDF). Site.uottawa.ca. Archived (PDF) from the original on 9 October 2022. Retrieved 10 April 2017.
^ "SAGE : Subsets" (PDF). Sagemath.org. Retrieved 10 April 2017.
^ "Combinations - Rosetta Code". 23 October 2022.^{[사용자 생성 소스?]}
^ 브루알디 2010, 페이지 52
^ Benjamin & Quinn 2003, p. 70
^ 기사에서 별과 막대(콤비네이터)는 $n$ 과 k의 역할이 반대입니다.
^ Benjamin & Quinn 2003, 페이지 71–72
^ Benjamin & Quinn 2003, p. 72 (아이덴티티 145)
^ Benjamin & Quinn 2003, 페이지 71
^ Mazur 2010, p. 10 여기서 별과 막대는 이진수로 표기되며, 별은 = 0이고 막대는 = 1입니다.

참고문헌

Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5
Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America
Uspensky, James (1937), Introduction to Mathematical Probability, McGraw-Hill

외부 링크

조합론에 대한 최상위 코드 자습서
질문으로 선택한 n개 원소의 모든 조합을 생성하는 C 코드
자세한 풀이를 포함한 많은 일반적인 유형의 순열 및 조합 수학 문제
Unknown formula 선택이 반복될 수 있고 순서가 중요하지 않을 때의 조합에 대한 Unknown formula
반복이 있는 조합(다음 기준)Akshatha AG and Smitha B)^{[영구 데드링크]}
주어진 합 문제를 갖는 주사위 굴림 복수의 주사위 굴림에 대한 반복을 갖는 조합의 적용

[1] Reichl, Linda E. (2016). "2.2. Counting Microscopic States". A Modern Course in Statistical Physics. WILEY-VCH. p. 30. ISBN 978-3-527-69048-0.

[2] 마주르 2010, 페이지 10

[3] Ryser 1963, p. 7은 순서 없는 선택이라고도 언급됩니다.

[4] (2010년 브루알디처럼) 두 가지 상황 중 하나를 지칭하기 위해 조합이라는 용어를 사용할 경우, 집합 또는 다중 집합이 논의되고 있는지 여부를 명확히 하기 위해 주의를 기울여야 합니다.

[5] 우스펜스키 1937, 페이지 18

[6] High School Textbook for full-time student (Required) Mathematics Book II B (in Chinese) (2nd ed.). China: People's Education Press. June 2006. pp. 107–116. ISBN 978-7-107-19616-4.

[7] 人教版高中数学选修2-3 (Mathematics textbook, volume 2-3, for senior high school, People's Education Press). People's Education Press. p. 21.

[8] 마주르 2010, 페이지 21

[9] Lucia Moura. "Generating Elementary Combinatorial Objects" (PDF). Site.uottawa.ca. Archived (PDF) from the original on 9 October 2022. Retrieved 10 April 2017.

[10] "SAGE : Subsets" (PDF). Sagemath.org. Retrieved 10 April 2017.

[11] "Combinations - Rosetta Code". 23 October 2022.^{[사용자 생성 소스?]}

[12] 브루알디 2010, 페이지 52

[13] Benjamin & Quinn 2003, p. 70

[14] 기사에서 별과 막대(콤비네이터)는 $n$ 과 k의 역할이 반대입니다.

[15] Benjamin & Quinn 2003, 페이지 71–72

[16] Benjamin & Quinn 2003, p. 72 (아이덴티티 145)

[17] Benjamin & Quinn 2003, 페이지 71

[18] Mazur 2010, p. 10 여기서 별과 막대는 이진수로 표기되며, 별은 = 0이고 막대는 = 1입니다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[16]

[17]

Search

조합

네임스페이스

더

목차