Combination

수학(mathematics)에서, 조합(combination)은, (순열(permutation)과 다르게) 선택의 순서가 문제되지 않는 것을 만족하는, 모음으로부터 항목의 선택입니다. 예를 들어, 세 과일이 주어지면, 말하자면 사과, 오렌지, 배, 이 집합으로부터 추출되어질 수 있는 둘의 세 조합: 사과와 배; 사과와 오렌지; 또는 배와 오렌지가 있습니다. 보다 공식적으로, 집합(set) S의 k-조합은 S의 k 구별되는 원소의 부분-집합입니다. 만약 집합이 n 원소를 가지면, k-조합의 숫자는 이항 계수(binomial coefficient)와 같습니다:

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

이것은 $k\leq n$ 일 때마다 $\textstyle {\frac {n!}{k!(n-k)!}}$ 로 팩토리얼(factorial)을 사용하여 쓸 수 있고, 이것은 $k>n$ 일 때 영입니다. 집합 S의 모든 k-조합의 집합은 $\textstyle {\binom {S}{k}}$ 에 의해 종종 표시됩니다.

조합은 반복없이 한 번에 n 물건에서 k 개를 취하는 조합을 참조합니다. 반복이 허용되는 조합을 참조하기 위해, 용어 k-중복집합(multiset),^[1] k-중복집합^[2] 또는 반복을 갖는 k-조합이 종종 사용됩니다.^[3] 만약, 위의 예제에서, 과일의 임의의 하나의 종류에서 두 개를 가질 가능성이 있으면 2-선택의 3가지: 두 사과를 갖는 하나, 두 오렌지를 갖는 하나, 및 두 배를 갖는 하나를 추가적으로 가질 것입니다.

비록 세 과일의 집합이 조합의 전체 목록을 쓰기 위해 충분히 작을지라도, 큰 집합과 함께 이것은 비실용적이 됩니다. 예를 들어, 포커 손(poker hand)는 52 카드 덱 (n = 52)으로부터 카드의 5-조합 (k = 5)으로 묘사될 수 있습니다. 손의 5장의 카드는 모두 구별되고, 손에 있는 카드의 순서는 문제가 되지 않습니다. 2,598,960 그러한 조합이 있고, 무작위로 임의의 한 손을 추첨할 기회는 1 / 2,598,960입니다.

Number of k-combinations

n 원소의 주어진 집합 S로부터 k-조합의 숫자(number of k-combinations)는 기초 조합론 교과서에서 $C(n,k)$ 에 의해, 또는 $C_{k}^{n}$ , ${}_{n}C_{k}$ , ${}^{n}C_{k}$ , $C_{n,k}$ 또는 심지어 $C_{n}^{k}$ 와 같은 변형에 의해 종종 표시됩니다 (후자의 형식은 프랑스, 루마니아, 러시아, 중국,^[4] 및 폴란드 교과서^{[citation needed]}에서 표준이었습니다). 같은 숫자는 어쨌든 많은 다른 수학적 문맥에서 발생하며, 여기서 그것은 ${\tbinom {n}{k}}$ 에 의해 표시됩니다 (종종 "n 선택 k"로 읽습니다); 주목할 만하게 그것은 이항 공식(binomial formula)에서 계수, 따라서 그의 이름 이항 계수로 발생합니다. 우리는 다음 관계에 의해 한 번에 모든 자연수 k에 대해 ${\tbinom {n}{k}}$ 를 정의할 수 있습니다:

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

이것으로부터, 그것은 다음임이 명확합니다:

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

및 나아가서, k > n에 대해, 다음입니다:

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

.

이들 계수가 S로부터 k-조합을 세는 것을 보이기 위해, 우리는 먼저 S의 원소 s에 의해 레이블된 n 구별되는 변수 X_s의 모음을 고려할 수 있고, S의 모든 원소에 걸쳐 곱(product)을 확장할 수 있습니다:

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

그것은 S의 모든 부분-집합에 해당하는 2ⁿ개의 구별되는 항을 가지며, 각 부분집합은 해당 변수 X_s의 곱을 제공합니다. 이제 곱이 (1 + X)ⁿ이 되도록, X_s의 모두를 비-레이블된 변수 X와 같게 설정함으로써, S로부터 각 k-조합에 대해 항은 결과에서 해당 거듭제곱의 계수가 그러한 k-조합의 숫자와 같도록 X^k가 됩니다.

이항 계수는 다양한 방법에서 명시적으로 계산될 수 있습니다. (1 + X)ⁿ까지 전개에 대해 그들의 모두를 얻기 위해, 우리는 (이미 주어진 기본 경우 외에), 0 < k < n에 대해, 다음 재귀 관계를 사용할 수 있습니다:

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

