Multiset

Original article: w:Multiset

This article is about the mathematical concept. For the computer science data structure, see Multiset (abstract data type).

수학(mathematics)에서, 중복집합(multiset, bag 또는 mset)은, 집합과 달리, 그의 원소(element) 각각에 대해 중복 경우를 허용하는 집합(set)의 개념의 수정입니다. 각 원소에 대해 주어진, 경우의 양의 정수는 중복집합에서 이 원소의 중복도(multiplicity)로 불립니다. 결과적으로, 중복집합의 무한 숫자가 존재하며, 이것은 오직 원소 a와 b를 포함하지만, 그들 원소의 중복도에 의해 변합니다:

• 집합 {a, b}는 오직 원소 a와 b를 포함하며, {a, b}가 중복집합으로 보일 때, 각각은 중복도 1을 가집니다.
• 중복집합 {a, a, b}에서, 원소 a는 중복도 2, 및 b는 중복도 1을 가집니다.
• 중복집합 {a, a, a, b, b, b}에서, a와 b 둘 다 중복도 3을 가집니다.

이들 대상은, 중복집합으로 보일 때, 모두 다르지만, 그들은 같은 집합(set)인데, 왜냐하면 그들 모두는 같은 원소로 구성되기 때문입니다. 집합에서 처럼, 및 튜플(tuple)과 달리, 순서는 중복집합을 구별하는 것에서 문제가 되지 않으므로, {a, a, b}와 {a, b, a}는 같은 중복집합을 나타냅니다. 집합과 중복집합 사이에 구별을 위해, 대괄호를 사용하는 표기법이 때때로 사용됩니다: 중복집합 {a, a, b}는 [a, a, b]로 표시될 수 있습니다.

중복집합의 카디널리티(cardinality)는 모든 그의 원소의 중복도를 합함으로써 구성됩니다. 예를 들어, 중복집합 {a, a, b, b, b, c}에서, 구성원 a, b, 및 c의 중복도는 각각 2, 3, 및 1이고, 따라서 이 중복집합의 카디널리티는 6입니다.

도널드 커누스(Donald Knuth)에 따르면, 니콜라스 호버트 더 블라인(Nicolaas Govert de Bruijn)은 1970년대에 단어 중복집합을 만들었습니다. 어쨌든, 중복집합에 대해 개념의 사용은 단어 중복집합의 생성보다 수세기만큼 선행됩니다. 커누스 자신은 중복집합의 첫 번째 연구를, 1150년경에 중복집합의 순열에 대해 기술한 인도의 수학자 바스카라 2세(Bhāskara II)에게 돌렸습니다. 커누스는 list, bunch, bag, heap, sample, weighted set, collection, 및 suite을 포함하는, 이 개념에 대해 제안 또는 사용된 다른 이름을 역시 나열합니다.

History

웨인 블리자드(Wayne Blizard)는 중복집합을 숫자의 근원으로 추적하면서, “고대에서, 숫자 n이 n 타격, 탈리 표식, 또는 단위의 집합으로 종종 나타내었다“라고 주장합니다. 이들 및 대상의 유사한 모임은 중복집합인데, 왜냐하면 타격, 탈리 표식 또는 단위는 구별할 수 없는 것으로 여겼습니다. 이것은 사람들이 심지어 수학이 등장하기 훨씬 전에 중복집합을 암묵적으로 사용했다는 것을 보여줍니다.

이 구조에 대해 실질적인 요구는 중복집합을 여러 시대 재발견되는 원인이 되었으며, 다른 이름으로 문헌에서 나타납니다. 예를 들어, 그것들은, QA4와 같은, 초기 AI 언어에서 중요했으며, 여기서 그것들은, 피터 도이치(Peter Deutsch)에 기인한 용어, bags로 참조되었습니다. 중복집합은 aggregate, heap, bunch, sample, weighted set, occurrence set, 및 fireset (유한하게 반복되는 원소 집합)으로 역시 불려 왔습니다.

비록 중복집합이 고대 시대부터 암묵적으로 사용되었을지라도, 그들의 명시적 탐구는 월씬 나중에 발생했습니다. 중복집합의 최초의 알려진 연구는 1150년경 인도의 수학자 바스카라 2세(Bhāskara II)에 기인되며, 그는 중복집합의 순열을 묘사했습니다. 마리우스 니졸리우스(Marius Nizolius) (1498–1576)의 연구는 중복집합의 개념에 대한 또 다른 초기 참조를 포함합니다. 아타나시우스 키르허(Athanasius Kircher)는 하나의 원소가 반복될 수 있을 때 중복집합 순열의 숫자를 발견했습니다. 장 프리스테(Jean Prestet)는 1675년에 중복집합 순열에 대해 일반적인 규칙을 발표했습니다. 존 월리스(John Wallis)는 1685년에 이 규칙을 보다 자세히 설명했습니다.

