Approximating the Level Curves on Pascal’s Surface
DOI:
https://doi.org/10.15837/ijccc.2022.4.4865Abstract
It is well-known that in general the algorithms for determining the reliability polynomial associated to a two-terminal network are computationally demanding, and even just bounding the coefficients can be taxing. Obviously, reliability polynomials can be expressed in Bernstein form, hence all the coefficients of such polynomials are fractions of the binomial coefficients. That is why we have very recently envisaged using an extension of the classical discrete Pascal’s triangle (which comprises all the binomial coefficients) to a continuous version/surface. The fact that this continuous Pascal’s surface has real values in between the binomial coefficients makes it appealing as being a mathematical concept encompassing all the coefficients of all the reliability polynomials (which are integers, as resulting from counting processes) and more. This means that, the coefficients of any reliability polynomial can be represented as discrete steps (on level curves of integer values) on Pascal’s surface. The equation of this surface was formulated by means of the gamma function, for which quite a few approximation formulas are known. Therefore, we have started by reviewing many of those results, and have used a selection of those approximations for the level curves problem on Pascal’s surface. Towards the end, we present fresh simulations supporting the claim that some of these could be quite useful, as being both (reasonably) easy to calculate as well as fairly accurate.
References
Abramowitz, M.; Stegun, I.A. (eds.) (1972). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (10th printing), National Bureau of Standards, Appl. Math. Series 55, 1972.
Allen, L.; Kirby, R.C. (2021). Bounds-constrained polynomial approximation using the Bernstein basis, Tech. Rep. arXiv:2104.11819, Numerical Analysis (math.NA), 1-26, 2021. https://arxiv.org/abs/2104.11819, Accessed on 06 June 2022.
Apianus, P. (1527). Eyn newe vnnd wolgegründte underweysung aller Kauffmannß Rechnung in dreyen Büchern, Ingolstadt, 1527. https://doi.org/10.3931/e-rara-8953, Accessed on 06 June 2022.
Babbage, C. (1834). Babbage's calculating engine, Edinburgh Review, 59(120), 263-327, 1834. Available: https://en.wikisource.org/w/index.php?title=Edinburgh_Review/Volume_59/ Babbage% 27s_Calculating_Engine&oldid=5473361, Accessed on 06 June 2022.
Beiu, V.; Daus, L. (2015). Reliability bounds for two dimensional consecutive systems, Nano Comm. Nets., 6(3), 145-152, 2015.
https://doi.org/10.1016/j.nancom.2015.04.003
Beiu, V.; Dragoi, V.-F.; Beiu, R.-M. (2020). Why reliability for computing needs rethinking, In Proc. Conf. Rebooting Comp. (ICRC2020), IEEE, 16-25, 2020.
https://doi.org/10.1109/ICRC2020.2020.00006
Beiu, V.; Daus, L.; Jianu, M.; Mihai, A.; Mihai, I. (2022). On a surface associated with Pascal's triangle, Symmetry, 14, art. 411 (1-12), 2022.
https://doi.org/10.3390/sym14020411
Beiu, V. (2022). The unfolding road from dust to trust, In Proc. Intl. Conf. Adv. 3OM (Adv3OM 2021), Timisoara, Romania, 13-16 Dec. 2021, SPIE, art. 1217007 (1-7), 2022.
Bernstein, S.N. (1912/13). Démonstration du théorème de Weierstrass fondée sur le calcul des probabilities [Proof of the theorem of Weierstrass based on the calculus of probabilities], Comm. Kharkov Math. Soc., 13, 1-2, 1912/13.
Bondarenko, B.A. (1990). Generalized Pascal Triangles and Pyramids-Their Fractals, Graphs, and Applications, Izdatel'stvo "FAN" RUz, Tashkent, 1990. Translated by R.C. Bollinger (1993). https://www.fq.math.ca/pascal.html, Accessed on 06 June 2022.
Brent, R.P. (2021). Asymptotic approximation of central binomial coefficients with rigorous error bounds, Open J. Math. Sci., 5(1), 380-386, 2021.
https://doi.org/10.30538/oms2021.0173
Brown, J.I.; Colbourn, C.J.; Cox, D.; Graves, C.; Mol, L. (2021). Network reliability: Heading out on the highway, Networks (Sp. Iss. 50 Years), 77(1), 146-160, 2021.
https://doi.org/10.1002/net.21977
Burnside, W. (1917). A rapidly converging series for logN!, Messenger Math., 46, 157-159, 1917. https://archive.org/details/messengerofmathe46cambuoft/page/157/mode/2up, Accessed on 06 June 2022.
Busard, H.L.L. (ed.) (1991). Jordanus de Nemore. De elementis arithmetice artis. A Medieval Treatise on Number Theory, Franz Steiner, Stuttgart, 1991. See p. 80 from the handwritten original https://gallica.bnf.fr/ark:/12148/btv1b10034347w, Accessed on 06 June 2022.
Cardano, G. (1570). Opus Novum de Proportionibus, . . . , Henric Petri, Basel, 1570. See p. 185 in https://www.digitale-sammlungen.de/de/view/bsb10147886, Accessed on 06 June 2022.
Causley, M.F. (2022). The gamma function via interpolation, Numer. Algo., 90(2), 687-707, 2022.
https://doi.org/10.1007/s11075-021-01204-8
Chari, M.; Colbourn, C.J. (1997). Reliability polynomials: A survey, J. Comb. Info. Syst. Sci., 22(3/4), 177-193, 1997.
Chen, C.-P. (2016). A more accurate approximation for the gamma function, J. Number Th., 164, 417-428, 2016.
https://doi.org/10.1016/j.jnt.2015.11.007
Cobeli, C.; Zaharescu, A. (2013). Promenade around Pascal triangle-Number motives, Bull. Math. Soc. Sci. Math. Roumanie, 56(104)1, 73-98, 2013.
Cohen, L.Z.; Kim, I.H.; Bartlett, S.D.; Brown, B.J. (2022). Low-overhead fault-tolerant quantum computing using long-range connectivity, Sci. Adv., 8(20), art. eabn1717 (1-12), 2022.
https://doi.org/10.1126/sciadv.abn1717
Colbourn, C.J. (1987). The Combinatorics of Network Reliability, Oxford Univ. Press, 1987.
Cowell, S.R.; Beiu, V.; Daus, L.; Poulin, P. (2018). On the exact reliability enhancements of small hammock networks, IEEE Access, 6, 25411-25426, 2018.
https://doi.org/10.1109/ACCESS.2018.2828036
Daus, L.; Beiu, V. (2015). Lower and upper reliability bounds for consecutive-k-out-of-n:F systems, IEEE Trans. Rel., 64(3), 1128-1135, 2015.
https://doi.org/10.1109/TR.2015.2417527
Daus, L.; Jianu, M. (2020). Full Hermite interpolation of the reliability of a hammock network, Appl. Anal. Discr. Math., 14(1), 198-220, 2020.
https://doi.org/10.2298/AADM190805017D
Daus, L.; Jianu, M. (2021). The shape of the reliability polynomial of a hammock network, In Proc. Intl. Conf. Comp. Comm. & Ctrl. (ICCCC2020), 93-105, Springer AISC vol. 1243 (2021).
https://doi.org/10.1007/978-3-030-53651-0_8
de Moivre, A. (1730). Miscellanea Analytica de Seriebus et Quadraturis (incl. Miscellaneis Analyticus Supplementum), J. Tonson & J. Watts, London, 1730.
Dixit, H.D.; Pendharkar, S.; Beadon, M.; Mason, C.; Chakravarthy, T.; Muthiah, B.; Sankar, S. (2021). Silent data corruptions at scale, Tech. Rep. arXiv:2102.11245, Hardware Architecture (cs.AR), 1-8, 2021. Available: https://arxiv.org/abs/2102.11245, Accessed on 06 June 2022.
do Carmo, M. (1976). Differential Geometry of Curves and Surfaces, Prentice-Hall, 1976.
Dragoi, V.-F.; Beiu, V. (2022). Fast reliability ranking of matchstick minimal networks, Networks, 79(4), 479-500, 2022.
https://doi.org/10.1002/net.22064
Dutka, J. (1991). The early history of the factorial function, Arch. Hist. Exact Sci., 43(3), 225- 249, 1991.
https://doi.org/10.1007/BF00389433
Farina, A.; Giompapa, S.; Graziano, A.; Liburdi, A.; Ravanelli, M.; Zirilli, F. (2013). Tartaglia- Pascal's triangle: A historical perspective with applications, Sign. Imag. Video Proc., 7(1), 173- 188, 2013.
https://doi.org/10.1007/s11760-011-0228-6
Formichella, S.; Straub, A. (2019). Gaussian binomial coefficients with negative arguments, Ann. Comb., 23(52), 725-748, 2019.
https://doi.org/10.1007/s00026-019-00472-5
Fowler, D. (1996). The binomial coefficient function, Amer. Math. Month., 103(1), 1-17, 1996.
https://doi.org/10.1080/00029890.1996.12004694
Fowler, D. (1996). A simple approach to the factorial function, Math. Gazette, 80(488), 378-381, 1996.
https://doi.org/10.2307/3619582
Fowler, D. (1999). A simple approach to the factorial function-The next step, Math. Gazette, 83(496), 53-57, 1999.
https://doi.org/10.2307/3618683
Gélinas, J. (2017). Original proofs of Stirling's series for log(n! ), Tech. Rep. arXiv: 1701.06689, History and Overview (math.HO), 1-9, 2017. https://arxiv.org/abs/1701.06689, Accessed on 06 June 2022.
Gosper, R.W. (1978). Decision procedure for indefinite hypergeometric summation, Proc. Nat. Acad. Sci. USA, 7(1), 40-42 (1978).
https://doi.org/10.1073/pnas.75.1.40
Gross, J.L. (2007). Combinatorial Methods with Computer Applications, Chapman & Hall, 2007. http://www.cs.columbia.edu/˜cs4205/files/CM4.pdf, Accessed on 06 June 2022.
Gubner, J.A. (2021). The gamma function and Stirling's formula, Tech. Note, 2021. https://gubner.ece.wisc.edu/notes/GammaFunctionStirling.pdf, Accessed on 06 June 2022.
Hirschhorn, M.D.; Villarino, M.B. (2014). A refinement of Ramanujan's factorial approximation, Ramanujan J., 34(1), 73-81, 2014.
https://doi.org/10.1007/s11139-013-9494-y
Hochschild, P.H.; Turner, P.; Mogul, J.C.; Govindaraju, R.; Ranganathan, P.; Culler, D.E.; Vahdat, A.M. (2021). Cores that don't count, In Proc. Workshop Hot Topics Operating Syst. (HotOS'21), ACM Press, 9-16, 2021.
https://doi.org/10.1145/3458336.3465297
IBM (2021). IBM Quantum breaks the 100-qubit processor barrier. Available: https://research.ibm.com/blog/127-qubit-quantum-processor-eagle, Accessed on 09 June 2022.
International Roadmap for Devices and Systems (IRDSTM), IEEE, 2021. Available: https://irds.ieee.org/editions/2021, Accessed on 06 June 2022.
Jianu, M.; Ciuiu, D.; Daus, L.; Jianu, M. (2022). Markov chain method for computing the reliability of hammock networks, Prob. Eng. & Info. Sci., 36(2), 276-293, 2022.
https://doi.org/10.1017/S0269964820000534
Johansson, F. (2021). Arbitrary-precision computation of the gamma function, HAL preprint, 2021. https://hal.inria.fr/hal-03346642, Accessed on 06 June 2022.
Kessler, D.A.; Schiff, J. (2021). The asymptotics of factorials, binomial coefficients and Catalan numbers, J. Integr. Seq., 24(8), art. 21.8.3 (1-15), 2021.
Lampret, V. (2006). Estimating the sequence of real binomial coefficients, J. Inequal. Pure Appl. Math., 7(5), art. 166 (1-16), 2006.
Lanier, D.; Trotoux, D. (1996). La formule de Stirling. XI-ième Colloque Inter-IREM d'Histoire des Mathématiques, Reims, Fance, 1-41, May 1996. French translation of pp. 102-105, 124- 128, 170-172 from Miscellaneis Analyticus Supplementum [37], and pp. 135-137 from Methodus DifferentialisSive Tractatus de Summatione et Interpolatione Serierum Infinitarum, Prop. XXVIII [40] http://cm2.ens.fr/content/la-formule-de-stirling-1609, Accessed on 06 June 2022.
Lawrencenko, S.A.; Magomedov, A.M.; Zgonnik, L.V. (2018). Problems with parameters and binomial identities (in Russian), Math. Sch., 6(1), 16-26, 2018.
Mascioni, V. (2012). An inequality for the binary entropy function and an application to binomial coefficients, J. Math. Inequal., 6(3), 501-507, 2012.
https://doi.org/10.7153/jmi-06-47
Mersenne, M. (1636). Harmonie Universelle, Sebastien Cramoisy, Paris, 1636. See Book 2 "Des Chants," p. 145 in https://gallica.bnf.fr/ark:/12148/bpt6k5471093v, Accessed on 06 June 2022.
Mersenne, M. (1636). Harmonicorum Libri, Guillielmi Baudry, Paris, 1636. See XII https://gallica.bnf.fr/ark:/12148/bpt6k63326258.r, Accessed on 06 June 2022.
Michel, R. (2008). The (n+1)th proof of Stirling's formula, Amer. Math. Month., 115(9), 844-845, 2008.
https://doi.org/10.1080/00029890.2008.11920599
Moore, E.F.; Shannon, C.E. (1956). Reliable circuits using less reliable relays-Part I, J. Frankl. Inst., 26(3), 191-208, 1956.
https://doi.org/10.1016/0016-0032(56)90044-8
Moore, E.F.; Shannon, C.E. (1956). Reliable circuits using less reliable relays-Part II, J. Frankl. Inst., 262(4), 281-297, 1956.
https://doi.org/10.1016/0016-0032(56)90044-8
Morris, S.A. (2022). Tweaking Ramanujan's approximation of n!, Fundam. J. Maths. Appls., 5(1), 10-15, 2022.
Mortici, C. (2011). A substantial improvement of the Stirling formula, Appl. Maths. Lett., 24(8), 1351-1354, 2011.
https://doi.org/10.1016/j.aml.2011.03.008
Namias, V. (1986). A simple derivation of Stirling's asymptotic series, Amer. Math. Month., 93(1), 25-29, 1986.
https://doi.org/10.1080/00029890.1986.11971738
Nemes, G. (2010). New asymptotic expansion for the gamma function, Arch. Math., 95(2), 161- 169, 2010.
https://doi.org/10.1007/s00013-010-0146-9
Northshield, S. (2011). Integrating across Pascal's triangle, J. Math. Anal. Appl., 374(2), 385-393, 2011.
https://doi.org/10.1016/j.jmaa.2010.09.018
Pascal, B. (1665). Traité du Triangle Arithmétique, Guillaume Desprez, Paris, 1665. https://gallica.bnf.fr/ark:/12148/btv1b86262012/f1.image, Accessed on 06 June 2022.
Pearson, K. (1924). Historical note on the origin of the normal curve of errors, Biometrika, 16(3/4), 402-404, 1924. [Mentions that the second Supplementum, entitled Approximatio ad summam terminorium binomii (a + b)n in seriem expansi, is dated 12 Nov. 1733.]
https://doi.org/10.1093/biomet/16.3-4.402
Pellicer, R.; Alvo, A. (2012). Modified Pascal triangle and Pascal surfaces. Tech. Rep. academia.edu, art. 956605, 2012. Available: http://www.academia.edu/956605/, Accessed on 06 June 2022.
Pérez-Rosés, H. (2018). Sixty years of network reliability, Maths. Comp. Sci., 12(3), 275-293, 2018.
https://doi.org/10.1007/s11786-018-0345-5
Radford, D.E. (2021). Factorials and powers, a minimality result, Tech. Rep. arXiv:2106.02002, Number Theory (math.NT), 1-22, 2021. https://arxiv.org/abs/2106.02002, Accessed on 06 June 2022
Ramanujan, S. (1920). Notes, 1920. https://www.imsc.res.in/˜rao/ramanujan/notebookindex.htm, Accessed on 06 June 2022.
Ramanujan, S. (1988). The Lost Notebook and Other Unpublished Papers, Narosa Publ. H. & Springer, 1988.
Robbins, H. (1955). A remark on Stirling's formula, Amer. Math. Month., 62(1), 26-29 (1955).
https://doi.org/10.2307/2308012
Salwinski, D. (2018). The continuous binomial coefficient: An elementary approach, Amer. Math. Month., 125(3), 231-244, 2018.
https://doi.org/10.1080/00029890.2017.1409570
Smith, S.T. (2020). The binomial coefficient C(n, x) for arbitrary x, Online J. Anal. Comb., 15, art. 176 (1-12), 2020.
Smith, W.D. (2006). The gamma function revisited, 29 Mar. 2006. https://schule.bayernport.com/gamma/gamma05.pdf, Accessed on 06 June 2022.
Stanica, P. (2001). Good lower and upper bounds on binomial coefficients, J. Inequal. Pure Appl. Math., 2(3), art. 30 (1-5), 2001.
Stifel, M. (1544). Arithmetica Integra, Iohan Petreium, Nuremberg, 1544. See Book 1, Chp. VI p. 45v in https://archive.org/details/bub_gb_fndPsRv08R0C, Accessed on 06 June 2022.
Stirling, J. (1730). Methodus Differentialis: Sive Tractatus de Summatione et Interpolatione Serierum Infinitarum, Gul. Bowyer & G. Strahan, London, 1730. https://archive.org/details/bub_gb_71ZHAAAAYAAJ/, Accessed on 06 June 2022.
Takita, M.; Yoder, T.J. (2022). How IBM Quantum is advancing quantum error correction with hardware experiments (2022). Available: https://research.ibm.com/blog/advancing-quantumerror- correction, Accessed on 09 June 2022.
Tartaglia, N. (1556). General Trattato di Numeri et Misure, Curtio Troiano de i Nauò, Vinice, 1556. https://doi.org/10.3931/e-rara-19205, and in particular Part II, Book 2, Chp. XXI, p. 69r https://www.e-rara.ch/zut/content/zoom/6032964, Accessed on 06 June 2022.
Tweddle, I. (1984). Approximating n!. Historical origins and error analysis, Amer. J. Phys., 52(6), 487-488, 1984.
https://doi.org/10.1119/1.13889
Tweddle, I. (2003). James Stirling's Methodus Differentialis - An annotated translation of Stirling's text, Springer, 2003.
https://doi.org/10.1007/978-1-4471-0021-8
Uspenskii, V.A. (1974). Pascal's Triangle (translated from Russian by Sookne, D.J.; McLarnan, T.). Univ. Chicago Press, 1974.
von Neumann, J. (1956). Probabilistic logics and the synthesis of reliable organisms from unreliable components, In Shannon, C.E.
https://doi.org/10.1515/9781400882618-003
McCarthy, J. (eds.), Automata Studies (AM-34), Princeton Univ. Press, 43-98, 1956. Available: https://archive.org/details/vonNeumann_Prob_Logics_Rel_Org_Unrel_Comp_Caltech_1952/ mode/2up, Accessed on 06 June 2022.
Wilson, R.; Watkins, J.J. (eds.) (2015). Combinatorics: Ancient and Modern, Oxford Univ. Press, 2015.
Windschitl, R.H. (2002). A curious result, Nov. 2002. http://www.rskey.org/CMS/index.php/thelibrary/ 11, Accessed on 06 June 2022.
Yang, Z.-H.; Tian, J.-F. (2018). An accurate approximation formula for gamma function, J. Inequal. Appl., 2018(1), art. 56 (1-9), 2018.
Additional Files
Published
Issue
Section
License
Copyright (c) 2022 Leonard Daus, Marilena Jianu, Mariana Nagy, Roxana-Mariana Beiu
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
