중복집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

중복집합은 각 원소가 여러 번 나타날 수 있는 집합과 유사한 구조이다. 중복집합은 집합과 중복도 함수로 구성된 순서쌍으로 정의되며, 중복도 함수는 각 원소가 중복집합에 몇 번 나타나는지를 나타내는 기수 값 함수이다. 중복집합의 크기는 모든 원소의 중복도의 합으로 정의된다. 중복집합은 소인수 분해, 다항식의 근, 행렬의 고유값 등 다양한 수학적 개념을 표현하는 데 사용된다. 중복 집합은 조합론, 데이터베이스, 컴퓨터 과학 등 다양한 분야에 응용되며, 특히 데이터베이스 시스템에서 중복 데이터를 처리하고 쿼리 결과를 정확하게 반환하는 데 중요한 역할을 한다. 또한, 실수 값을 갖는 중복집합, 퍼지 중복집합, 러프 중복집합 등 다양한 형태로 일반화되어 연구되고 있다.

더 읽어볼만한 페이지

계승과 이항식 주제 - 이항 정리
이항 정리는 이변수 다항식 (x + y)ⁿ을 전개하는 공식으로, 이항 계수를 사용하며, 조합론적 증명과 수학적 귀납법을 통해 증명할 수 있고, 다양한 분야에 응용되며, 이항 급수, 다항 정리 등 일반화된 형태가 존재한다.
계승과 이항식 주제 - 감마 분포
감마 분포는 형상 모수와 척도 모수로 정의되는 연속 확률 분포로, 확률 밀도 함수가 감마 함수로 표현되며, 베이즈 통계학에서 켤레 사전 분포로 활용되고, 형상 모수가 양의 정수일 때는 얼랑 분포를 나타낸다.
집합론의 기본 개념 - 치역
치역은 함수에서 정의역의 모든 원소에 대한 함숫값들의 집합으로, 공역의 부분집합이며, 함수의 상을 의미하거나 공역 전체를 의미하기도 한다.
집합론의 기본 개념 - 항등 함수
항등 함수는 집합 X의 각 원소를 자기 자신에게 대응시키는 함수로서, 정의역과 공역이 같은 집합 X에서 단사 함수이자 전사 함수이며, 함수 합성에서 항등원의 역할을 수행하는 중요한 개념이다.

중복집합
개요
정의	집합의 일반화로, 원소의 중복을 허용하는 자료 구조
영어	multiset
다른 이름	bag unordered tuple (비순서 튜플)
설명	원소의 중복 횟수를 나타내는 multiplicity (다중도, 중복도)를 가짐. 순서가 없는 모임. 집합과는 달리 원소의 중복을 허용.
수학적 표현
표기법	(중복된 원소를 포함하여 표기)
예시	(a가 3번, b가 3번 중복된 다중집합)
특징
집합과의 차이점	원소의 중복 허용 여부 (집합은 중복 불허)
순서	원소의 순서는 중요하지 않음
크기	중복된 원소를 포함한 원소의 총 개수
응용
컴퓨터 과학	데이터베이스, 알고리즘 분석 등에 활용
조합론	중복조합 계산 등에 활용

2. 정의

중복집합은 각 원소가 여러 번 나타날 수 있는 집합과 유사한 구조이다. 예를 들어, {a, a, b}는 a가 두 번, b가 한 번 나타나는 중복집합이다.

하위 섹션에서 자세한 정의와 표기법, 크기 등을 다룬다.

2. 1. 기본 정의

중복집합은 다음의 데이터로 구성되는 순서쌍

(M,\mu_M)

이다.

집합 $M$ . 그 원소를 중복집합의 '''원소'''라고 한다.
기수 값 함수 $\mu_M\colon M\to\operatorname{Card}\setminus\{0\}$ . 각 $m\in M$ 에 대하여, $\mu_M(m)$ 을 $m$ 의 '''중복도'''라고 한다. ( $M$ 에 속하지 않는 원소의 중복도는 0이라고 정의한다.)

'''중복 집합'''은

(A, m)

의 형태로 정의될 수 있으며, 여기서

A

는 중복 집합의 "기저 집합"으로, 고유한 원소들로 구성되며,

m\colon A \to \mathbb{Z}^{+}

는

A

에서 양의 정수 집합으로 가는 함수이며, 중복 집합에서 원소

a

의 "중복도" (즉, 발생 횟수)를 수

m(a)

로 나타낸다.^[16]

함수

m

을 그 그래프 (순서쌍의 집합

\{(a, m(a)) : a \in A\}

)로 나타내면, 중복 집합

\{\!\!\{a, a, b\}\!\!\}

를

\{(a, 2), (b, 1)\}

, 중복 집합

\{\!\!\{a, b\}\!\!\}

