콤비네토리얼 클래스

Combinatorial class

수학에서 콤비네이터 클래스는 각 물체를 음이 아닌 정수에 매핑하는 크기 함수와 함께 계산 가능한 수학적 물체의 집합으로, 각 크기의 물체가 매우 많다.[1][2]

시퀀스 및 이형성 계수

콤비네이터 클래스의 계수 순서는 i = 0, 1, 2, ...에 대한 크기 i의 원소 수의 순서다.; 이러한 숫자를 계수로 갖는 생성함수로도 설명될 수 있다.조합 클래스의 계수 순서는 열거 조합 연구의 주요 주제다.두 개의 결합체 클래스는 각 크기의 개체 수가 같을 경우 이형성이거나, 계수 순서가 같을 경우 동등하게 동일하다고 한다.[3]흔히 두 개의 결합체 클래스가 이형체라고 알려지면 이 등가성에 대한 비주사적인 증거를 찾는데, 그러한 증거는 두 이형체 클래스의 물체가 서로 암호화된 것임을 보여주는 것으로 해석될 수 있다.

예를 들어, 일반 다각형의 삼각형(폴리곤의 면수로 주어진 크기, 크기별로 삼각형을 이루는 고정된 다각형의 선택)과 뿌리박히지 않은 이항 평면 나무의 집합(이항형성을 그래프로 나타내기까지, 잎의 순서가 고정되고 잎의 수로 주어진 크기)은 모두 카탈라에 의해 계수된다.n개의 숫자, 그래서 그들은 이형 결합 클래스를 형성한다.이 경우 편평형 이형성은 평면 그래프 이중성에 의해 주어진다: 삼각형은 각 다각형 가장자리, 각 삼각형에는 내부 노드, 서로 인접한 두 개의 다각형 가장자리 또는 삼각형 각각에 대한 가장자리가 있는 나무로 비거주적으로 변환될 수 있다.[4]

분석 결합기

결합종 이론과 그 분석 결합학으로의 확장은 많은 중요한 결합 계급을 기술하고, 이전에 정의된 결합 계수의 조합으로부터 새로운 계급을 구성하며, 그들의 계산 순서를 자동으로 도출하는 언어를 제공한다.[3]예를 들어, 두 개의 결합 등급은 분리 결합 또는 두 등급 각각에서 한 개체의 쌍을 정렬하는 데카르트 제품 구조로 결합될 수 있으며, 크기 함수는 쌍에 있는 각 개체의 크기를 합한 값이다.이 연산들은 각각 0개 객체가 빈 결합체 클래스이고, 단위는 빈 집합인 (이형성 동등성 클래스) 결합체 클래스의 (이형성 동등성 클래스) 계열에 대한 의미 부여 및 곱셈 연산을 형성한다.[5]

순열 패턴

순열 패턴 연구에서는 순열 길이로 열거된 순열 클래스의 조합 클래스를 Wilf 클래스라고 한다.[6]특정 순열 클래스의 열거에 대한 연구는 연관성이 없어 보이는 순열 클래스의 시퀀스를 계산하는 데 있어서 예상치 못한 동등성을 발견했다.

참조

  1. ^ Martínez, Conrado; Molinero, Xavier (2001), "A generic approach for the unranking of labeled combinatorial classes" (PDF), Random Structures & Algorithms, 19 (3–4): 472–497, doi:10.1002/rsa.10025, MR 1871563.
  2. ^ Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles (2004), "Boltzmann samplers for the random generation of combinatorial structures", Combinatorics, Probability and Computing, 13 (4–5): 577–625, doi:10.1017/S0963548304006315, MR 2095975.
  3. ^ a b Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, Definition I.3, p.19, ISBN 9781139477161.
  4. ^ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25, Springer, Theorem 1.1.3, pp. 4–6, ISBN 9783642129711.
  5. ^ Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579.
  6. ^ Steingrímsson, Einar (2013), "Some open problems on permutation patterns", Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser., vol. 409, Cambridge Univ. Press, Cambridge, pp. 239–263, MR 3156932