Hostname: page-component-7b7567c8c-2jgqx Total loading time: 0 Render date: 2026-11-19T13:54:48.149Z Has data issue: false hasContentIssue false

Sequence Enumeration and the de Bruijn-Van Aardenne Ehrenfest-Smith-Tutte Theorem

Published online by Cambridge University Press:  20 November 2018

D. M. Jackson
Affiliation:
University of Waterloo, Waterloo, Ontario
I. P. Goulden
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The de Bruijn—van Aardenne Ehrenfest— Smith—Tutte theorem [1] is a theorem which connects the number of Eulerian dicircuits in a directed graph with the number of rooted spanning arborescences. In this paper we obtain a proof of this theorem by considering sequences over a finite alphabet, and we show that the theorem emerges from the generating function for a certain type of sequence. The generating function for the set of sequences is obtained as the solution of a linear system of equations in Section 2. The power series expansion for the solution of this system is obtained by means of the multivariate form of the Lagrange theorem for implicit functions, and is given in Section 3, together with a restatement of the theorem as a matrix identity.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1979