<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
Enumeration of K-Trees and Applications
Mahendra Jani, Robert G. Rieper, and Melkamu Zeleke
Department of Mathematics, William Paterson University, Wayne, NJ 07470, USA
{janim, zelekem}@wpunj.edu
Annals of Combinatorics 6 (3) p.375-382 September, 2002
AMS Subject Classification: 05A15
A k-tree is constructed from a single distinguished k-cycle by repeatedly gluing other k-cycles to existing ones along an edge. If K is any nonempty subset of , then a K-tree is obtained as above using k-cycles with . In this paper, we enumerate ordered K trees, show that the ratio of terminal edges to total number of edges in k-trees is , and use the K-trees as models to enumerate planted plane cacti.
Keywords: K-trees, terminal edges, generating functions, generalized Catalan numbers, planted plane cacti


1. M. Bona, M. Bousquet, and G. Labelle, Enumeration of m-ary cacti, Adv. Appl. Math. 24 (2000) 22每56.

2. W.Y.C. Chen, A general bijective algorithm for trees, Proc. Natl. Acad. Sci. USA 87 (1990) 9635每9639.

3. R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.

4. F. Haray and G.E. Uhlenbeck, On the number of Husimi trees, Proc. Natl. Acad. Sci. USA 39 (1953) 315每322.

5. F. Harary and G. Palmer, Graph Enumeration, Academic Press, 1973.

6. I. Pak, Reduced decomposition of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees, Dicrete Math. 204 (1999) 329每335.

7. M. Petkovsek, H. Wilf, and D. Zeilberger, A=B, AK Peters, 1996.

8. R.G. Rieper and M. Zeleke, Skew diagrams and ordered trees, Adv. Appl. Math. 27 (2001) 671每681.

9. W.R. Schmitt and M. S.Waterman, Linear trees and RNA secondary structures, Dicrete Appl. Math. 51 (1994) 317每323.

10. L.W. Shapiro, Problem #10753, Amer. Math. Monthly 106 (1999) 777.

11. L.W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976) 83每70.

12. L.W. Shapiro, The higher you go, the odder it gets, Congr. Numer. 138 (1999) 93每96.

13. R.P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

14. D. Stanton and D. White, Constructive Combinatorics, Springer-Verlag, 1986.

15. H.S.Wilf, Generatingfunctionology, Academic Press, 1994.

16. D. Zeilberger, EKHAD-Maple Package, http://math.temple.edu.