Hostname: page-component-76fb5796d-dfsvx Total loading time: 0 Render date: 2024-04-26T12:46:32.341Z Has data issue: false hasContentIssue false
  • English
  • Français

Diagonal Asymptotics for Products of Combinatorial Classes

Published online by Cambridge University Press:  10 October 2014

MARK C. WILSON
MARK C. WILSON*
Affiliation:
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand (e-mail: mcw@cs.auckland.ac.nz)
Get access Rights & Permissions [Opens in a new window]

Abstract

We generalize and improve recent results by Bóna and Knopfmacher and by Banderier and Hitcz-enko concerning the joint distribution of the sum and number of parts in tuples of restricted compositions. Specifically, we generalize the problem to general combinatorial classes and relax the requirement that the sizes of the compositions be equal. We extend the main explicit results to enumeration problems whose counting sequences are Riordan arrays. In this framework, we give an alternative method for computing asymptotics in the supercritical case, which avoids explicit diagonal extraction.

Keywords

Primary 05A15Secondary 05A16
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 1: Honouring the Memory of Philippe Flajolet - Part 3 , January 2015 , pp. 354 - 372
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Banderier, C. and Flajolet, P. (2002) Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci. 281 37–80.Google Scholar
[2] Banderier, C. and Hitczenko, P. (2012) Enumeration and asymptotics of restricted compositions having the same number of parts. Discrete Appl. Math. 160 2542–2554.Google Scholar
[3] Bóna, M. and Flajolet, P. (2009) Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab. 46 1005–1019.Google Scholar
[4] Bóna, M. and Knopfmacher, A. (2010) On the probability that certain compositions have the same number of parts. Ann. Combin. 14 291–306.Google Scholar
[5] Bostan, A., Lairez, P. and Salvy, B. (2013) Creative telescoping for rational functions using the Griffiths–Dwork method. In ISSAC (Monagna, M. B., Cooperman, G. and Giesbrecht, M., eds), ACM, pp. 93–100.Google Scholar
[6] Fill, J. A., Flajolet, P. and Kapur, N. (2005) Singularity analysis, Hadamard products, and tree recurrences. J. Comput. Appl. Math. 174 271–313.Google Scholar
[7] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[8] Flaxman, A., Harrow, A. W. and Sorkin, G. B. (2004) Strings with maximally many distinct subsequences and substrings. Electron. J. Combin. 11 R8.Google Scholar
[9] Labelle, J. and Yeh, Y. N. (1990) Generalized Dyck paths. Discrete Math. 82 1–6.Google Scholar
[10] Merlini, D., Rogers, D. G., Sprugnoli, R. and Verri, M. C. (1997) On some alternative characterizations of Riordan arrays. Canad. J. Math. 49 301–320.Google Scholar
[11] Noble, R. (2010) Asymptotics of a family of binomial sums. J. Number Theory 130 2561–2585.Google Scholar
[12] OEIS Foundation (2013) On-Line Encyclopedia of Integer Sequences. http://oeis.org Google Scholar
[13] Pemantle, R. and Wilson, M. C. (2002) Asymptotics of multivariate sequences I: Smooth points of the singular variety. J. Combin. Theory, Ser. A 97 129–161.Google Scholar
[14] Pemantle, R. and Wilson, M. C. (2008) Twenty combinatorial examples of asymptotics derived from multivariate generating functions. SIAM Rev. 50 199–272.Google Scholar
[15] Pemantle, R. and Wilson, M. C. (2013) Analytic Combinatorics in Several Variables, Cambridge University Press.Google Scholar
[16] Raichev, A. (2013) amgf-0.8. http://www.alexraichev.org/research.html Google Scholar
[17] Raichev, A. and Wilson, M. C. (2007) A new method for computing asymptotics of diagonal coefficients of multivariate generating functions. In 2007 Conference on Analysis of Algorithms: AofA 07, DMTCS Proc. AH, pp. 439–449.Google Scholar
[18] Raichev, A. and Wilson, M. C. (2008) Asymptotics of coefficients of multivariate generating functions: Improvements for smooth points. Electron. J. Combin. 15 R89.Google Scholar
[19] Shapiro, L. W., Getu, S., Woan, W. J. and Woodson, L. C. (1991) The Riordan group. Discrete Appl. Math. 34 229–239.Google Scholar
[20] Singer, N., Shouldice, A., Ye, L., Daske, T., Dobcsanyi, P., Manna, D., Chan, O.-Y. and Borwein, J. (2013) Inverse Symbolic Calculator. http://isc2.carma.newcastle.edu.au/advancedCalc Google Scholar
[21] Wilson, M. C. (2005) Asymptotics for generalized Riordan arrays. In 2005 International Conference on Analysis of Algorithms, DMTCS Proc. AD, pp. 323–333.Google Scholar