이것은 (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X)로부터 따릅니다; 이것은 파스칼의 삼각형(Pascal's triangle)의 구성으로 이어집니다.

개별 이항 계수를 결정하는 것에 대해, 다음 공식을 사용하는 것이 보다 실용적입니다:

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

.

분자(numerator)는 n의 k-순열(k-permutations), 즉, S의 k 구별되는 원소의 수열의 숫자를 제공하며, 반면에 분모(denominator)는 순서가 무시될 때 같은 k-조합을 제공하는 그러한 k-순열의 숫자를 제공합니다.

k가 n/2을 초과할 때, 위의 공식은 분자 및 분모에 공통 인수를 포함하고, 그들을 약분함으로써, 0 ≤ k ≤ n에 대해, 다음 관계를 제공합니다:

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

.

이것은 이항 공식으로부터 명백하게 되는 대칭을 나타내고, 그러한 조합의 여(complement)를 취함으로써 k-조합의 관점에서 역시 이해될 수 있으며, 그것은 (n − k)-조합입니다.

마지막으로 이 대칭을 직접적으로 나타내는 수식이 있고, 기억하기 쉽다는 장점을 가집니다:

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

여기서 n!는 n의 팩토리얼(factorial)을 나타냅니다. 그것은 분모와 분자에 (n − k)!를 곱함으로써 이전 공식에서 얻어지므로, 그것은 해당 공식에 대한 계산의 방법으로 확실히 열등합니다.

마지막 공식은 S의 모든 원소의 n! 순열을 고려함으로써 직접 이해될 수 있습니다. 각각의 그러한 순열은 그의 첫 번째 k 원소를 선택함으로써 k-조합을 제공합니다. 많은 중복 선택이 있습니다: 서로 사이의 첫 번째 k 원소, 및 서로 사이의 마지막 (n − k) 원소의 임의의 결합된 순열은 같은 조합을 생성합니다; 이것은 그 공식에서 나눗셈을 설명합니다.

위의 공식으로부터 모두 세 방향에서 파스칼 삼각형의 인접 숫자 사이의 다음 관계를 따릅니다:

{\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}

.

기본 경우 ${\tbinom {n}{0}}=1={\tbinom {n}{n}}$ 와 함께, 이들은 같은 집합 (파스칼의 삼각형에서 행)으로부터 조합, 증가하는 크기의 집합의 k-조합, 및 고정된 크기 n − k의 여를 갖는 조합의 각각 모든 숫자의 연속적인 계산을 허용합니다.

Example of counting combinations

특정 예제로서, 우리는 표준 52 카드 데크로부터 가능한 5-카드 손의 숫자를 계산할 수 있습니다:^[5]

{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.

대안적으로, 우리는 팩토리얼의 관점에서 공식을 사용하고 분자에서 인수를 분모에서 인수의 대응하는 부분을 약분한 후에, 남아있는 인수의 오직 곱셈이 요구됩니다:

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

첫 번째 것과 동등한, 또 다른 대안적인 계산은, 다음으로 쓰이는 것을 기반으로 합니다:

{n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{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 \div 1 \times 51 \div 2 \times 50 \div 3 \times 49 \div 4 \times 48 \div 5$ 에서 평가할 때, 이것은 오직 정수 산술을 사용하여 계산될 수 있습니다. 그 이유는, 각 나눗셈이 발생할 때, 곱으로 생성되는 중간 결과는 자체로 이항 계수이므로, 나머지가 절대 발생하지 않는 것입니다.

단순화를 수행하는 것없이 팩토리얼의 관점에서 대칭 수식을 사용하면 상당히 광범위한 계산을 제공합니다:

{\begin{aligned}{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,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}

Enumerating k-combinations

우리는 어떤 고정된 순서에서 n 원소의 주어진 집합 S의 모든 k-조합을 열거(enumerate)할 수 있으며, 이것은 그들 k-조합의 집합을 갖는 ${\tbinom {n}{k}}$ 정수의 구간으로부터 전단사(bijection)를 확립합니다. S가 자체로 정렬된 것을 가정하면, 예를 들어 S = { 1, 2, …, n }, 그의 k-조합을 순서화하는 두 가지 자연스러운 가능성: (위 그림에서 처럼) 먼저 그들의 가장 작은 원소를 비교하는 것 또는 먼저 그들의 가장 큰 원소를 비교하는 것이 있습니다. 후자의 선택사항은 S에 대한 새로운 가장 큰 원소를 추가하는 것이 열거의 초기 부분을 변경하지 않지만, 단지 이전 것 뒤에 더 큰 집합의 새로운 k-조합을 추가한다는 장점을 가집니다. 이 과정을 반복하면, 열거는 언제나 더 큰 집합의 k-조합을 갖는 명확하지-않게 확장될 수 있습니다. 만약 게다가 정수의 구간이 0에서 시작하는 것으로 취해지면, 열거의 주어진 위치 i에서 k-조합을 i로부터 쉽게 계산될 수 있고, 이와 같이 얻어진 전단사는 조합론적 숫자 시스템(combinatorial number system)으로 알려져 있습니다. 그것은 계산론적 수학에서 "랭크"/"랭크화" 및 "비-랭크화"로 역시 알려져 있습니다.^[6]^[7]

k 조합을 열거하기 위한 여러 방법이 있습니다. 하나의 방법은 2ⁿ보다 작은 모든 이진수를 찾아가는 것입니다. 비록 이것이심지어 작은 n에 대해 매우 비효율적일지라도 (예를 들어, n = 20은 약 100만 개의 숫자를 찾아가는 것을 요구하지만, 허용된 k 조합의 최대 숫자는 k = 10에 대해 약 18만 6천입니다), k 비-영 비트를 가지는 그들 숫자를 선택합니다. 그러한 숫자에서 이들 1 비트의 위치는 집합 { 1, …, n }의 특정 k-조합입니다.^[8] 또 다른 간단하고, 더 빠른 방법은 선택된 원소의 k 인덱스 숫자를 추적하는 것입니다: 첫 번째 허용된 k-조합으로 {0 .. k−1} (영-기반) 또는 {1 .. k} (일-기반)과 함께 시작하며, 그런-다음 마지막 인덱스 숫자를 증가시킴으로써 다음 허용된 k-조합으로 반복적으로 이동시키며, 만약 그것이 n-1 (영-기반) 또는 n (일-기반) 또는 그것을 따르는 인덱스 숫자보다 작은 마지막 인덱스 숫자 x보다 작으면, 만약 그러한 숫자가 존재하면 1을 빼고, x 이후의 인덱스 숫자를 {x+1, x+2, …}로 재설정합니다.

Number of combinations with repetition

반복을 갖는 k-조합, 또는 k-중복조합, 또는 집합 S로부터 크기 k의 중복부분집합(multisubset)은 S의 구별되는 원소일 필요가 없는 k의 수열에 의해 제공되며, 여기서 순서는 고려되지 않습니다: 두 수열은 만약 우리가 항을 순열화함으로써 다른 것에서 얻어질 수 있으면 같은 중복집합을 정의합니다. 달리 말해서, 중복 (즉, 대체)을 허용하지만 다른 순서화 (예를 들어, {2,1,2} = {1,2,2})를 무시하는 n 원소의 집합으로부터 k 원소를 표본화하는 방법의 숫자입니다. S의 각 원소에 대한 인덱스를 연결하고 S의 원소를 대상의 유형(types)으로 생각하면, 우리는 $x_{i}$ 를 중복부분집합에서 유형 i의 원소 숫자를 나타내는 것으로 놓을 수 있습니다. 크기 k의 중복부분집합의 숫자는 그때에 디오판토스 방정식(Diophantine equation)의 비-음의 정수 해의 숫자입니다:^[9]

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

만약 S가 n 원소를 가지면, 그러한 k-중복부분집합의 숫자는 다음에 의해 표시됩니다:

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

이 표기법은 k-부분집합을 세는 이항 계수(binomial coefficient)의 아날로그인 것입니다. 이 표현, n 중복선택 k^[10]는 이항 계수의 관점에서 역시 제공될 수 있습니다:

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

이 관계는 별과 막대(stars and bars)로 알려진 표현을 사용하여 쉽게 입증될 수 있습니다.^[11]

Proof

위의 디오판토스 방정식의 해는 $x_{1}$ 별들, 구분-기호 (막대), 그런 다음 $x_{2}$ 또 다른 별들, 다른 구분-기호, 등에 의해 표현될 수 있습니다. 이 표현에서 별의 전체 숫자는 k이고 막대의 숫자는 n – 1입니다 (왜냐하면 구분-기호는 맨 끝에서 필요하지 않기 때문입니다). 따라서, k + n - 1 기호 (별과 막대)의 문자열은, 만약 문자열에서 k 별이 있으면, 해에 해당합니다. 임의의 해는 k + n - 1 위치에서 k를 선택하서 별을 배치하고 나머지 위치에 막대로 채움으로써 표현될 수 있습니다. 예를 들어, 방정식 $x_{1}+x_{2}+x_{3}+x_{4}=10$ 의 해 $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ 는 다음으로 표현될 수 있습니다:

\bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar

.^[12]

그러한 문자열의 숫자는 13 위치 중에 10 별을 배치하는 방법의 숫자, ${\binom {13}{10}}={\binom {13}{3}}=286$ 이며, 이것은 4 원소를 갖는 집합의 10-중복부분집합의 숫자입니다.

이항 계수와 마찬가지로, 이들 중복선택 표현 사이에 여러 관계가 있습니다. 예를 들어, $n\geq 1,k\geq 0$ 에 대해,

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

이 항등식은 위의 표현에서 별과 막대를 서로-바꾸는 것으로부터 따릅니다.^[13]

Example of counting multisubsets

예를 들어, 만약 여러분이 메뉴에서 네 가지 유형의 도넛 (n = 4)을 선택할 수 있고 여러분이 세 개의 도넛 (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-중복부분집합을 목록화함으로써 검증될 수 있습니다. 이것은 다음 테이블에서 표시됩니다.^[14] 두 번째 열은 방정식 $x_{1}+x_{2}+x_{3}+x_{4}=3$ 의 비-음의 정수 해 $[x_{1},x_{2},x_{3},x_{4}]$ 를 보여주고 마지막 열은 해의 별과 막대 표현을 제공합니다. ^[15]

번호	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$

Number of k-combinations for all k

모든 k에 대해 k-조합의 숫자는 n 원소의 집합의 부분집합의 숫자입니다. 이 숫자가 2ⁿ임을 보이기 위한 여러 방법이 있습니다. 조합의 관점에서, $\sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}$ 이며, 이것은 파스칼의 삼각형(Pascal's triangle)에서 이항 계수(binomial coefficients)의 (0부터 세어서) n-번째 행의 합입니다. 이들 조합 (부분-집합)은 0에서 2ⁿ − 1까지 세는 밑수 2(base 2) 숫자의 집합의 1 자릿수에 의해 열거되며, 여기서 각 자릿수 위치는 n의 집합으로부터 항목입니다.

1에서 3까지 번호가 매겨진 3 카드가 주어지면, 빈 집합(empty set)를 포함하여, 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

Probability: sampling a random combination

주어진 집합 또는 목록으로부터 임의의 조합을 골라내는 다양한 알고리듬(algorithms)이 있습니다. 배제 표본화(rejection sampling)은 큰 표본 크기에 대해 극단적으로 느립니다. 크기 n의 모집단에서 효율적으로 k-조합을 선택하는 하나의 방법은 모집단의 각 원소를 가로질러 반복하는 것이고, 각 단계에서 ${\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}$ 의 동적으로 변하는 확률을 갖는 해당 원소를 선택합니다. (저장소 표본화(reservoir sampling)을 참조하십시오).

Notes

^ Ryser 1963, p. 7 also referred to as an unordered selection.
^ Mazur 2010, p. 10
^ When the term combination is used to refer to either situation (as in (Brualdi 2010)) care must be taken to clarify whether sets or multisets are being discussed.
^ 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.
^ Mazur 2010, p. 21
^ Lucia Moura. "Generating Elementary Combinatorial Objects" (PDF). Site.uottawa.ca. Retrieved 2017-04-10.
^ "SAGE : Subsets" (PDF). Sagemath.org. Retrieved 2017-04-10.
^ "Combinations - Rosetta Code".^{[user-generated source?]}
^ Brualdi 2010, p. 52
^ Benjamin & Quinn 2003, p. 70
^ In the article Stars and bars (combinatorics) the roles of $n$ and $k$ are reversed.
^ Benjamin & Quinn 2003, pp. 71 –72
^ Benjamin & Quinn 2003, p. 72 (identity 145)
^ Benjamin & Quinn 2003, p. 71
^ Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.

References

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

External links

Topcoder tutorial on combinatorics
C code to generate all combinations of n elements chosen as k
Many Common types of permutation and combination math problems, with detailed solutions
The Unknown Formula For combinations when choices can be repeated and order does NOT matter
Combinations with repetitions (by: Akshatha AG and Smitha B)^{[permanent dead link]}
The dice roll with a given sum problem An application of the combinations with repetition to rolling multiple dice

[1] Ryser 1963, p. 7 also referred to as an unordered selection.

[2] Mazur 2010, p. 10

[3] When the term combination is used to refer to either situation (as in (Brualdi 2010)) care must be taken to clarify whether sets or multisets are being discussed.

[4] 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.

[5] Mazur 2010, p. 21

[6] Lucia Moura. "Generating Elementary Combinatorial Objects" (PDF). Site.uottawa.ca. Retrieved 2017-04-10.

[7] "SAGE : Subsets" (PDF). Sagemath.org. Retrieved 2017-04-10.

[8] "Combinations - Rosetta Code".^{[user-generated source?]}

[9] Brualdi 2010, p. 52

[10] Benjamin & Quinn 2003, p. 70

[11] In the article Stars and bars (combinatorics) the roles of $n$ and $k$ are reversed.

[12] Benjamin & Quinn 2003, pp. 71 –72

[13] Benjamin & Quinn 2003, p. 72 (identity 145)

[14] Benjamin & Quinn 2003, p. 71

[15] Mazur 2010, p. 10 where the stars and bars are written as binary numbers, with stars = 0 and bars = 1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]