이 기사는 분석 조합의 방법에 관한 것이다. 불변 이론의 방법은 기호 방법을 참조하십시오. 조합학에서 상징적인 방법은 조합물체를 세는 기술이다. 그것은 물체의 생성함수에 대한 공식을 도출하기 위해 물체의 내부 구조를 이용한다. 이 방법은 대부분 필리프 플라호레와 연관되어 있으며 그의 저서 A부에 로버트 세지윅과 함께 자세히 설명되어 있는 반면, 이 책의 나머지 부분에서는 해당 발생함수에 대한 점증적 및 확률론적 결과를 얻기 위해 복잡한 분석을 사용하는 방법을 설명하고 있다.
2세기 동안, 그들의 계수에 대한 상응하는 재발을 통해 생성 기능이 나타나고 있었다(버누이, 오일러, 아서 케이리, 슈뢰더, 라마누잔, 리오단, 크누스, 콤테트[fr] 등의 세미 작품에서 볼 수 있다). 그 후 생성 기능이 초기 이산 결합 물체의 다른 많은 면을 포착하고 있으며, 이는 보다 직접적인 공식적 방법으로 이루어질 수 있다는 것을 서서히 깨달았다. 일부 조합 구조의 재귀적 특성은 일부 이형성을 통해 해당 생성함수에 주목할 만한 정체성으로 변환한다. 따라서 Polya의 작품에 이어, 1970년대에는 순열에 관한 Foata와 Schützenberger[1], prefabs에 관한 Bender와 Goldman,[2] 결합 종에 관한 Joyal의 작품에서 볼 수 있듯이 결합 계급과 그 생성 기능을 명시하기 위한 언어의 총체적인 사용으로 이러한 정신에서 더 많은 발전이 이루어졌다.[3]
열거에 있어서 이 상징적인 방법은 단지 탯줄 미적분학의 또 다른 옛 이름일 뿐인 "블리사드의 상징적인 방법"과는 무관하다는 점에 유의한다.
결합기에서의 상징적 방법은 컴퓨터 대수학을 통한 자동화에 적합하게 되는 빠른 연산 체계로 이어질 수 있는 결합기 구조의 많은 분석의 첫 번째 단계를 구성한다.
조합 구조 등급
생성함수에 의해 주어진 객체를 n개의 슬롯 세트로 분산시키는 문제를 고려해 보십시오. 여기서 순열 그룹 G ° n은 슬롯에 작용하여 채워진 슬롯 구성의 동등성 관계를 만들고, 이 동등성과 관련하여 구성의 가중치를 기준으로 구성의 생성 기능에 대해 물어 보십시오. 관계, 여기서 구성의 가중치는 슬롯에 있는 객체의 가중치 합이다. 우리는 먼저 라벨이 부착된 사례와 라벨이 부착되지 않은 사례에서 이 문제를 해결하는 방법을 설명하고 이 솔루션을 사용하여 조합 구조의 클래스 생성에 동기를 부여할 것이다.
Polya 열거 정리는 라벨이 붙지 않은 사례에서 이 문제를 해결한다. f(z)를 객체의 일반 생성 함수(OGF)로 설정한 다음, 구성의 OGF를 대체 사이클 인덱스에 의해 부여한다.

라벨링된 경우 우리는 물체의 지수 생성 함수(EGF) g(z)를 사용하고 라벨링된 열거 정리를 적용하는데, 여기에는 구성의 EGF가 다음과 같이 명시되어 있다.

