열거 조합학

열거 조합학은 특정 패턴이 형성될 수 있는 여러 가지 방법을 다루는 조합론의 한 분야입니다.이러한 유형의 문제의 두 가지 예는 조합 카운트와 순열 카운트입니다.보다 일반적으로, 자연수에 의해 지수화된 유한 집합_i S의 무한 집합이 주어졌을 때, 열거 조합학은 각 n에 대해 S의_n 개체 수를 세는 계수 함수를 기술하려고 한다.집합의 요소 수를 세는 것은 다소 광범위한 수학 문제이지만, 응용 프로그램에서 발생하는 문제의 대부분은 비교적 단순한 조합 기술을 가지고 있습니다.12배 방법은 순열, 조합 및 파티션을 계산하기 위한 통합 프레임워크를 제공합니다.

가장 간단한 함수는 닫힌 공식으로, 인수, 검정력 등의 기본 함수의 구성으로 표현될 수 있습니다.예를 들어, 아래와 같이 n장의 카드 한 벌의 다른 가능한 순서의 수는 f(n) = n!이다.닫힌 공식을 찾는 문제는 대수적 열거로 알려져 있으며, 종종 반복 관계를 도출하거나 함수를 생성하고 이를 사용하여 원하는 닫힌 형식에 도달하는 것을 포함한다.

종종 복잡한 닫힌 공식은 카운트된 객체의 수가 증가함에 따라 카운트 함수의 동작에 대한 통찰력을 거의 제공하지 않습니다.이러한 경우에는 단순한 점근 근사치가 바람직할 수 있다.$함수{\displaystyle }$ g$)$ {$displaystyle$ g$($$n)}$는 $f{\displaystyle (n)}$ {$displaystyle$ f$(n$${\displaystyle )\}}$$$${\displaystyle \to }$ 1 {{$displaystyle$f($n)/g(n)\$$rightarrow$1)에 $대한{\displaystyle }$ 점근법이다${\displaystyle \mathrm{.}}$ 이 경우$,$ g${\displaystyle (n)}$라고 쓴다.$,}$

함수 생성