중복집합은 리하르트 데데킨트(Richard Dedekind)의 연구에서 명시적으로 나타났습니다.

다른 수학자들은 중복집합을 공식화하고 20세기에서 정확한 수학 구조로 그들을 연구하기 시작했습니다. 예를 들어 휘트니(Whitney) (1933)는 일반화된 집합(generalized sets) (그의 특성 함수(characteristic function)가 임의의 정수 값 - 양수, 음수 또는 영을 가질 수 있는 "집합")을 설명했습니다. 몬노(Monro) (1987)는 중복집합과 그들의 모피즘의 카테고리(category) Mul을 조사했으며, "같은 종류의" 원소들 사이의 동등 관계를 갖는 집합으로 중복집합, 종류에 관계하는 함수로 중복집합 사이의 모피즘을 정의합니다. 그는 중복숫자: 중복집합에서 자연수로의 함수 f(x), 중복집합에서 원소 x의 중복도를 제공하는 함수를 도입했습니다. 몬노(Monro)는 중복집합과 중복숫자의 개념은, 비록 둘 다가 유용할지라도, 무차별적으로 종종 혼합된다고 주장했습니다.

Examples

가장 간단하고 자연스러운 예제 중 하나는 숫자 n의 소수(prime) 인수의 중복집합입니다. 여기서 원소의 놓여-있는 집합은 n의 소수 약수(divisor)의 집합입니다. 예를 들어, 숫자 120은 다음 소수 인수분해(prime factorization)를 가집니다:

$120=2^{3}3^{1}5^{1}$

이것은 중복집합 {2, 2, 2, 3, 5}을 제공합니다.

관련된 예제는 대수적 방정식의 해의 중복집합입니다. 이차 방정식(quadratic equation)은, 예를 들어, 두 해를 가집니다. 어쨌든, 일부 경우에서 그들은 둘 다 같은 숫자입니다. 따라서 방정식의 해의 중복집합은 {3, 5}가 될 수 있으며, 또는 그것은 {4, 4}가 될 수 있습니다. 후자의 경우에서 그것은 중복도 2의 해를 가집니다. 보다 일반적으로, 대수학의 기본 정리(fundamental theorem of algebra)는 차수 d의 다항 방정식(polynomial equation)의 복소수(complex) 해는 카디널리티 d의 중복집합을 항상 형성한다고 주장합니다.

위의 특별한 경우는 행렬의 고윳값(eigenvalue)이며, 이들의 중복도는 특성 다항식(characteristic polynomial)의 근으로 그들의 중복집합으로 정의되는 정의됩니다. 어쨌든 두 다른 중복도가 고윳값에 대해 자연스럽게 정의되며, 하나는 최소 다항식(minimal polynomial)의 근으로 중복도, 및 다른 하나는 A – λI의 커널의 차원(dimension)으로 정의되는 기하학적 중복도(geometric multiplicity)입니다 (여기서 λ는 행렬 A의 고윳값입니다). 이들 세 중복도는 고윳값의 세 중복집합을 정의하며, 이것은 모두 다를 수 있을 것입니다: A는 단일 고윳값을 가지는 조르당 정규 형식(Jordan normal form)의 근으로 n×n 행렬로 놓습니다. 그것의 중복도는 n이고, 최소 다항식의 근으로 중복도는 가장-큰 조르당 블록의 크기이고, 그의 기하학적 중복도는 조르당 블록의 숫자입니다.

Definition

중복집합은 2-튜플(tuple) (A, m)으로 공식적으로 정의될 수 있으며, 여기서 A는 그의 구별되는 원소로부터 형성된 중복집합의 놓여-있는 집합(underlying set)이고, $m\colon A\to \mathbb {N} _{\geq 1}$은 A로부터 중복도를 제공하는 양의(positive) 정수(integer), 즉, 숫자 m(a)로 중복집합에서 원소 a의 발생의 숫자의 집합으로의 함수(function)입니다.