라벨이 부착되지 않은 케이스의 PET 또는 라벨이 부착된 케이스의 열거 정리를 사용하여 채워진 슬롯 구성을 열거할 수 있다. 이제 우리는 순열 그룹이 각각 작용하는 두 개 이상의 슬롯이 있을 때 얻은 구성의 생성 기능에 대해 질문한다. 분명히 궤도는 교차하지 않으며 우리는 각각의 생성 기능을 추가할 수 있다. 예를 들어, 길이 레이블이 지정되지 않은 시퀀스 중 세트 X에 포함된 일부 객체를 두 개 또는 세 개 열거한다고 가정합시다. 슬롯은 두 세트로 되어 있는데, 첫 번째 슬롯은 두 개의 슬롯이 있고, 두 번째 슬롯은 세 개의 슬롯이 있다. 첫 번째 세트에 작용하는 그룹은 2 }이고
두 번째 에 E {\
X의 다음과 같은 공식 파워 시리즈로 이것을 나타낸다.

여기서 X / X라는 용어는 G 및 = {\ X X에 따른 궤도의 집합을 나타내기 위해 사용되며
이는 반복과 함께 X의 객체를 N 슬롯으로 분배하는 과정을 분명하게 나타낸다. 마찬가지로 라벨이 표시된 개체 X 집합에서 임의 길이의 주기를 생성하는 레이블링된 문제를 고려하십시오. 이렇게 하면 다음과 같은 주기적 그룹의 일련의 작용이 발생한다.

분명히 우리는 순열 그룹에 관한 그러한 일련의 인용문(또는 비트)에 의미를 부여할 수 있다. 여기서 우리는 고유한 인자화 영역을 형성하는 대칭 그룹
의
결합 등급 Cl (){\n}}}에 n의 등급 n을 제한한다. (동일한 결합 등급의 두 그룹에 대한 궤도는 이형성이다.) 이것은 다음과 같은 정의에 동기를 부여한다.
구조물의 클래스 C
N []{\{\은(는) 정식 계열이다.

where
(the "A" is for "atoms") is the set of primes of the UFD
and
다음에 우리는 우리의 표기법을 약간 단순화하고 예를 들어 쓸 것이다.

위에 언급된 수업들을 위해.
Flajolet-Sedgewick 기본 정리
상징 결합학의 Flajolet-Sedgewick 이론의 정리는 조합 구조가 포함된 방정식을 직접 (그리고 자동으로) 생성함수의 생성 방정식으로 변환할 수 있게 하는 기호 연산자의 생성에 의해 라벨링되고 라벨링되지 않은 결합체 클래스의 열거 문제를 다룬다. 이 구조물들
[ {N을(를) 결합 구조로 분류하도록
한다. The OGF
of
where X has OGF
and the EGF
of
where X is labelled with EGF
are given by

그리고

라벨이 표시된 경우, X에 0 크기의 요소가 포함되지 않아야 한다는 추가 요구사항이 있다. 세트의 한 복사본이 존재함을 나타내기 위해
G( ) 에 하나를 추가하는 것이 때로는 편리함을 증명할 것이다. It is possible to assign meaning to both
(the most common example is the case of unlabelled sets) and 정리를 증명하기 위해서는
PET(Polya 열거 정리)와 라벨로 표시된 열거 정리만 적용하면 된다.
이 정리의 힘은 결합 계급을 나타내는 함수 생성에 관한 연산자를 구성할 수 있게 한다는 사실에 있다. 따라서 조합 등급 간의 구조적 방정식은 해당 생성함수의 방정식으로 직접 해석된다. 더욱이 라벨링된 사례에서 가 g( ) 을 원자 z로
대체하고 그 결과 연산자를 계산할 수 있다는 것은 공식으로부터 명백하며, 이는 EGF에 적용될 수 있다. 우리는 이제 가장 중요한 사업자를 건설하기 위해 진행한다. 독자는 사이클 인덱스 페이지의 데이터와 비교하기를 원할 수 있다.
시퀀스 연산자 SEQ
이 연산자는 클래스에 해당한다.

그리고 시퀀스를 나타낸다. 즉, 슬롯이 순열되지 않고 정확히 한 개의 빈 시퀀스가 있다. 우리는 가지고 있다.

그리고

사이클 연산자 CYC
이 연산자는 클래스에 해당한다.

즉, 하나 이상의 객체를 포함하는 주기. 우리는 가지고 있다.

또는

그리고

이 연산자와 설정 연산자 SET, 그리고 이들의 특정 등급 제한은 무작위 순열 통계를 계산하는 데 사용된다. 이 연산자에는 짝수 사이클과 홀수 사이클이라는 두 가지 유용한 제한이 있다.
이븐 사이클 연산자 CYC는even 다음과 같다.

어느 것이 생산되는가

이는 홀수 사이클 연산자 CYC로odd 라벨이 표시된 것을 의미한다.

에 의해 주어지다

멀티셋/셋 연산자 MSET/SET
시리즈는

즉, 대칭 그룹이 슬롯에 적용된다. 이것은 라벨이 부착되지 않은 케이스에 멀티셋을 만들고 라벨이 부착된 케이스에 세트를 만든다(레이블이 동일한 객체의 여러 인스턴스를 다른 슬롯에 넣는 세트와 구별하기 때문에 라벨이 부착된 케이스에는 멀티셋이 없다). 우리는 라벨이 부착된 케이스와 라벨이 부착되지 않은 케이스에 모두 빈 세트를 포함한다.
라벨이 부착되지 않은 케이스는 기능을 사용하여 수행된다.

하도록

( () , ) M( 평가 결과
얻음

라벨이 부착된 케이스의 경우

라벨이 부착된 케이스에서 우리는 운용자를 SET로, 라벨이 부착되지 않은 케이스에서 MSET로 나타낸다. 이것은 라벨이 부착된 경우에는 멀티셋(레이블이 복합 결합 등급의 성분을 구별함)이 없는 반면 라벨이 부착되지 않은 경우에는 멀티셋과 집합이 있고, 후자는 다음과 같이 지정되기 때문이다.

절차
일반적으로 0 크기의 단일 개체(중립 개체, 흔히 으로 표시됨
를 포함하는 중립 클래스 epsilon와 각각 크기가 1인 단일 개체를 포함하는 하나 이상의 원자 클래스 {로 시작한다
다음으로, 분리 유니언, 제품, 세트, 시퀀스, 멀티셋과 같은 다양한 단순 연산을 포함하는 집합-이론적 관계는 이미 정의된 클래스의 관점에서 더 복잡한 클래스를 정의한다. 이러한 관계는 재귀적일 수 있다. 상징 결합학의 우아함은 정해진 이론적 또는 상징적 관계가 직접 생성 기능을 포함하는 대수적 관계로 번역된다는 데 있다.
이 글에서는 스크립트 대문자를 사용하여 조합 클래스와 생성 함수에 해당하는 일반 문자를 나타내는 관례를 따르겠다(따라서 클래스 {에 함수 A )
기호 조합에 일반적으로 사용되는 생성함수의 유형에는 두 가지 유형이 있다. 즉, 라벨링되지 않은 객체의 조합 클래스에 사용되는 일반 생성함수와 라벨링된 객체의 클래스에 사용되는 지수 생성함수가 있다.
과
(와) Z 에 대한 생성 함수(일반 또는 지수)가
각각 z)=
(z)=}임을 보여주는 것은 사소한 일이다
The disjoint union is also simple — for disjoint sets
and
,
implies
. 다른 작업에 해당하는 관계는 라벨링된 구조 또는 라벨링되지 않은 구조(및 일반 또는 지수 생성 함수)에 대해 말하는지 여부에 따라 달라진다.
결합합계
노조의 노조해체 제한은 중요한 것이지만, 상징 조합의 공식 명세에서는 어떤 조합이 해체되는지 추적하는 것이 너무 어렵다. 대신 교차점이 없음을 보증하는 공법을 사용한다(단, 주의하라, 이것은 운영의 의미론에도 영향을 미친다). 두 세트 과
( B {\ {\ {의
조합 합계를 정의할
때 각 세트 구성원을 구별되는 마커로 표시한다
: A {\
조합 합계는 다음과 같다.

이것은 공식적으로 덧셈에 해당하는 작전이다.
라벨이 부착되지 않은 구조물
라벨이 부착되지 않은 구조에서는 일반 발생 함수(OGF)가 사용된다. {\의 OGF는 다음과 같이 정의된다
.

제품
조합 클래스 과
( B {\ {\ {의 곱은 순서 쌍의 크기를 쌍의 원소 크기의 합으로 정의하여 지정한다
. 및
,
( )=+ {\ (= 에 대한 정의가 상당히 직관적이어야 한다
A 에 있는 원소의 개수가 크기임을
알 수 있다. n 이다

OGF와 일부 초등 대수학의 정의를 이용하여, 우리는 그것을 보여줄 수 있다.
- = mathcal {{\는 () =B( C( )를 의미한다


순서
= { {\{\로 표시된 시퀀스 구성은 다음과 같이 정의된다
.

즉, 순서는 중성 원소 또는
의 원소 또는 순서 쌍, 순서 쌍, 순서 쌍, 순서 세 개 등이다. 이것이 인연으로 이어진다.

세트
= { 로 표시된 집합(또는 powerset) 구조는 다음과 같이 정의된다
.

그래서 관계가 맺어진 거야

확장된 곳

4호선에서 5호선으로 가는 데 쓰였다.
멀티셋
= { B 로 표시된 멀티셋 구조는 세트 구조의 일반화다
. 설정된 구조에서 각 원소는 0 또는 1회 발생할 수 있다. 다중 집합에서 각 요소는 임의의 횟수로 나타날 수 있다. 그러므로

이것이 인연으로 이어진다.

여기서, 위의 세트 구성과 유사하게, 우리는 ( z 을 확장하고 합계를 교환하며
{\의 OGF를 대체한다
기타 기초 시공
기타 중요한 기본 구조는 다음과 같다.
- 순환 구성({ 은 순환 회전이 구별되는 것으로 간주되지 않는다는 점을 제외하고 시퀀스처럼 구성된다.

- 포인팅(
- 이 경우, B의 각 멤버는 원자 중 하나에 대해 중성(영원자) 포인터를 사용하여 증강된다. - 치환(∘ {\{\ 여기서
B의 멤버에 있는 각 원자는 C의 멤버로 대체된다.
이 건축물의 유래는 너무 복잡해서 여기서는 알 수 없다. 결과는 다음과 같다.
건설 | 생성함수 |
| (where is the Euler totient function) |
| |
| |
예
많은 조합 수업은 이러한 기본적인 구조를 사용하여 건설될 수 있다. 예를 들어, 평면 나무의 등급(즉, 하위 트리의 순서가 중요하도록 평면에 내장된 나무)은 재귀적 관계에 의해 지정된다.

즉 트리는 크기 1의 루트 노드와 하위 트리의 시퀀스다. 이것으로 알 수 있다.

- () 을
곱하여 G(z)에 대해 해결함
2차 공식을 사용한 G(z)에 대한 분해 및 분해능은 다음과 같다.

또 다른 예(그리고 고전적인 조합 문제)는 정수 파티션이다. 먼저 양의 정수 의 클래스를 정의하십시오
여기서 각 정수의 크기는 해당 값입니다.

의 OGF가 그 다음인
경우

P {P 집합을 다음으로
정의하십시오.

의 OGF는

불행히도 ( ) 에 대해 닫힌 양식은 없지만, OGF를 사용하여 재발 관계를 도출하거나 보다 진보된 조합 분석 방법을 사용하여 카운팅 시퀀스의 점근거동을 계산할 수 있다
사양 및 지정 가능한 클래스
위에서 언급된 기본적인 구조는 규격의 개념을 정의할 수 있다. 이 규격은 다중 결합 등급과 함께 일련의 재귀 방정식을 사용할 수 있다.
Formally, a specification for a set of combinatorial classes
is a set of
equations
여기서 i 는 표현식이며
, 원자는 이고
는 위에 나열된 초기 이다.
조합 구조물의 종류는 규격을 인정할 때 구성 가능하거나 구체화할 수 있다고 한다.
예를 들어 잎의 깊이가 짝수(존중, 홀수)인 나무의 세트는 두 의 인 과
을 사용하여 정의할 수 있다
Those classes should satisfy the equation
and 이름 { {\
.
레이블 구조
물체는 원자가 각각 음이 아닌 정수 라벨을 가지고 있고 이러한 라벨이 각각 구별되는 경우 약하게 라벨을 표시한다. 물체는 (강력하게 또는 잘) 라벨로 표시된다. 더 나아가 이 라벨이 연속 정수[… n을(를) 구성한다
참고: 일부 조합 등급은 라벨로 표시된 구조물 또는 라벨이 부착되지 않은 구조물로 가장 잘 지정되지만, 일부는 두 규격을 모두 쉽게 인정한다. 라벨로 표시된 구조의 좋은 예는 라벨로 표시된 그래프의 등급이다.
라벨이 표시된 구조에는 지수 생성 함수(EGF)가 사용된다. {\의 EGF는 다음과 같이 정의된다
.

제품
라벨이 부착된 구조물에 대해서는 라벨이 부착되지 않은 구조물이 아닌 제품에 대해 다른 정의를 사용해야 한다. 사실, 만약 우리가 단순히 데카르트 제품을 사용한다면, 결과적인 구조들은 심지어 라벨을 잘 붙이지 않을 것이다. 대신 우리는 b {\ {로 표시된 소위 라벨링된 제품을 사용한다.
B {\ \in {\ { 및 ∈ 의
경우 두 구조를 하나의 구조로 결합하고자 한다
결과가 잘 표시되려면 및
의 원자를 다시 라벨링해야 한다
원래 라벨의 순서와 일치하는 다시 라벨링으로 주의를 제한한다. 다시 라벨을 부착하는 방법은 여전히 여러 가지가 있으므로 각 멤버 쌍은 제품 내 단일 멤버가 아니라 새로운 멤버 집합을 결정한다. 이 구성에 대한 자세한 내용은 라벨링된 열거 정리 페이지에서 확인할 수 있다.
이러한 개발을 돕기 위해
을(를) 인수로 α {\을(를) 정의하고
atoms(가 잘
라벨링되도록 순서에 따라 원자를 다시 배열한다. 그런 다음 두 α {\
} β {\에 대한 라벨링 제품을 정의한다
.

마지막으로 두 A 과
(와 {\ {\의 레이블이 붙은 제품은

EGF는 크기 및
n- 의
객체에 대해 다시 라벨링하는 방법k k이
있다는 점에 유의하여 도출할 수 있다. 따라서 크기가 인 개체의 총 수는

용어에 대한 이항성 경련 관계는 EGF를 곱한 것과 동일하다.

순서
시퀀스 구성 = G{ 은(는) 라벨링되지 않은 사례와 유사하게 정의된다
.

그리고 다시 상기처럼

세트
라벨이 표시된 구조에서 요소
집합은 정확히 ! k 시퀀스에
해당한다. 이것은 일부 순열이 일치하는 라벨이 없는 경우와는 다르다. 따라서 = { 에 대해서는 다음과 같이 한다

사이클
사이클 또한 라벨이 부착되지 않은 경우보다 쉽다. 의 사이클은 k 고유
시퀀스에 해당한다
. 따라서 = {
에 대해 다음을 수행하십시오.

상자형 제품
In labelled structures, the min-boxed product
is a variation of the original product which requires the element of
in the product with the minimal label. 마찬가지로 A = C {\ {\}}\{\
로 표시된 최대 상자 제품을 동일한 방법으로 정의할 수도 있다. 그럼, 우리는,

또는 동등하게

예
증가하는 Cayley 트리는 라벨이 붙지 않은 나무와 뿌리가 있는 나무로, 뿌리에서 유래한 가지에 따른 라벨이 증가하는 순서를 형성한다. 그런 L {\을(를) 그런 나무의 등급으로 한다
. 이제 이 = Z◻ ( L) . {L {mathcal
기타 기초 시공
연산자 CYCeven, CYCodd, SETeven 및 SET는odd 짝수 및 홀수 길이의 사이클과 짝수 및 홀수 카디널리티 세트를 나타낸다.
예
구조분해를 이용하여 두 번째 종류의 스털링 숫자를 도출하고 분석할 수 있다.

분해

첫 번째 종류의 서명되지 않은 스털링 숫자와 무작위 순열의 통계 도출에 사용된다. 심볼 콤비네이터학에서 스털링 숫자와 관련된 지수 생성 함수의 자세한 검사는 스털링 숫자 및 기호 콤비네이터학에서 지수 생성 함수의 페이지에서 확인할 수 있다.
참고 항목
참조
- 프랑수아 베르제론, 길버트 라벨레, 피에르 르루, 테오리 데 에스페스, 콤비나토아르 데스 구조 형광체, 라킴, 몬트레알(1994)이다. 영어 버전: 캠브리지 대학 출판부(1998년)의 조합종과 나무와 같은 구조.
- Cambridge University Press(2009년)의 Philipe Flajolet and Robert Sedgewick Analytic Combinatorics. (온라인: http://algo.inria.fr/flajolet/Publications/book.pdf)
- Micha Hofri, Analysis of Algorithm: Computing Methods and Matheical Tools, Oxford University Press (1995년)