를

\{(a, 1), (b, 1)\}

로 작성할 수 있다.

만약

A=\{a_1, \ldots, a_n\}

가 유한 집합이라면, 중복 집합

(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^2b.

로 쓸 수 있다.

모든 원소의 중복도가 1이면 중복 집합은 일반적인 집합에 해당한다. 색인화된 패밀리

(a_i)_{i\in I}

, 여기서

i

는 어떤 색인 집합 ''I''에서 변동하며, 중복 집합을 정의할 수 있으며, 때로는

\{\!\!\{a_i\}\!\!\}

로 작성된다.

집합과 중복 집합의 구분을 위해 집합처럼 중괄호

\{,\}

로 묶는 대신, 이중 중괄호

\{\!\!\{,\}\!\!\}

또는 대괄호 ^[40] 또는 중괄호 내부 삭제

\{\!\vert,\vert\!\}

.^[41] 등으로 묶기도 한다.

집합과 중복 집합과 순서쌍 (또는 튜플)은 예를 들어 다음과 같은 점에서 차이가 있다.

a \ne b

로서,

순서쌍: $(a, a, b)$ 와 $(a, b, a)$ 는 순서 삼중쌍으로 다르다. 이것들은 물론 $(a, b)$ 와도 다르다.
중복 집합: $\{\!\!\{a, a, b\}\!\!\}$ 와 $\{\!\!\{a, b, a\}\!\!\}$ 는 중복 집합으로 일치한다. 하지만, $\{\!\!\{a, a, b\}\!\!\}$ 와 $\{\!\!\{a, b\}\!\!\}$ 는 중복 집합으로 다르다.
집합: $\{a, a, b\}$ 와 $\{a, b, a\}$ 와 $\{a, b\}$ 는 모두 같은 집합이다.

2. 2. 표기법

중복집합은 중괄호 안에 원소를 나열하고, 각 원소의 중복도를 위첨자로 표시하여 표현할 수 있다. 예를 들어, `{a, a, b}`는 `{a^2, b}` 또는 `a^2b`와 같이 나타낼 수 있다.^[16] 여기서 `a`는 2번, `b`는 1번 나타난다. 숫자로 된 원소의 경우, 일반적인 산술 연산과 혼동될 수 있으므로 문맥에 따라 주의해야 한다.

단항식은 미지수의 중복집합으로 볼 수 있다. 예를 들어, 단항식 `x`³`y`²는 중복집합 `{x, x, x, y, y}`에 해당한다.

모든 원소의 중복도가 1이면, 중복집합은 일반적인 집합이 된다.

2. 3. 크기

중복집합 ''M''의 '''크기'''는 모든 원소의 중복도의 합이다.^[40]

:

|M|=\sum_{m\in M}\mu_M(m)

여기서 우변은 기수의 덧셈이다.

3. 역사

웨인 블리자드는 "고대에는 숫자 ''n''이 종종 ''n''개의 획, 눈금 또는 단위의 모음으로 표현되었다"고 주장하며,^[4] 중복집합의 기원이 숫자의 기원까지 거슬러 올라간다고 설명한다. 획, 눈금 또는 단위는 구별할 수 없다고 여겨지기 때문에 이러한 객체들의 모음은 중복집합으로 간주될 수 있다. 이는 수학이 등장하기도 전에 사람들이 암묵적으로 중복집합을 사용했음을 보여준다.

이러한 구조에 대한 실용적인 필요성으로 인해 중복집합은 여러 번 재발견되었으며, 문헌에서는 다른 이름으로 나타났다.^[5] 초기 인공 지능 언어인 QA4에서는 "가방"이라고 불렸으며, 이 용어는 피터 도이치에게서 유래되었다고 한다.^[6] 중복집합은 집합체, 힙, 묶음, 표본, 가중 집합, 발생 집합, 화재 집합(유한 반복 요소 집합)이라고도 불린다.^[5]^[7]

3. 1. 초기 연구

1150년경 인도의 수학자 바스카라 2세는 중복집합의 순열을 연구한 것으로 알려져 있다.^[36]

3. 2. 명시적 연구

마리우스 니졸리우스(1498–1576)는 중복집합 개념을 연구한 초기 학자 중 한 명이다.^[8] 아타나시우스 키르허는 한 요소가 반복될 수 있을 때 중복집합 순열의 수를 연구했다.^[9] 1675년 장 프레스테는 중복집합 순열에 대한 일반적인 규칙을 발표했고,^[10] 1685년 존 윌리스는 이 규칙을 더 자세히 설명했다.^[11]

리하르트 데데킨트의 연구에서 중복집합이 명시적으로 나타났다.^[12]^[13]

20세기에 들어 해슬러 휘트니 등 여러 수학자들이 중복집합을 형식화하고 정밀한 수학적 구조로 연구하기 시작했다. 휘트니는 "일반화된 집합" (특성 함수가 임의의 정수 값을 가질 수 있는 "집합")을 설명했다.^[5]^[14]

4. 연산

중복집합의 연산은 일반 집합의 연산을 확장하여 정의할 수 있다. 중복집합에서는 각 원소가 여러 번 나타날 수 있으므로, 연산 시 각 원소의 중복도를 고려해야 한다.

포함 관계: 중복집합 `A`가 중복집합 `B`에 포함된다는 것은 모든 `x`에 대해 `A`에서의 `x`의 중복도가 `B`에서의 `x`의 중복도보다 작거나 같음을 의미한다. 이를 `A ⊆ B`로 표시하며, 다음이 성립한다.

:

m_A(x) \le  m_B(x)\quad\forall x\in U.

일반적인 집합 연산과 유사하게 중복도 함수를 사용하여 부분 다중집합을 정의할 수 있다. 다중집합 `(A, m)`에 대해, 밑집합 `A`의 부분집합 `B`를 밑집합으로 하는 다중집합 `(B, m)`에서 `B`의 각 원소 `b`의 중복도에 대해

:

m_B(b) \leq m_A(b)

가 성립할 때, 다중집합 `(B, m)`는 다중집합 `(A, m)`의 '''부분 다중집합'''이라고 하며, `(B, m) ⊂ (A, m)`로 나타낸다.

집합의 지시 함수와 다중집합의 정의 함수 비교
	집합의 지시 함수	다중집합의 정의 함수
교집합	$\chi_{A\cap B} = \min\{\chi_A,\chi_B\}$	$m_{A\cap B}(x) = \min\{m_A(x),m_B(x)\}(=: (m_A \wedge m_B)(x)),$
합집합	$\chi_{A\cup B} = \max\(x) ≤ m(x)`$
데카르트 곱	$\chi_{A \times B} = \chi_A\cdot\chi_B$	(정의되지 않음)
농도	>A\|=\sum_{x\in X} \chi_{A}(x)	(정의되지 않음)

합집합, 교집합, 차집합, 합(결합)에 대한 내용은 하위 섹션을 참고하라.

4. 1. 합집합

두 중복집합

A

,

B

의 합집합

C

는 각 원소의 중복도 중 최댓값을 취하여 계산한다.^[13] 즉,

C

의 중복도 함수

m_C(x)

는 다음과 같이 정의된다.

:

m_C(x) = \max(m_A(x),m_B(x))\quad\forall x\in U.

여기서

m_A(x)

,

m_B(x)

는 각각 중복집합

A

,

B

의 원소

x

에 대한 중복도 함수이고,

U

는 전체 집합이다. 이는 각 원소별로 두 중복집합의 중복도를 비교하여 더 큰 값을 선택하는 방식이다.

이러한 합집합 연산은 '최대값' 또는 '최소 공배수'라고 불리기도 한다.

4. 2. 교집합

두 중복집합의 교집합은 각 원소의 중복도 중 최솟값을 취하여 계산된다.^[13] 즉, 두 중복집합 *A*와 *B*의 교집합 *C*의 중복도 함수는 다음과 같이 정의된다.

:

m_C(x) = \min(m_A(x),m_B(x))\quad\forall x\in U.

여기서 `m_A(x)`와 `m_B(x)`는 각각 중복집합 *A*와 *B*의 원소 *x*에 대한 중복도를 나타낸다. 이러한 교집합은 일부 맥락에서 "하한" 또는 "최대 공약수"라고 불리기도 한다.

4. 3. 차집합

와 의 차집합은 중복도 함수가 다음과 같은 중복 집합 이다.^[13]

:

m_C(x) = \max(m_A(x) - m_B(x), 0)\quad\forall x\in U.

4. 4. 합 (결합)

두 중복집합의 합(결합)은 각 원소의 중복도를 더한 값을 취한다.^[13] ''A''와 ''B''의 합은 중복도 함수가 다음과 같은 중복 집합 ''C''이다.

:

m_C(x) = m_A(x) + m_B(x)\quad\forall x\in U.

이는 집합의 분리 합집합의 일반화로 볼 수 있다. 이는 주어진 전체 집합 내의 유한 중복 집합에 대한 가환 모노이드 구조를 정의한다. 이 모노이드는 전체 집합을 기저로 하는 자유 가환 모노이드이다.

두 중복 집합의 지지 집합이 상호 배타적 집합이면 해당 중복 집합은 ''상호 배타적''이다. 이는 교집합이 빈 중복 집합이거나 합이 합집합과 같다고 말하는 것과 동일하다.

다중집합의 합, 곱, 대칭차 등의 중복도 함수는, 집합의 지시 함수가 만족하는 것과 마찬가지의 산술에 따른다.

:

m_{A\sqcup B}(x) = m_A(x) + m_B(x)

가 성립한다. 특히 밑집합이 교차를 갖지 않을 때는

:

m_{A\sqcup B}(x) = \max\{m_A(x),m_B(x)\} = \begin{cases}m_A(x) & (x\in A)\\ m_B(x) & (x\in B)\end{cases}

로 쓸 수 있다.

5. 성질

집합 x^영어를 단항식 x로 나타내면, 그 멱집합은 이항식 1 + x로 나타낼 수 있다. 집합 x, y^영어를 단항식 xy에 대응시키면 그 멱집합은 다항식 (1 + x)(1 + y) = 1 + x + y + xy에 대응된다. 마찬가지로, 중복 집합 x, x^영어를 단항식 x²에 대응시키면, 그 멱중복집합(부분 중복 집합 전체를 이루는 중복 집합)는 다항식 (1 + x)² = 1 + 2x + x²에 대응한다. 단항식 xⁿ으로 표현되는 중복 집합의 멱중복집합이

:(1+x)ⁿ=\sum_{k=0}^n{n \choose k} x^k

로 표현되는 것은, 이항 계수 (ⁿ_k)가 n-원 집합에서 선택된 k-원의 조합의 총수를 계산하게 되는 이유를 설명한다.

집합 x^영어에서 원소를 가지는 유한 중복 집합 전체를 이루는 무한 집합은 형식적 멱급수 S = 1 + x + x² + x³ + ⋯ ( = 1 + xS)로 표현되며, 형식 해 S = (1 − x)⁻¹에 중복 집합의 집합으로서의 의미를 부여할 수 있지만, 중간 표현인 1 − x는 중복 집합의 집합으로서 의미를 갖지 않는다. 마찬가지로, 단항식 xy로 표현되는 집합 값을 가지는 유한 중복 집합 전체를 이루는 무한 집합은

:(1-x)^-1(1-y)^-1=1+(x+y)+(x²+xy+y²)+\dotsb

로 표현되며, 단항식 x²로 표현되는 중복 집합에서 원소를 가져 만들어지는 유한 중복 집합 전체를 이루는 무한 중복 집합은 x = y라는 특별한 경우로서 (1 − x)⁻² = 1 + 2x + 3x² + ⋯로 표현된다. 더 나아가 단항식 xⁿ에 대응하는 중복 집합에 값을 갖는 유한 중복 집합 전체를 이루는 무한 중복 집합은

:(1-x)^-n=\sum_{k=0}^\infty{-n \choose k} (-x)^k

이다. 이것을 "중복 집합은 농도가 음수인 집합"이라고 형식적으로 설명할 수 있다. '''음의 이항 계수''' (⁻ⁿ_k)는 n-원 집합에서 원소를 가져 얻어지는 k-원 중복 집합의 총수를 계산하는 것이다.

5. 1. 포함 관계

중복집합 가 중복집합 에 ''포함''된다는 것은 (''A'' ⊆ ''B'')로 표시되며, 모든 에 대해 다음 조건을 만족하는 것을 의미한다.

:

m_A(x) \le  m_B(x)

여기서

m_A(x)

와

m_B(x)

는 각각 중복집합 와 의 중복도 함수이다.^[13] 이는 중복집합 의 모든 원소의 중복도가 중복집합 에서의 해당 원소의 중복도보다 작거나 같다는 것을 뜻한다.

5. 2. 상호 배타적

두 중복집합이 상호 배타적이라는 것은 두 중복집합의 지지 집합이 서로소인 경우를 말한다.^[13] 이는 두 중복집합의 교집합이 빈 중복집합이거나, 두 중복집합의 합이 두 중복집합의 합집합과 같다는 것과 같은 의미이다.

6. 예시

중복집합은 여러 상황에서 나타날 수 있다.

자연수 n의 소인수로 이루어진 중복집합이 있다. 여기서 원소의 기본 집합은 n의 소인수 집합이다.
대수 방정식의 해로 이루어진 중복집합이 있다.
행렬의 고유값이 있으며, 이들의 중복도는 일반적으로 근으로서의 특성 다항식의 중복도로 정의된다.

집합 {x}를 단항식 x로 나타내면, 그 멱집합 { {}, {x} }는 이항식 1 + x로 나타낼 수 있다. 집합 {x, y}를 단항식 xy에 대응시키면 그 멱집합 { {}, {x}, {y}, {x, y} }는 다항식 (1 + x)(1 + y) = 1 + x + y + xy에 대응된다. 마찬가지로, 중복집합 {x, x}를 단항식 x²에 대응시키면, 그 멱중복집합(부분 중복 집합 전체를 이루는 중복 집합) { {}, {x}, {x}, {x, x} }는 다항식 (1 + x)² = 1 + 2x + x²에 대응한다. 단항식 xⁿ으로 표현되는 중복 집합의 멱중복집합이

:

(1+x)^n=\sum_{k=0}^n{n \choose k} x^k

로 표현되는 것은, 이항 계수 nCk 가 n-원 집합에서 선택된 k-원의 조합의 총수를 계산하게 되는 이유를 설명한다.

집합 {x}에서 원소를 가지는 유한 중복 집합 전체를 이루는 무한 집합 { {}, {x}, {x, x}, {x, x, x}, … }는 형식적 멱급수 S = 1 + x + x² + x³ + ⋯ (= 1 + xS)로 표현되며, 형식 해 S = (1 - x)^-1에 중복 집합의 집합으로서의 의미를 부여할 수 있지만, 중간 표현인 1 - x는 중복 집합의 집합으로서 의미를 갖지 않는다. 마찬가지로, 단항식 xy로 표현되는 집합 값을 가지는 유한 중복 집합 전체를 이루는 무한 집합은

:

(1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+\dotsb

로 표현되며, 단항식 x²로 표현되는 중복 집합에서 원소를 가져 만들어지는 유한 중복 집합 전체를 이루는 무한 중복 집합은 x = y라는 특별한 경우로서 (1 - x)^-2 = 1 + 2x + 3x² + ⋯로 표현된다. 더 나아가 단항식 xⁿ에 대응하는 중복 집합에 값을 갖는 유한 중복 집합 전체를 이루는 무한 중복 집합은

:

(1-x)^{-n}=\sum_{k=0}^\infty{-n \choose k} (-x)^k

이다. 이것을 "중복 집합은 농도가 음수인 집합"이라고 형식적으로 설명할 수 있다. '''음의 이항 계수''' -nCk는 n-원 집합에서 원소를 가져 얻어지는 k-원 중복 집합의 총수를 계산하는 것이다.

6. 1. 소인수 분해

素因數分解|소인수 분해^중국어는 자연수를 소인수들의 중복집합으로 표현할 수 있다. 예를 들어 120은 다음과 같은 소인수 분해를 갖는다.

:120 = 2³ × 3¹ × 5¹

이는 중복집합 {2, 2, 2, 3, 5}로 표현할 수 있다.^[53]

6. 2. 다항식의 근

대수 방정식의 해는 중복집합으로 나타낼 수 있다. 예를 들어, 이차 방정식은 두 개의 해를 가지는데, 두 해가 같은 숫자일 수도 있다. 방정식의 해를 중복집합으로 표현하면 또는 와 같이 나타낼 수 있다. 후자의 경우 해의 중복도는 2이다. 대수학의 기본 정리에 따르면, 다항 방정식의 복소수 해는 차수가 인 경우 항상 크기가 인 중복집합을 이룬다.^[53]

6. 3. 행렬의 고유값

행렬의 고유값은 중복도를 고려하여 중복집합으로 표현할 수 있다. 고유값의 중복도는 일반적으로 특성 다항식의 근으로서의 중복도로 정의된다.^[53] 그러나 고유값에 대해 자연스럽게 정의되는 다른 두 가지 중복도가 있는데, 이는 최소 다항식의 근으로서의 중복도와 기하학적 중복도이다. 기하학적 중복도는 의 커널의 차원으로 정의된다(여기서 는 행렬 의 고유값이다). 이 세 가지 중복도는 세 개의 고유값 중복집합을 정의하며, 이는 모두 다를 수 있다. 가 단일 고유값을 갖는 요르단 정규형의 행렬이라고 하자. 고유값의 중복도는 이고, 최소 다항식의 근으로서의 중복도는 가장 큰 요르단 블록의 크기이며, 기하학적 중복도는 요르단 블록의 수이다.

7. 응용

중복 집합은 조합론, 관계형 데이터베이스, 다중 그래프 등 다양한 분야에서 활용된다.

리처드 라도는 집합족의 속성을 조사하는 데 중복 집합을 사용하면서, "집합의 개념은 구성원의 중복 발생을 고려하지 않지만, 이러한 종류의 정보가 자주 중요하다. 다항식 ''f'' (''x'')의 근 집합이나 선형 연산자의 스펙트럼을 생각하면 된다."라고 언급했다.^[5]

조합론: 중복 집합은 조합론에서 중요한 연구 대상이 되었으며, 현대 조합론은 집합이 아닌 다중 집합에 대한 이론으로 발전했다.^[55]^[56]^[57]^[58]
관계형 데이터베이스: 데이터베이스 시스템에서 관계를 구현하는 데 중복 집합이 자주 사용된다. 특히, (기본 키가 없는) 테이블은 여러 개의 동일한 레코드를 가질 수 있기 때문에 중복 집합으로 작동한다. SQL 쿼리의 결과는 중복 집합이다.^[59]^[60]^[61]
다중 그래프: 다중 그래프에서는 주어진 두 정점 사이에 여러 개의 간선이 있을 수 있다. 따라서 간선을 지정하는 개체는 집합이 아닌 중복 집합이다.^[7]

7. 1. 조합론

기수가 n인 유한 집합에서 원소를 가져와 만든 기수가 k인 중복집합의 개수를 '''중복집합 계수''' 또는 '''중복집합 수'''라고 한다. 이 숫자는 이항 계수와 유사하게

\textstyle\left(\!\!{n\choose k}\!\!\right)

로 표기되기도 하며, "n 멀티초이스 k"로 읽을 수 있다. 이는 이항 분포와 유사하게, 중복집합 계수가 사용되는 음이항 분포가 있기 때문이다. 중복집합 계수는 다항 정리에서 나타나는 다항 계수와는 다른 개념이다.

중복집합 계수의 값은 다음과 같이 명시적으로 나타낼 수 있다.

\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인 부분집합의 개수와 같다. 이항 계수와의 관계는 위의 식에서 분자를 상승 계승 거듭제곱으로 나타내면 더 명확해진다.

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

이는 하강 계승 거듭제곱을 사용한 이항 계수의 표현과 유사하다.

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

예를 들어, 기수가 2인 집합 {1, 2}에서 원소를 가져와 만든 기수가 3인 중복집합은 {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, {2, 2, 2}로 총 4개이다. (n=2, k=3) 한편, 기수가 4인 집합 {1, 2, 3, 4} (n+k-1)의 기수가 3인 부분집합 역시 {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}로 4개이다.

중복집합 계수와 이항 계수의 동등성을 수학적 증명하는 간단한 방법은 다음과 같다. 먼저, a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d (6개의 a, 2개의 b, 3개의 c, 7개의 d)와 같은 중복집합을 표현하는 방법을 생각해보자.

이는 기수가 4인 집합의 원소로 구성된 기수가 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,

이므로 중복집합 계수와 그 동등성은 다음과 같다.

\begin{align}\left(\!\!{4\choose18}\!\!\right)&={21\choose18}=\frac{21!}{18!\,3!}={21\choose3}, \\[1ex]&=\frac{\mathbf{1\cdot2\cdot3}\cdot{\color{red}4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}, \\[1ex]&=\frac{1\cdot2\cdot3\cdot4\cdot5\cdots16\cdot17\cdot18\;\mathbf{\cdot\;19\cdot20\cdot21}}{\,1\cdot2\cdot3\cdot4\cdot5\cdots16\cdot17\cdot18\;\mathbf{\cdot\;1\cdot2\cdot3\quad}}, \\[1ex]&=\frac{19\cdot20\cdot21}{1\cdot2\cdot3}.\end{align}

이항 계수와 중복집합 계수 사이의 관계를 이용하여, 기수가 n인 집합에서 기수가 k인 중복집합의 개수를 다음과 같이 나타낼 수 있다.

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

또한, 다음이 성립한다.

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

다중집합은 여러 분야에서 활용된다.^[46] 다중집합은 조합론에서 중요한 연구 대상이 되었으며, 현대 조합론은 집합 대신 다중집합을 중심으로 발전해왔다.^[55]^[56]^[57]^[58] 또한 다중집합은 데이터베이스 시스템에서 중요한 도구로 사용되며,^[59]^[60]^[61] 데이터베이스 관계를 표현하는 데 자주 활용된다. 컴퓨터 과학 분야에서도 다중집합은 중요한 역할을 한다.^[36]

Richard Rado|리처드 라도^영어는 집합족의 성질을 연구하는 데 다중집합을 활용했다. 그는 "집합의 개념은 각 원소가 몇 번 나타나는지를 고려하지 않지만, 이러한 정보는 종종 중요해진다. 다항식 f(x)의 근 전체로 이루어진 집합이나 선형 연산자의 스펙트럼 등을 생각해보면 알 수 있다"고 언급했다.^[43]

7. 2. 데이터베이스

관계형 데이터베이스 이론에서 중복 집합은 "bag"이라는 동의어로 종종 사용되며 중요한 도구가 되었다.^[21]^[22]^[23] 예를 들어, 데이터베이스 시스템에서 관계를 구현하는 데 중복 집합이 자주 사용된다. 특히, (기본 키가 없는) 테이블은 여러 개의 동일한 레코드를 가질 수 있기 때문에 중복 집합으로 작동한다. 마찬가지로, SQL은 중복 집합을 사용하여 동일한 레코드를 반환한다. 예를 들어, "SELECT name from Student"를 생각해 보자. 학생 테이블에 "Sara"라는 이름을 가진 여러 레코드가 있는 경우, 그 레코드들이 모두 표시된다. 즉, SQL 쿼리의 결과는 중복 집합이다. 만약 결과가 집합이었다면, 결과 집합에서 반복되는 레코드가 제거되었을 것이다.

7. 3. 다중 그래프

다중 그래프에서는 주어진 두 정점 사이에 여러 개의 간선이 있을 수 있다. 따라서 간선을 지정하는 개체는 집합이 아닌 중복 집합이다.^[7]

8. 일반화

중복집합은 여러 가지 방식으로 일반화되어 연구 및 문제 해결에 적용되어 왔다. 주요 일반화 방식은 다음과 같다.

실수 값 중복 집합: 요소의 중복성을 임의의 실수로 나타낸다.^[24]^[25]
퍼지 중복 집합: 중복도 함수가 [0, 1] 구간의 값을 갖는다.^[26]
러프 중복 집합: 러프 집합 개념을 중복집합에 적용한 것이다.^[27]
하이브리드 집합^[28]
중복성이 임의의 실수 값 계단 함수인 중복 집합^[29]
소프트 중복 집합^[30]
소프트 퍼지 중복 집합^[31]
명명된 집합: 집합의 모든 일반화를 통합한다.^[32]^[33]^[34]^[35]

이 외에도 Fuzzy multisets^[62], Hybrid sets^[66], Named set^[70]^[71]^[72]^[73] 등이 있다.

8. 1. 실수 값 중복집합

요소의 중복성이 임의의 실수일 수 있다.^[24]^[25] 중복도 함수의 값역을 변경하여 중복도를 음수를 포함한 정수값이나 실수값 등으로 확장하여 생각할 수 있다. 확장된 의미에서의 다중집합에 관한 다중집합 연산은, 대개의 경우 음수가 아닌 정수값의 경우 중복도 함수의 산술이 그대로 성립하는 것으로 연산 후의 중복도 함수를 정하고, 그것에 의해 특징지어지는 다중집합으로 정의된다.^[64]^[65]

8. 2. 퍼지 중복집합

퍼지 집합(애매 집합, 확률적 집합)은 중복도 함수가 구간 [0, 1]의 값을 갖는 다중집합으로 볼 수 있다.^[26]^[62] 이 때 퍼지 집합의 귀속률 함수(멤버십 함수)가 중복도 함수에 해당한다. 단, 전체 집합 ''X''를 고정하고 그 부분 집합만을 퍼지 집합으로 간주할 경우, (확률적 해석을 위해) ''X''의 임의의 분할

:

X = \sum_{\lambda\in\Lambda}A_\lambda

에 대해,

:

(\mu_X =) \sum_{\lambda\in\Lambda}\mu_{A_\lambda} \equiv 1

이 되도록 귀속률 함수에 제약을 가하는 경우도 많다.

8. 3. 러프 중복집합

러프 집합 개념을 중복집합에 적용한 것이다.^[27]^[63]

8. 4. 소프트 중복집합, 소프트 퍼지 중복집합

소프트 집합 개념을 중복집합에 적용한 소프트 중복집합^[30]과 소프트 퍼지 중복집합^[31]이 연구되었다.

9. 한국의 관점

한국에서는 중복집합의 개념이 직접적으로 교육과정에 명시되어 있지는 않지만, 경우의 수를 다루는 다양한 문제 상황에서 간접적으로 활용된다. 특히, 확률과 통계 과목에서 조합, 순열 등을 학습할 때 중복집합의 개념이 응용될 수 있다. 예를 들어, 서로 다른 종류의 과일이 여러 개 있을 때, 중복을 허용하여 과일을 선택하는 경우의 수를 계산하는 문제는 중복조합의 대표적인 예시이며, 이는 중복집합의 개념과 연결된다.

참조

_[1] 논문 beiträge zur begründung der transfiniten Mengenlehre http://brinkmann-du.[...] New York Dover Publications (1954 English translation) 1895
_[2] 서적 Discrete mathematics https://archive.org/[...] Jones & Bartlett Publishers
_[3] 서적 Seminumerical Algorithms Addison Wesley 1998
_[4] 논문 Multiset theory http://projecteuclid[...]
_[5] 논문 The Development of Multiset Theory http://projecteuclid[...]
_[6] 간행물 QA4: A Procedural Calculus for Intuitive Reasoning 1972-11
_[7] 논문 An overview of the applications of multisets
_[8] 논문 Leibniz's misunderstanding of Nizolius' notion of 'multitudo'
_[9] 서적 Musurgia Universalis https://archive.org/[...] Corbelletti
_[10] 서적 Elemens des Mathematiques André Pralard
_[11] 서적 A treatise of algebra John Playford
_[12] 서적 Was sind und was sollen die Zahlen? Vieweg
_[13] conference Multiset Processing, Mathematical, Computer Science, and Molecular Computing Points of View [Workshop on Multiset Processing, WMP 2000, Curtea de Arges, Romania, August 21–25, 2000] Springer
_[14] 논문 Characteristic Functions and the Algebra of Logic 1933
_[15] 논문 The Concept of Multiset 1987
_[16] 문서 Cf., for instance, Richard Brualdi, Introductory Combinatorics, Pearson.
_[17] 서적 Combinatorial Theory Springer Verlag
_[18] 서적 Combinatorics of Finite Sets https://archive.org/[...] Clarendon Press
_[19] 서적 Enumerative Combinatorics http://www-math.mit.[...] Cambridge University Press
_[20] 서적 Enumerative Combinatorics Cambridge University Press
_[21] 논문 Towards tractable algebras for bags
_[22] 서적 Proceedings of the Workshop on Database Programming Languages Springer Verlag
_[23] 논문 On representation and querying incomplete information in databases with bags
_[24] 논문 Real-valued Multisets and Fuzzy Sets
_[25] 논문 Negative Membership
_[26] 논문 On the Theory of Bags
_[27] 서적 Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems
_[28] 논문 Sets with a negative numbers of elements
_[29] 서적 Multiset Processing
_[30] 논문 Soft Multisets Theory
_[31] 논문 Fuzzy Soft Multiset Theory
_[32] 서적 Structures in Mathematical Theories San Sebastian
_[33] 논문 On the concept of a multiset in cybernetics
_[34] arXiv Unified Foundations of Mathematics
_[35] 서적 Theory of Named Sets Nova Science Pub Inc
_[36] 서적 The Art of Computer Programming – Vol. 2: Seminumerical Algorithms Addison Wesley
_[37] 간행물 The development of multiset theory https://projecteucli[...] 2022-02-12
_[38] 서적 수에 대해 岩波書店
_[39] 간행물 Mathematics of Multisets http://citeseerx.ksu[...] Springer-Verlag 2010-11-26
_[40] 서적 Discrete mathematics Jones & Bartlett Publishers
_[41] 문서 Cristian S. Calude, Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa, Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View Springer Verlag 2001, ISBN 3-540-43063-6 S. 105
_[42] 간행물 Multiset theory http://projecteuclid[...]
_[43] 간행물 The Development of Multiset Theory http://projecteuclid[...]
_[44] 서적 Petri Net Theory and the Modelling of Systems http://jklp.org/prof[...] Prentice-Hall
_[45] 보고서 Formal Control Flow Properties of a Model of Computation Computer Science Department, University of California 1971-12
_[46] 간행물 An overview of the applications of multisets
_[47] 간행물 Leibniz's misunderstanding of Nizolius' notion of 'multitudo'
_[48] 서적 Musurgia Universalis Corbelletti
_[49] 서적 Elemens des Mathematiques André Pralard
_[50] 서적 A treatise of algebra John Playford
_[51] 서적 Was sind und was sollen die Zahlen? Vieweg
_[52] 서적 Multiset processing: Mathematical, computer science, and molecular computing points of view Springer-Verlag
_[53] 문서 예를 들어
_[54] 문서 MathWorld
_[55] 서적 Combinatorial Theory Springer Verlag
_[56] 서적 Combinatorics of Finite Sets Clarendon Press
_[57] 서적 Enumerative Combinatorics http://www-math.mit.[...] Cambridge University Press
_[58] 서적 Enumerative Combinatorics Cambridge University Press
_[59] 간행물 Towards tractable algebras for bags
_[60] 서적 Proceedings of the Workshop on Database Programming Languages Springer Verlag
_[61] 간행물 On representation and querying incomplete information in databases with bags
_[62] 간행물 On the Theory of Bags
_[63] 서적 Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems
_[64] 간행물 Real-valued Multisets and Fuzzy Sets
_[65] 간행물 Negative Membership
_[66] 간행물 Sets with a negative numbers of elements
_[67] 간행물 Fuzzy Multisets and their Generalizations
_[68] 간행물 Soft Multisets Theory
_[69] 간행물 Fuzzy Soft Multiset Theory
_[70] 서적 Structures in Mathematical Theories San Sebastian
_[71] 논문 On the concept of a multiset in cybernetics
_[72] 간행물 Unified Foundations of Mathematics
_[73] 서적 Theory of Named Sets Nova Science Pub Inc

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com