함수 m을 그의 그래프(graph)로 표현하면, 그것은 ({a, b}, {(a, 2), (b, 1)})으로 중복집합 {a, a, b}, 및 ({a, b}, {(a, 1), (b, 1)})으로 중복집합 {a, b}을 쓰는 것을 허용하는 순서쌍(ordered pair) $\left\{\left(a,m\left(a\right)\right):a\in A\right\}$의 집합입니다. 이 표기법은 어쨌든 공통적으로 사용되지 않고 보다 간결한 표기법이 사용됩니다.

만약 $A=\{a_{1},\ldots ,a_{n}\}$가 유한 집합(finite set)이면, 중복집합 (A, m)은 종종 다음으로 표현됩니다:

$\left\{a_{1}^{m(a_{1})},\ldots ,a_{n}^{m(a_{n})}\right\},\quad$ 때때로 $\quad a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})}\;$으로 단순화됩니다.

여기서 1과 같은 위쪽 인덱스는 생략됩니다. 예를 들어, 중복집합 {a, a, b}는 $\{a^{2},b\}$ 또는 $a^{2}b$로 쓸 수 있을 것입니다. 만약 중복집합의 원소가 숫자이면, 보통의 산술 연산(arithmetic operations)과 혼동이 발생길 수 있으며, 그것들은 통상적으로 문맥으로부터 제외될 수 있습니다. 다른 한편으로, 후자의 표기법은 양의 정수의 소수 인수분해(prime factorization)는, 산술의 기본 정리(fundamental theorem of arithmetic)에 의해 주장된 것처럼, 고유하게 정의된 중복집합이라는 사실과 일치합니다. 역시, 단항식(monomial)은 불확정(indeterminate)의 중복집합입니다.

중복집합이, 만약 모든 각 원소의 중복도가 (일부 더 큰 자연수가 있는 것과 반대로) 일이면, 보통의 집합에 해당합니다. 인덱스된 가족(indexed family), (a_i)_i∈I는, 여기서 i는 일부 인덱스-집합 I에 걸쳐 변하며, 중복집합을 정의할 수 있으며, 때때로 {a_i}로 쓰입니다. 이 관점에서 중복집합의 놓여-있는 집합은 가족의 이미지(image)에 의해 제공되고, 임의의 원소 x의 중복도는 $a_{i}=x$를 만족하는 인덱스 값 i의 숫자입니다. 이 기사에서 중복도는 유한으로 여겨지며, 즉, 어떤 원소도 가족 안에서 무한하게 여러 번 발생하지 않습니다: 심지어 무한 중복집합에서도, 중복도는 유한 숫자입니다.

개별 원소의 중복도를 자연수가 아닌 무한 기수인 것을 허용함으로써 중복집합의 정의를 확장할 수는 있지만, 모든 속성이 이 일반화로 이어지지는 않습니다.

Basic properties and operations

중복집합의 원소는, 때때로 전체-집합(universe)라고 불리는, 고정된 집합 U에서 일반적으로 취해지며, 이것은 전형적으로 자연수(natural number)의 집합입니다. 주어진 중복집합에 속하지 않는 U의 원소는 이 중복집합에서 중복도 0을 가진다고 말합니다. 이것은 중복집합의 중복도 함수를 U에서 비-음의 정수(nonnegative integer)의 집합 $\mathbb {N}$으로의 함수로 확장합니다. 이것은 이들 함수와 U에서 그들 원소를 가지는 중복집합 사이의 일-대-일 대응을 정의합니다.

이 확장된 중복도 함수는 공통적으로 간단히 중복도 함수(multiplicity function)로 불리고, 원소를 포함하는 전체-집합이 고정되어 있을 때, 중복집합을 정의하기에 충분합니다. 이 중복도 함수는 부분-집합의 지시 함수(indicator function)의 일반화이고, 그것을 갖는 일부 속성을 공유합니다.

전체-집합 U에서 중복집합 $A$의 지원(support)은 중복집합의 놓여-있는 집합입니다. 중복도 함수 $m$을 사용하여, 그것은 다음으로 특성화됩니다:

$\operatorname {Supp} (A):=\left\{x\in U\mid m_{A}(x)>0\right\}$.

중복집합은, 만약 그것의 지원이 유한하면, 또는, 동등하게, 만약 그것의 카디널리티

$|A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)$

가 유한이면, 유한입니다. 빈 중복집합(empty multiset)은 빈 지원 (놓여-있는 집합)을 갖는 고유한 중복집합이고, 따라서 카디널리티 0입니다.