생성 함수는 조합 객체의 패밀리를 설명하는 데 사용됩니다.$(\$는 객체 패밀리를 나타내고 F(x)를 생성 함수라고 합니다.그리고나서

${\displaystyle F(x)=\sum _{n=0}^{\infty}f_{n}x^{n}$

${\displaystyle {여기}_{}}$서 f n$${\$displaystyle f_{$n}}은 크기가 n인 조합 객체의 수를 나타냅니다.따라서 크기 n의 조합 객체의 수는 x $(\$ x$^{n$의 계수로 지정됩니다. 조합 객체의 패밀리에 대한 몇 가지 일반적인 연산과 생성 함수에 대한 영향을 개발합니다.지수 생성 함수를 사용하는 경우도 있습니다.이 경우 다음과 같은 형태를 갖습니다.

${\displaystyle F(x)=\sum _{n=0}^{\infty }f_{n}{\frac {x^{n}}{n!}}}$

일단 결정되면, 생성 함수는 이전의 접근법에 의해 주어진 정보를 산출한다.또한, 덧셈, 곱셈, 미분 등의 함수를 생성하는 다양한 자연 연산은 조합적 의미를 가지며, 이를 통해 하나의 조합적 문제에서 다른 문제를 해결하기 위해 결과를 확장할 수 있다.

유니언

F$($x)와 $G{\displaystyle \mathcal{}}$(x)의 생성함수인 F($style)$와 G$($)의 2개의 조합군(\display\mathcal ${F$$})$이 주어졌을 때, 두 계열$display\$style$\mathcal {F$$cup\mathcal {G})$의 분리결합은 F(x)를 생성함수 + 생성함수이다.

쌍들

두 패밀리의 데카르트 곱(쌍) 위에 있는 두 조합 패밀리의 경우($F$ ${\displaystyle \times }$ \style $\mathcal {F}\times \mathcal {G}$ )는$$생성 함수 F(x)G(x)를 갖는다.

시퀀스

(무한) 시퀀스는 위에서 정의한 쌍의 아이디어를 일반화합니다.시퀀스는 조합 객체와 조합 객체의 임의의 데카르트 산물이다.형식:

${\displaystyle {\mbox{Seq}}({\mathcal {F}})=\epsilon \cup \\mathcal {F}\cup \\mathcal {F}\!\times \!컵!(*************************){\mathcal {F}}\\cup \cdots}$

위의 내용을 말로 표현하면:빈 배열 또는 한 요소의 배열 또는 두 요소의 배열 또는 세 요소의 배열 등.생성 함수는 다음과 같습니다.

$({displaystyle 1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots =param frac {1}{1-F(x)}}}).$

조합 구조

이제 위의 연산을 사용하여 트리(이진수 및 평면), 다이크 경로 및 사이클을 포함한 공통 조합 개체를 열거할 수 있습니다.조합 구조는 원자로 구성되어 있다.예를 들어 나무에서는 원자가 노드입니다.물체를 구성하는 원자는 라벨이 붙어 있거나 라벨이 붙어 있지 않을 수 있습니다.라벨이 붙어 있지 않은 원자는 서로 구별할 수 없지만 라벨이 붙어 있는 원자는 구별됩니다.따라서, 라벨이 붙은 원자로 이루어진 조합 물체의 경우, 두 개 이상의 원자를 간단히 교환함으로써 새로운 물체가 형성될 수 있다.

이진 트리 및 평면 트리

바이너리 트리와 평면 트리는 라벨이 부착되지 않은 조합 구조의 예입니다.트리는 주기가 없는 방식으로 가장자리로 연결된 노드로 구성됩니다.일반적으로 부모 노드가 없는 루트라는 노드가 있습니다.플레인 트리에서 각 노드는 임의의 수의 자식을 가질 수 있습니다.플레인 트리의 특수한 경우인 바이너리 트리에서 각 노드는 두 개의 자식을 가질 수도 있고 가지지 않을 수도 있습니다.$(\$는 모든 평면 트리의 패밀리를 나타냅니다.그런 다음 이 패밀리를 다음과 같이 반복적으로 정의할 수 있습니다.

${\displaystyle {P}={\bullet \}\times,{\mbox{Seq}}({\mathcal {P}})}}}$

이 경우${\displaystyle }${ ${\displaystyle \}}${\$display$\{\$bullet$\}}은$$(는) 하나의 노드로 구성된 객체 패밀리를 나타냅니다.여기에는 생성함수 x가 있습니다.P$($x)는 $생성함수{\displaystyle \mathcal{}}$P(\$displaystyle\mathcal$ {$P$를 나타냅니다.위의 설명을 말로 표현하면, 플레인 트리는 임의의 수의 서브트리가 연결된 노드로 구성되며, 각 노드는 플레인 트리입니다.이전에 개발된 조합 구조의 패밀리에 대한 연산을 사용하면 재귀 생성 함수로 변환됩니다.

${\displaystyle P(x)=x,{\frac {1}{1-P(x)}}}$

P(x)에 대해 해결한 후:

${\displaystyle P(x)=black {1-{\displayrt {1-4x}}{2}}$

이제ⁿ x의 계수를 추출하여 크기 n의 플레인 트리 수에 대한 명시적 공식을 구할 수 있다.

${\displaystyle {begin {n}&=[x^{n}]P(x)=[x^{n}}{1-{\fracrt {1-4x}}{2}}\[6pt]&=[x^{n}{\frac {1}{2}}-[x^{n}}{\frac {1}{2}{\frac rt {1-4x}}\\[6pt]&=-{1}{2}\sum _k=0}{\infty}{1}\frac{1}{\frac{1}{\frac{1}{\frac{\frac {1}}을 선택합니다.$

참고: [xⁿ] f(x) 표기법은 f(x)의 xⁿ 계수를 나타냅니다.제곱근의 급수 팽창은 뉴턴의 이항정리에 대한 일반화에 기초한다.일반화 이항 계수를 사용하여 네 번째에서 다섯 번째까지 선 조작을 얻으려면 이항 계수가 필요합니다.

마지막 줄의 식은 (n - ^st1) 카탈로니아 숫자와 같습니다.따라서_n p = c입니다_n−1.

「 」를 참조해 주세요.

레퍼런스

• Zeilberger, Doron, Enumative 및 Algebraic Combinatorics
• Björner, Anders and Stanley, Richard P., A Combinatory Miscellany
• Graham, Ronald L., Grottschel M. 및 Lavasz, Lasszlo, eds.(1996년).조합론 핸드북, 제1권 및 제2권엘세비어(노스홀랜드), 암스테르담, MIT 프레스, 캠브리지, 매사추세츠. ISBN0-262-07169-X.
• Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (2nd ed.). London: Penguin Books. ISBN 0-14-012529-9.
• 로어, 니콜라스 A. (2011년) A.Bijectionive Combinatorics.CRC 프레스ISBN 143984884X, ISBN 978-1439848845.
• 스탠리, 리처드 P.(1997, 1999).Enumative Combinatorics, Volume 1 및 2.케임브리지 대학 출판부ISBN 0-521-55309-1, ISBN 0-521-56069-1.
• Goulden, Ian P.와 Jackson, David M. (2004).조합 열거.도버 출판물ISBN 0486435970.
• Combinatory Analysis – 브리태니커 백과사전 제11판 기사
• 리오단, 존(1958년).뉴욕, Wiley & Sons, Combinatory Analysis의 개요(재출판).
• 리오단, 존(1968).뉴욕, Wiley & Sons, Combinatory Identity (재출판)
• Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press. ISBN 0-12-751956-4. Zbl 0831.05001.