Chords, trees and permutations

DOI10.1016/0012-365X(93)90326-OMaRDI QIDQ686151zbMATH OpenOpenAlexFDO

Authors J.-G. Penaud, Serge Dulucq

Publication date 11 January 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90326-o

zbMATH Keywords

binary trees Catalan numbers chord configuration cyclic permutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05)

Review text

The present authors considered chord configurations on the circle and their relation with involutions, binary trees, and the decomposition of a cyclic permutation, represented as a product of transpositions. That latter case leads the authors to a new recurrence formula for the Catalan numbers. Reviewer's remark: The reviewer proved in his first paper [Publ. Math. Inst. Hung. Acad. Sci. 4, 63-70 (1959; Zbl 0092.011)] that the number of labelled trees with \(n\) vertices \((n^{n-2})\) is equal to the number of different representations of a cycle of length \(n\) as a product of \(n-1\) transpositions. The reviewer could not obtain a one to one correspondence between a given tree and a product of transpositions. He posed the problem to find such a one to one correspondence in his paper mentioned above. \textit{P. Moszkowski} solved the reviewer's problem, see [Eur. J. Comb. 10, No. 1, 13-16 (1989; Zbl 0672.05022)]. The authors of the present paper refer to Moszkowski's paper (see reference [16] in the present paper) as one to be published. Actually it had been published, when the present authors submitted their paper in 1990.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Chords, trees and permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686151)