집합의 보통 연산은 중복도 함수를 사용함으로써, 부분집합에 대해 지시 함수를 사용할 때와 같은 비슷한 방법에서, 중복집합으로 확장될 수 있습니다. 다음에서, A와 B는 중복도 함수 $m_{A}$와 $m_{B}$를 갖는 주어진 전체-집합 U에서 중복집합입니다.

• 포함: A가, 만약 다음이면, A ⊆ B로 표시되는, B에 포함됩니다:

$\forall x\in U,m_{A}(x)\leq m_{B}(x).$

• 교집합: A와 B의 (일부 문맥에서, 하한(infimum) 또는 최대공약수(greatest common divisor)로 불리는) 교집합은 다음 중복도 함수를 갖는 중복집합 C입니다:

$m_{C}(x)=\min(m_{A}(x),m_{B}(x))\quad \forall x\in U.$

• 합집합: A와 B의 (일부 문맥에서, 상한(infimum) 또는 최소공배수(greatest common multiple)로 불리는) 합집합은 다음 중복도 함수를 갖는 중복집합 C입니다:

$m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \forall x\in U.$

• 합: 중복집합의 합은 집합의 서로소 합집합(disjoint union)의 일반화로 보일 수 있고, 다음에 의해 정의됩니다:

$m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \forall x\in U.$

합은 주어진 전체-집합에서 유한 중복집합 위에 교환적 모노이드(commutative monoid) 구조를 정의합니다. 이 모노이드는 기저로 전체-집합을 갖는 자유 교환적 모노이드(free commutative monoid)입니다.

두 중복집합이, 만약 그들의 지원이 서로소 집합(disjoint sets)이면, 서로소입니다. 이것은 그들의 교집합이 빈 중복집합 또는 그들의 합이 그들의 합집합과 같다고 말하는 것과 동등합니다.

(집합에 대해 그것과 유사한) 유한 중복집합에 대해 포함–제외 원칙이 있으며, 유한 중복집합의 유한 합집합은 중복집합의 두 합의 차이임을 말합니다: 첫 번째 합에서 우리는 주어진 중복집합의 홀수의 모든 가능한 교집합을 고려하며, 반면에 두 번째 합계에서 우리는 주어진 중복집합의 짝수의 모든 가능한 교집합을 고려합니다.

Counting multisets

Bijection between 3-subsets of a 7-set (left)
and 3-multisets with elements from a 5-set (right)
So this illustrates that $\textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right)$.

See also: Stars and bars (combinatorics)

카디널리티 n의 유한 집합으로부터 취해진 원소를 갖는, 카디널리티 k의 중복집합의 숫자는 중복집합 계수(multiset coefficient) 또는 중복집합 숫자(multiset number)로 불립니다. 이 숫자는 일부 저자에 의해 이항 계수(binomial coefficient)의 표기법과 유사한 그것, $\textstyle \left(\!\!{n \choose k}\!\!\right)$으로 쓰입니다; 그것은 예를 들어 (Stanley, 1997)에서 사용되고, ${\tbinom {n}{k}}$에 대해 "n 선택 k"와 유사하게 "n 중복선택 k"로 발음될 수 있습니다. 이항 계수와 달리, 중복집합 계수가 발생하는 것에서 "중복집합 정리"는 존재하지 않고, 그들은 다항 정리(multinomial theorem)에서 발생하는 비-관련된 다항 계수(multinomial coefficient)와 혼동되어서는 안됩니다.

중복집합 계수의 값은 다음으로 명시적으로 제공될 수 있습니다:

$\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},$

여기서 두 번째 표현은 이항 계수입니다; 많은 저자는 사실 별도의 표기법을 피하고 그냥 이항 계수를 씁니다. 그래서, 그러한 중복집합의 숫자는 카디널리티 n + k − 1의 집합에서 카디널리티 k의 부분집합의 숫자와 같습니다. 이항 계수와 함께 아날로그는, 떨어지는 팩토리얼 거듭제곱

${n \choose k}={n^{\underline {k}} \over k!}$

을 사용하여 표현하는 이항 계수와 일치시키기 위해, 위의 표현에서 분자를 올라가는 팩토리얼 거듭제곱(rising factorial power)

$\left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!}$

으로 쓰는 것으로 강조될 수 있습니다.

