Enumeration of Non-Separable Planar Maps

Abstract

In (2), Tutte has shown that the number, B n , of rooted non-separable planar maps having n edges is [2(3n — 3)!]/[n! (2n — 1)!]. Rooting was accomplished by designating one edge as the root, orienting it, and distinguishing between its sides as left and right . We shall here compute the number, B n,m , of rooted non-separable planar maps having n edges and such that the face to the left of the root is incident with exactly m edges, which maps will be said to be of type [ n, m ].