Geodesic
Sequence Enumeration and the de Bruijn-Van Aardenne Ehrenfest-Smith-Tutte Theorem
Canadian journal of mathematics, Tome 31 (1979) no. 3, pp. 488-495

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
Jackson, D. M.; Goulden, I. P. Sequence Enumeration and the de Bruijn-Van Aardenne Ehrenfest-Smith-Tutte Theorem. Canadian journal of mathematics, Tome 31 (1979) no. 3, pp. 488-495. doi: 10.4153/CJM-1979-054-x
@article{10_4153_CJM_1979_054_x,
     author = {Jackson, D. M. and Goulden, I. P.},
     title = {Sequence {Enumeration} and the de {Bruijn-Van} {Aardenne} {Ehrenfest-Smith-Tutte} {Theorem}},
     journal = {Canadian journal of mathematics},
     pages = {488--495},
     year = {1979},
     volume = {31},
     number = {3},
     doi = {10.4153/CJM-1979-054-x},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1979-054-x/}
}
TY  - JOUR
AU  - Jackson, D. M.
AU  - Goulden, I. P.
TI  - Sequence Enumeration and the de Bruijn-Van Aardenne Ehrenfest-Smith-Tutte Theorem
JO  - Canadian journal of mathematics
PY  - 1979
SP  - 488
EP  - 495
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1979-054-x/
DO  - 10.4153/CJM-1979-054-x
ID  - 10_4153_CJM_1979_054_x
ER  - 
%0 Journal Article
%A Jackson, D. M.
%A Goulden, I. P.
%T Sequence Enumeration and the de Bruijn-Van Aardenne Ehrenfest-Smith-Tutte Theorem
%J Canadian journal of mathematics
%D 1979
%P 488-495
%V 31
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1979-054-x/
%R 10.4153/CJM-1979-054-x
%F 10_4153_CJM_1979_054_x

[1] 1. van Aardenne-Ehrenfest, T. and de Bruijn, N. G., Circuits and trees in oriented linear graphs, Simon Stevin. 28 (1951), 203–217. Google Scholar

[2] 2. Brooks, R. L., Smith, C. A. B., Stone, A. H. and Tutte, W. T., The dissection of rectangles into squares, Duke Math. J. 7 (1940), 312–340. Google Scholar

[3] 3. Cartier, P. and Foata, D., Problèmes comminatoires de commutation et réarrangements, Lecture Notes in Mathematics, Vol. 85 (Springer-Verlag, Berlin, 1969). Google Scholar

[4] 4. Dawson, R. and Good, I. J., Exact Markov probabilities from oriented linear graphs, Ann. Math. Stat. 28 (1957), 946–956. Google Scholar

[5] 5. Good, I. J., Generalizations to several variables of La granges’ expansion with applications to stochastic processes, Proc. Cambridge Phil. Soc. 56 (1960), 367–380. Google Scholar

[6] 6. Good, I. J., A short proof of MacMahon s “master theorem”, Proc. Cambridge Phil. SoC. 58 (1962), 160. Google Scholar

[7] 7. Good, I. J., The generalisation of Lagrange's expansion and the enumeration of trees Proc. Cambridge Phil. Soc. 61 (1965), 499–517. (Correction: Proc. Cambridge Phil. Soc. 61 (1968), 489.) Google Scholar

[8] 8. Hutchinson, J. P. and Wilf, H. S., On Eulerian circuits and words with prescribed adjacency patterns, J. Combinatorial Theory (A). 18 (1975), 80–87. Google Scholar

[9] 9. Jackson, D. M., The unification of certain enumeration problems for sequences, J. Combinatorial Theory (A). 22 (1977), 92–96. Google Scholar

[10] 10. Jacksqn, D. M. and Aleliunas, R., Decomposition based generating functions for sequences, Can. J. Math. 29 (1977), 971–1009. Google Scholar

[11] 11. MacMahon, P. A., Combinatory analysis, Vol. 1 (Chelsea, New York, 1960). Google Scholar

[12] 12. Marcus, M., Inequalities for matrix functions of combinatorial interest, S.I.A.M.J. Appl. Math. 17 (1969), 1023–1031. Google Scholar

[13] 13. Tutte, W. T., The dissection of equilateral triangles into equilateral triangles, Proc. Cambridge Phil. Soc. 44 (1948), 463–482. Google Scholar

[14] 14. Tutte, W. T., Qn elementary calculus and the Good formula, J. Combinatorial Theory, (B). 18 (1975), 97–137. Google Scholar

[15] 15. Vrba, A., An inversion formula, matrix functions, combinatorial identities and graphs, Casopis pro pëstovâni matematiky. 98 (1973), 292–297. Google Scholar

Cité par Sources :