예를 들어, 카디널리티 2의 집합 {1, 2}로부터 취해지는 원소를 갖는 카디널리티 3 (n = 2, k = 3)의 4 중복집합, 즉 {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, {2, 2, 2}가 있습니다. 카디널리티 4 (n + k − 1)의 집합 {1, 2, 3, 4}에서 카디널리티 3의 4 부분집합, 즉 {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}이 역시 있습니다.

위에서 주어진 중복집합 계수와 이항 계수의 상등을 증명하기 위한 하나의 간단한 방법은, 다음 방법에서 중복집합을 표현하는 것을 포함합니다. 먼저 이 형식에서 {a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d} (a 6개, b 2개, c 3개, d 7개)를 나타내는 중복집합에 대해 다음 표기법을 생각해 보십시오:

 •  •  •  •  •  •  |  •  •  |  •  •  •  |  •  •  •  •  •  •  •

이것은 카디널리티 n = 4의 집합의 원소로 만들어지는 카디널리티 k = 18의 중복집합입니다. 이 표기법에서 사용된 점과 수직 막대 둘 다를 포함하는 문자의 숫자는 18 + 4 − 1입니다. 수직 막대의 숫자는 4 − 1입니다. 카디널리티 18의 중복집합의 숫자는, 그런-다음, 18 + 4 − 1 문자 사이에 4 − 1 수직 막대를 정렬하기 위한 방법의 숫자이고, 따라서 카디널리티 18 + 4 − 1의 집합에서 카디널리티 4 − 1의 부분집합의 숫자입니다. 동등하게, 그것은 18 + 4 − 1 문자 사이의 18점을 정렬하기 위한 방법의 숫자이고, 이것은 카디널리티 18 + 4 − 1의 집합에서 카디널리티 18의 부분집합의 숫자입니다. 이것은 다음과 같습니다:

${4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,$

따라서 중복집합 계수와 그 동등성의 값입니다:

$\left(\!\!{4 \choose 18}\!\!\right)={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3}=\left(\!\!{19 \choose 3}\!\!\right),$

$={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},$

$={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\,\times \,\mathbf {1\cdot 2\cdot 3\quad } }},$

$={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.$

우리는 일반화된 이항 계수를 다음으로 정의할 수 있습니다:

${n \choose k}={n(n-1)(n-2)\cdots (n-k+1) \over k!}$

이것에서 n은 비-음의 정수가 되는 것을 요구하지 않지만, 음 또는 비-정수, 또는 비-실수 복소수(complex number)일 수 있습니다. (만약 k = 0이면, 이 계수의 값은 1인데 왜냐하면 그것은 빈 곱(empty product)이기 때문입니다.) 그런-다음 카디널리티 n의 집합에서 카디널리티 k의 중복집합의 숫자는 다음입니다:

$\left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.$

Recurrence relation

중복집합 계수에 대해 재귀 관계(recurrence relation)는 다음으로 주어질 수 있습니다:

$\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{for }}n,k>0$

단,

$\left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{and}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.$

위의 재귀는 다음으로 해석될 수 있습니다. [n] := $\{1,\cdots ,n\}$을 소스 집합으로 놓습니다. 항상 크기 0의 정확히 하나의 (빈) 중복집합이 있고, 만약 n = 0이면 더 큰 중복집합이 없으며, 이것은 초기 조건을 제공합니다.

이제, n,k > 0인 것에서 경우를 생각해 보십시오. [n]으로부터 원소를 갖는 카디널리티 k의 중복집합은 마지막 원소 n의 임의의 경우를 포함 또는 포함하지 않을 수 있습니다. 만약 그것이 나타나면, 한 번 n을 제거함으로써, 하나는 [n]으로부터 원소의 카디널리티 k − 1의 중복집합으로 남겨지고, 모든 각 그러한 중복집합이 발생할 수 있으며, 이것은 다음의 전체를 제공합니다:

$\left(\!\!{n \choose k-1}\!\!\right)$ 가능성.

만약 n이 나타나지 않으면, 원래의 중복집합은 [n − 1]으로부터 원소를 갖는 카디널리티 k의 중복집합과 같으며, 다음과 같습니다:

$\left(\!\!{n-1 \choose k}\!\!\right).$

따라서,

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

Generating series

중복집합 계수의 생성하는 함수(generating function)는 매우 간단하며, 다음입니다:

$\sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{(1-t)^{n}}}.$

