웨더번 – 에더링턴 번호

웨더번-에테르링턴 수는 특정 종류의 이진 트리를 세는 데 사용될 수 있는 Ivor Malcolm Haddon Etherington과^[1][2] Joseph Wederburn의^[3] 이름을 딴 정수열입니다. 수열의 처음 몇개의 숫자는

0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ... (OEIS: A001190)

조합해석

이 숫자들은 조합 열거에서 여러 문제를 해결하는 데 사용될 수 있습니다. 시퀀스의 n번째 숫자(n = 0인 경우 0으로 시작) 카운트

• 루트를 포함한 모든 노드가 0개 또는 정확히 2개의 자식을 가지는 n개의 잎을 가진 순서 없는 루트 트리의 수입니다.^[4] 이 나무들은 Richard Outter의 조합적인 열거 작업의 이름을 ^[5]따서 Outter tree라고 불립니다.^[6] 그것들은 또한 주어진 수의 잎을 가진 라벨이 없고 순위가 매겨진 덴드로그램으로 해석될 수 있습니다.^[7]
• n개의 노드가 있는 순서 없는 루트 트리의 수 중 루트의 차수가 0 또는 1이고 다른 모든 노드는 최대 2개의 자식을 갖습니다.^[4] 루트에 최대 한 개의 자식이 있는 트리를 식재 트리라고 하며, 다른 노드에 최대 두 개의 자식이 있는 추가 조건은 약한 이진 트리를 정의합니다. 화학 그래프 이론에서 이 나무들은 지정된 잎 원자를 뿌리로 선택한 폴리엔의 이성질체로 해석될 수 있습니다.^[8]
• n명의 선수를 대상으로 한 단일 엘리미네이션 토너먼트를 구성하는 다양한 방법(선수 이름을 빈칸으로 유지하고 토너먼트에 선수를 시드하기 전)의 수.^[9] 그러한 토너먼트의 짝짓기는 수달 나무에 의해 설명될 수 있습니다.
• 서로 다른 방법으로 생성할 수 있는 서로 다른 결과 수. 교환적이라고 가정되지만 연관적이지도 않고 idempotent도 않은 이진 곱셈$$ $연산$에 ${\displaystyle {대해}^{}}$ x$$n {\$displaystyle x^{$n}} 식을 그룹화합니다.^[4] For instance ${\displaystyle x^{5}}$ can be grouped into binary multiplications in three ways, as ${\displaystyle x(x(x(xx)))}$, ${\displaystyle x((xx)(xx))}$, or ${\displaystyle (xx)(x(xx))}$. 이것은 원래 Etherington과^[1][2] Wederburn 모두가 고려한 해석이었습니다.^[3] 오터 트리는 각 리프 노드가 $x{\displaystyle }$ ${\displaystyle x}$의 복사본 중 하나에 해당하고$$ 각 리프 노드가 곱셈 연산에 해당하는 그룹화된 표현식으로 해석할 수 있습니다. 다른 방향으로, 두 개의 트리를 새로운 루트 노드의 두 서브트리로 만들어 결합하는 이진 곱셈 연산이 있는 모든 수달 트리 집합은 하나의 $생성기{\displaystyle }$ x ${\displaystyle x}($하나의 노드가 있는 트리)에서 자유 교환 마그마로 해석될 수 있습니다. 이 대수 구조에서 $x{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\$의 각 그룹은 n-리프 오터 트리 중 하나의 값을 갖습니다$$.^[10]

공식

Wedderburn-Etherington 수치는 재발 관계를 사용하여 계산할 수 있습니다.

${\displaystyle a_{2n-1}=\sum _{i=1}^{n-1}a_{i}a_{2n-i-1}}$

${\displaystyle a_{2n}={\frac {a_{n}(a_{n}+1)}{2}}+\sum _{i=1}^{n-1}a_{i}a_{2n-i}}$

${\displaystyle {기본}_{}}$ 케이스 a 1 = ${\displaystyle 1}$ ${\$displaystyle a_{1}=1}부터 시작합니다.

n개의 잎을 가진 뿌리 이진 트리를 세는 것으로 이 숫자들의 해석 측면에서, 반복의 합산은 이 잎들을 두 개의 부분집합으로 분할하고 각 부분집합을 잎으로 하는 부분트리를 형성하는 다른 방법을 세웁니다. 두 부분 트리에서 같은 수의 잎을 가진 나무를 이중으로 세는 것을 피하기 위해 n의 짝수 값에 대한 공식은 홀수 값에 대한 공식보다 약간 더 복잡합니다.^[7]

성장률

웨더번-에테르링턴 수는 다음과 같이 점근적으로 증가합니다.

${\displaystyle a_{n}\approx {\sqrt {\frac {\rho +\rho ^{2}B'(\rho ^{2})}{2\pi }}}{\frac {\rho ^{-n}}{n^{3/2}}},}$

여기서 B는 숫자의 생성 함수이고 ρ는 수렴 반경으로, 약 0.4027(OEIS에서 서열 A240943)이고, 제곱근에서의 표현식의 부분에 의해 주어진 상수는 약 0.3188(OEIS에서 서열 A245651)입니다.

적용들

Young & Young (2003)은 숨겨진 뒷문을 포함하는 암호화 시스템 설계의 일부로 Wedderburn-Etherington 숫자를 사용합니다. 그들의 시스템에 의해 암호화될 입력이 Huffman 코딩에 의해 충분히 압축될 수 있을 때, 그것은 주요 데이터를 공격자에게 유출하는 추가 정보와 함께 압축된 형태로 대체됩니다. 이 시스템에서 허프만 코딩 트리의 모양은 Other 트리로 설명되고 코드의 심볼 수에 대해 0부터 Wedderburn-Etherington 번호까지의 구간에서 이진수로 인코딩됩니다. 이러한 방식으로 인코딩은 매우 적은 수의 비트를 사용하는데, 이는 Wedderburn-Etherington 숫자의 밑-2 로그입니다.^[12]

Farzan & Munro(2008)는 트리를 작은 하위 트리로 분할하고 각 하위 트리를 크기에 대해 Wedderburn-Etherington 번호로 경계를 이루는 숫자로 인코딩하는 것을 기반으로 하는 근되지 않은 이진 트리에 대한 유사한 인코딩 기술을 설명합니다. 그들의 방식은 이러한 트리를 정보 이론적 하한(Wedderburn-Etherington number의 밑-2 로그)에 가까운 비트로 인코딩하는 동시에 트리 내에서 일정한 시간 탐색 작업을 허용합니다.^[13]

Iserles & Nørsett (1999)은 정렬되지 않은 이진 트리를 사용하며, 웨더번-에테르링턴 수가 정렬된 이진 트리를 세는 수보다 현저히 작다는 사실은 특정 미분 방정식에 대한 해의 직렬 표현에서 항의 수를 크게 줄입니다.^[14]

참고 항목

• 카탈루냐 수

참고문헌

더보기

• Finch, Steven R. (2003), Mathematical constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge: Cambridge University Press, pp. 295–316, doi:10.1017/CBO9780511550447, ISBN 978-0-521-81805-6, MR 2003519.