나무의 수

나무에 대한 수학적 이론은 1857년 Cayley에 의해 처음 논의되었다(1). 그는 정점의 수가 유한한 나무 또는 뿌리 나무의 수를 세기 위한 재귀 공식을 찾아내는 데 성공했으며, 정점에서 가지의 수는 제한되지 않았다. Cayley는 또한 화학에서 이성질체 문제를 연구하는 가능성을 나무 개념을 활용하여 인식했지만, 이 문제의 해결을 위해서는 정점에서 발생할 수 있는 가지의 수에 대한 제한이 필요하다. 1931년 Henze와 Blair(2)는 정점의 수가 동일한 유한한 나무 또는 뿌리 나무의 수를 세기 위한 재귀 공식을 개발했으며, 정점에서 가지의 수는 루트 정점을 제외하고 최대 네 개까지 허용되었고, 루트 정점은 최대 세 개의 가지를 가질 수 있었다. 이것은 화학의 이성질체 문제에 대한 첫 번째 해답이었다. n개의 정점을 가진 그러한 나무의 수는 구조적 이성질체인 지방족 탄화수소의 수와 정확히 동일하다. 즉, 분자식 CnH2n+2의 화합물이다. n개의 정점을 가진 그러한 뿌리 나무의 수는 구조적 이성질체인 단일 치환 지방족 탄화수소의 수와 정확히 동일하다. 즉, 분자식 CnH2+1XX의 화합물이며, 여기서 X는 수소와 다른 화학적 유리기 또는 원자를 나타낸다. 1937년 그의 고전적인 출판물에서 G. Polya(3)는 주어진 치환 그룹 아래에서 특정 유형의 기하학적 구성의 대칭을 처리하기 위한 강력한 방법을 개발했다. 생성 함수로 사용되는 파워 시리즈의 계수는 이 치환 그룹에 대한 서로 다른 가능한 구성의 수를 나타낸다. 이러한 생성 함수에 대한 기능 방정식을 생성하는 방법이 개발되었다. 이러한 기능 방정식에는 계수를 결정하기 위한 재귀 공식이 함축되어 있으며, 그의 기능 방정식 분석은 계수에 대한 점근적 표현을 도출해 내었다. 특히, Polya는 화학자들에게 흥미로운 많은 문제를 연구하며 Henze와 Blair, Cayley의 재귀 공식을 얻었다. 그러나 그는 화학 이성질체와 관련된 다른 많은 문제도 해결했다. 비록 Polya는 그의 출판물에서 화학자에게 주된 관심을 두고 있는 나무와 뿌리 나무를 세는 데 제한하고 있지만, 그의 방법은 우리가 다룬 사례에서 나무와 뿌리 나무의 수를 계산하는 데 일반화될 수 있는 것을 분명히 한다. 그러나 그의 생성 함수 분석 방법이 점근적 값을 도출하기 위해 일반화될 수 있는지는 명확하지 않다. 그러나 그의 기계는 기하학적 구성의 대칭 문제에 대한 아주 일반적인 문제 해결에 강력하지만, 나무나 뿌리 나무의 처리에는 많은 부분이 불필요한 것으로 보인다.