Geodesic
The Application of Lagrangian Methods to the Enumeration of Labelled Trees with Respect to Edge Partition
Canadian journal of mathematics, Tome 34 (1982) no. 3, pp. 513-518

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

In an earlier paper [6] we considered the application of Lagrangian methods to the enumeration of plane rooted trees with given colour partition. We obtained an expression which generalised Tutte’s result [9], and a correspondence, which, when specialised, gives the de Bruijn-van Aardenne Ehrenfest-Smith-Tutte Theorem [1]. A corollary of these results is a one-to-one correspondence [4], between trees and generalised derangements, for which no combinatorial description has yet been found.In this paper we extend these methods to the enumeration of rooted labelled trees to demonstrate how another pair of well-known and apparently unrelated theorems may be obtained as the result of a single enumerative approach. In particular, we show that a generalisation of Good's result [3], also considered by Knuth [7], and the matrix tree theorem [8] have a common origin in a single system of functional equations, and that they correspond to different coefficients in the power series solution. 
Goulden, I. P.; Jackson, D. M. The Application of Lagrangian Methods to the Enumeration of Labelled Trees with Respect to Edge Partition. Canadian journal of mathematics, Tome 34 (1982) no. 3, pp. 513-518. doi: 10.4153/CJM-1982-035-0
@article{10_4153_CJM_1982_035_0,
     author = {Goulden, I. P. and Jackson, D. M.},
     title = {The {Application} of {Lagrangian} {Methods} to the {Enumeration} of {Labelled} {Trees} with {Respect} to {Edge} {Partition}},
     journal = {Canadian journal of mathematics},
     pages = {513--518},
     year = {1982},
     volume = {34},
     number = {3},
     doi = {10.4153/CJM-1982-035-0},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-035-0/}
}
TY  - JOUR
AU  - Goulden, I. P.
AU  - Jackson, D. M.
TI  - The Application of Lagrangian Methods to the Enumeration of Labelled Trees with Respect to Edge Partition
JO  - Canadian journal of mathematics
PY  - 1982
SP  - 513
EP  - 518
VL  - 34
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-035-0/
DO  - 10.4153/CJM-1982-035-0
ID  - 10_4153_CJM_1982_035_0
ER  - 
%0 Journal Article
%A Goulden, I. P.
%A Jackson, D. M.
%T The Application of Lagrangian Methods to the Enumeration of Labelled Trees with Respect to Edge Partition
%J Canadian journal of mathematics
%D 1982
%P 513-518
%V 34
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1982-035-0/
%R 10.4153/CJM-1982-035-0
%F 10_4153_CJM_1982_035_0

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

[2] 2. Good, I. J., Generalizations to several variables of Lagrange1 s expansion, with applications to stochastic processes, Proc. Cambridge Philos. Soc. 56 (1960), 367–380. Google Scholar

[3] 3. Good, I. J., The generalization of Lagrange's expansion and the enumeration of trees, Proc. Cambridge Philos. Soc. 61 (1965), 499–517. Google Scholar

[4] 4. Goulden, I. P. and Jackson, D. M., A correspondence between plane rooted chromatic trees and generalised derangements, Bull. London Math. Soc. 13 (1981), 28–32. Google Scholar

[5] 5. Goulden, I. P. and Jackson, D. M., The enumeration of directed closed Euler trails and directed Hamiltonian circuits by Lagrangian methods, European J. Combinatorics 2 (1981), 131–135. Google Scholar

[6] 6. Goulden, I. P. and Jackson, D. M., The generalisation of Tutte's result for chromatic trees, by Lagrangian methods, Can. J. Math. 33 (1981), 12–19. Google Scholar

[7] 7. Knuth, D. E., Another enumeration of trees, Can. J. Math. 20 (1968), 1077–1086. Google Scholar

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

[9] 9. Tutte, W. T., The number of planted plane trees with a given partition, Amer. Math. Monthly 71 (1964), 272–277. Google Scholar

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

Cité par Sources :