Asymptotic expansion of a sequence related to the number e and its application in analytical counting of number of paths in full graph

Document Type : Research Paper

Author

Department of Mathematics, University of Zanjan, University Blvd., Zanjan, Iran

Abstract

In this paper we study the number of distinct paths between any pair of vertices in the complete graph $K_{n+2}$. First we show that the number of these paths is $w_{n+2}=e_n n!$, where $e_n=\sum_{j=0}^n 1/j!$ is the partial sum of the series representing the number $e$. Then we obtain an integral representation, similar to the integral representation of the Gamma function, for $e_n$. By using this representation we get an asymptotic expansion for $w_{n+2}$ as follows
\[
w_{n+2}=en!-\sum_{k=1}^r\frac{c_k}{n^k}+O\left(\frac{1}{n^{r+1}}\right),
\]
where $r\geq 1$ is any fixed integer and the constants $c_k$ are computable. Moreover, we show that the constant of $O$-term does not exceed $e^2B_{r+1}$, where $B_{r+1}$ denotes the $r+1$-th Bell number. \\
\textbf{Keywords:} complete graph, the number e, analytic enumeration, asymptotic expansion, bell numbers.

Keywords

References

[1] M. Aigner, A course in enumeration, Graduate Texts in Mathematics, 238, Springer, Berlin, 2007.
[2] E. A. Bender, Asymptotic methods in enumeration, SIAM Rev., 16 (1974) 485–515.
[3] L. Comtet, Advanced combinatorics: the art of finite and infinite expansions, Dordrecht, Netherlands, Reidel, 1974.
[4] N. G. De Bruijn, Asymptotic methods in analysis, North-Holland Publishing Co., Amsterdam, 1961.
[5] P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, 2009.
[6] I. S. Gradshteyn and I. M. Ryzhik, Table of Integrals, Series, and Products, 7th Edition, Academic Press, 2007.
[7] M. Hassani, Cycles in graphs and derangements, Math. Gaz., 88 (2004) 123–126.
[8] M. Hassani, Derangements and alternating sum of permutations by integration, J. Integer Sequences, 23 (2020) Article 20.7.8.
[9] M. Hassani, Enumeration by e, in T. M. Rassias and N. J. Daras, eds., Modern discrete mathematics and analysis: with applications in cryptography, information systems and modelling, Springer, 2018 227–233.
[10] M. Hassani, On a difference concerning the number e and summation identities of permutations, J. Inequal. Spec. Funct.,12 (2021) 14–22.
[11] L. Lovász, Combinatorial problems and exercises, 2nd ed., Amsterdam, Netherlands, North-Holland, 1993.
[12] A. M. Odlyzko, Asymptotic enumeration methods, in Handbook of combinatorics, 1, 2, Elsevier, Amsterdam, 1995 1063–1229.
[13] F. W. J. Olver, D. W. Lozier, R. F. Boisvert and C. W. Clark (editors), NIST Handbook of Mathematical Functions, Cambridge University Press, 2010.
[14] K. H. Rosen, J. G. Michaels, J. L. Gross, J. W. Grossman and D. R. Shier, Handbook of discrete and combinatorial mathematics, CRC Press, 2000.
[15] M. Z. Spivey, The art of proving binomial identities, CRC Press, 2019.
[16] E. C. Titchmarsh, The theory of functions, 2nd ed., Oxford University Press, 1975.
[17] E. W. Weisstein, CRC Concise encyclopedia of mathematics, 2nd ed., CRC Press, 2003.
[18] م. حسنی، ع. احمدی، جای خالی عدد نپر در کتاب‌های متوسّطه، ریاضی و جامعه، 1 (1393) 13--23.
Mathematics and Society
Volume 6, Issue 3 - Serial Number 3
September 2021
Pages 19-24

Files

History

  • Receive Date: 06 September 2021
  • Revise Date: 17 February 2022
  • Accept Date: 28 February 2022
  • Publish Date: 22 November 2021

Share

How to cite

Statistics