중복집합이 모노이드와 일-대-일 대응이므로, $\left(\!\!{n \choose d}\!\!\right)$는 역시 n 불확정수에서 차수 d의 모노이드의 숫자입니다. 따라서, 위의 급수는 역시 다항식 링(polynomial ring) $k[x_{1},\ldots ,x_{n}]$의 힐베르트 급수(Hilbert series)입니다.

$\left(\!\!{n \choose d}\!\!\right)$는 n에서 다항식이므로, 그것은 n의 임의의 복소(complex) 값에 대해 정의됩니다.

Generalization and connection to the negative binomial series

곱셈적 공식은 n을 임의의 숫자 α (음수, 실수, 복소수)로 대체함으로써 중복집합 계수의 정의를 확장하는 것을 허용합니다:

$\left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .$

이 정의와 함께, 우리는 (변수 중 하나를 1로 설정하는 것과 함께) 음의 이항 공식의 일반화를 가지며, 이것은 $\left(\!\!{\alpha \choose k}\!\!\right)$ 음의 이항 계수로 부르는 것을 정당화합니다:

$(1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X^{k}.$

이 테일러 급수(Taylor series) 공식은 모든 복소수 α와 |X| < 1을 갖는 X에 대해 유효합니다. 그것은 X에서 형식적 거듭제곱 급수(formal power series)의 항등식으로 역시 해석될 수 있으며, 여기서 그것은 실제로 1과 같은 상수 계수를 갖는 급수의 임의의 거듭제곱의 정의로 사용될 수 있습니다; 요점은 이 정의와 함께 모든 항등식은 우리가 지수(exponentiation)에 대해 기대하는 것을 유지하는 것입니다, 특히

$(1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{and}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )}$,

및 이들과 같은 공식은 중복집합 계수에 대해 항등식을 입증하기 위해 사용될 수 있습니다.

만약 α가 비-음의 정수 n이면, k > −n을 갖는 모든 항은 영이고, 무한 급수는 유한 합이 됩니다. 어쨌든, 양의 정수와 유리수를 포함하는, α의 다른 값에 대해, 급수는 무한입니다.

Applications

중복집합은 다양한 응용을 가집니다. 그들은 조합론(combinatorics)에서 기초가 되고 있습니다. 중복집합은 데이터베이스 이론에서 중요한 도구가 되어 왔으며, 이것은 종종 동의어 bag을 사용합니다. 예를 들어, 중복집합은 종종 데이터베이스 시스템에서 관계를 구현하기 위해 사용됩니다. 중복집합은 또한 컴퓨터 과학에서 중요한 역할을 합니다.

역시 다른 응용도 있습니다. 예를 들어, 리하르트 라도(Richard Rado)는 중복집합을 집합의 가족의 속성을 조사하기 위한 장치로 사용했습니다. 그가 썼습니다: "집합의 개념은 그의 구성원 중 하나가 여러 번 나타나는 것을 고려하지 않고, 게다가 자주 중요한 것으로 여기는 것은 바로 이런 종류의 정보입니다. 우리는 다항식 f(x)의 근의 집합 또는 선형 연산자의 스펙트럼을 단지 생각해도 됩니다."

Generalizations

중복집합의 다른 일반화가 도입, 연구되어 왔고 문제에 푸는 것에 적용되어 왔습니다.

• 실수-값 중복집합 (이것에서 원소의 중복도는 임의의 실수가 될 수 있습니다)

퍼지 집합 및 중복집합에 대해 많은 정의가 매우 유사하고 특성 함수의 값 범위 (각각, [0, 1] 또는 ℕ₀ = {0, 1, 2, 3, ...})를 ℝ₀⁺ = [0, ∞[로 단지 대체함으로써 실수 값 중복집합에 대해 취할 수 있으므로, 이것은 간단해 보입니다. 어쨌든, 이 접근은 멤버쉽의 간단한 정도 대신에 부분적으로 순서화 집합(poset) 또는 격자(lattice)를 사용하는 일반화된 퍼지 집합에 대해 절대 쉽게 확장될 수 없습니다. 퍼지 중복집합에 대해 여러 다른 접근이 이 제한을 가지지 않는 것에 대해 개발되어 왔습니다.

• 퍼지 중복집합
• 거친 중복집합
• 하이브리드 집합
• 그의 중복도가 임의의 실수-값 계단 함수인 중복집합
• 부드러운 중복집합
• 부드러운 퍼지 중복집합
• 이름-지은 집합 (집합의 모든 일반화의 통일)

See also

• Frequency (statistics) as multiplicity analog
• Quasi-sets
• Set theory
• Partitions of multisets