<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
Enumeration of Decomposable Combinatorial Structures with Restricted Patterns
Li Dong, Zhicheng Gao, and Daniel Panario
School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, Canada
{ldong, zgao, daniel}@math.carleton.ca
Annals of Combinatorics 12 (4) pp.353-368 December, 2008
AMS Subject Classification: 05A16, 05A15
Abstract:
Decomposable combinatorial structures are studied with restricted patterns. We focus on the decomposable structures in the $\exp$-$\log$ class. Using the method of analysis of singularities introduced by Flajolet and Odlyzko \cite{SIANGF}, we provide an estimate for the probability that a decomposable structure of size $n$ has a given restricted pattern. We exemplify with several decomposable structures like permutations and polynomials over finite fields.
Keywords: decomposable structures, restricted pattern, labeled and unlabeled structures, generating functions, $\exp$-$\log$ class

References:

1. R. Arratia, A.D. Barbour, and S. Tavar´e, Random combinatorial structures and prime factorizations, Notices Amer. Math. Soc. 44 (8) (1997) 903-–910.

2. M. Car, Th´eoremes de densit´e dans Fq[x], Acta Arith. 48 (1987) 145-–165.

3. L. Dong, Z. Gao, and D. Panario, The size of the rth smallest component in decomposable structures with a restricted pattern, In: 2007 Conference on Analysis of Algorithms, DMTCS Proc., Paris, (2007) pp. 365-–384.

4. P. Flajolet, X. Gourdon, and D. Panario, The complete analysis of a polynomial factorization algorithm over finite fields, J. Algorithms 40 (1) (2001) 37-–81.

5. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) (1990) 216-–240.

6. P. Flajolet, B. Salvy, and P. Zimmermann, Automatic average-case analysis of algorithms, Theoret. Comput. Sci. 79 (1) (1991) 37-–109.

7. P. Flajolet and R. Sedgewick, Analytic Combinatorics, to appear.

8. P. Flajolet and M. Soria, Gaussian limiting distribution for the number of components in combinatorial structures, J. Combin. Theory Ser. A 53 (2) (1990) 165-–182.

9. X. Gourdon, Largest component in random combinatorial structures, Discrete Math. 180 (1-3) (1998) 185-–209.

10. T. Garefalakis and D. Panario, The index calculus method using non-smooth polynomials, Math. Comp. 70 (235) (2001) 1253-–1264.

11. T. Garefalakis and D. Panario, Polynomials over nite elds free from large and small degree irreducible factors, J. Algorithms 44 (1) (2002) 98-–120.

12. V. Goncharov, Sur la distribution des cycles dans une permutations, Acad. Sci. URSS 35 (1942) 267-–269.

13. V. Goncharov, On the field of combinatorial analysis, Amer. Math. Soc. Transl. (2) 19 (1962) 1-–46.

14. P. Henrici, Applied and Computational Complex Analysis, Vol. 2, John Wiley, New York, 1974.

15. A. Knopfmacher and R. Warlimont, Distinct degree factorizations for polynomials over a finite eld, Trans. Amer. Math. Soc. 347 (6) (1995) 2235–-2243.

16. A. Knopfmacher and R. Warlimont, Counting permutations and polynomials with a restricted factorization pattern, Australas. J. Combin. 13 (1996) 151-–162.

17. A. Odlyzko, Discrete logarithms in nite elds and their cryptographic signicance, Lecture Notes in Comput. Sci. 209 (1985) 224-–314.

18. D. Panario and B. Richmond, Analysis of Ben-Or's polynomial irreducibility test, Random Structures Algorithms 13 (3-4) (1998) 439-–456.

19. D. Panario and B. Richmond, Smallest components in decomposable structures: exp-log class, Algorithmica 29 (1-2) (2001) 205–-226.

20. L.A. Shepp and S.P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 (1996) 340-–357.

21. E.T. Whittaker and G.N. Watson, A Course of Modern Analysis, 4th Ed., Cambridge University Press, Cambridge, 1996.

22. H. Wilf, Generatingfunctionology, A.K. Peters, Ltd., Wellesley, MA, 2006.