×

A history and a survey of lattice path enumeration. (English) Zbl 1204.05015

Summary: In celebration of the Sixth International Conference on Lattice Path Counting and Applications, it is befitting to review the history of lattice path enumeration and to survey how the topic has progressed thus far.
We start the history with early games of chance specifically the ruin problem which later appears as the ballot problem. We discuss André’s Reflection Principle and its misnomer, its relation with the method of images and possible origins from physics and Brownian motion, and the earliest evidence of lattice path techniques and solutions.
In the survey, we give representative articles on lattice path enumeration found in the literature in the last 35 years by the lattice, step set, boundary, characteristics counted, and solution method. Some of this work appears in the author’s 2005 dissertation.

MSC:

05A15 Exact enumeration problems, generating functions
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics

Software:

AARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addario-Berry, L., Reed, B., 2006. Ballot theorems, old and new. Bolyai Society Mathematical Studies Series 17, 9-35.; Addario-Berry, L., Reed, B., 2006. Ballot theorems, old and new. Bolyai Society Mathematical Studies Series 17, 9-35. · Zbl 1151.91412
[2] Aebly, J., Démonstration du problème du scrutin par des considérations géométriques, L’enseignement mathématique, 23, 185-186 (1923) · JFM 50.0656.01
[3] Aigner, M., Lattice paths and determinants, (Computational discrete mathematics, 1-12, Lecture Notes in Computer Science, vol. 2122 (2001), Springer: Springer Berlin) · Zbl 0999.05007
[4] André, D., Solution directe du probleme resolu par M. Bertrand, Comptes rendus hebdomadaires Seances Paris, 105, 436-437 (1887) · JFM 19.0200.05
[5] Andrews, G.; Askey, R.; Roy, R., Special functions, (Encyclopedia of Mathematics and its Applications (1999), Cambridge University Press: Cambridge University Press Cambridge)
[6] Banderier, C., Limit laws for the basic parameters of lattice paths with unbounded jumps, (Mathematics and Computer Science, II. Trends Math (2002), Birkhäuser: Birkhäuser Basel), 33-47 · Zbl 1024.60004
[7] Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci., 281, 37-80 (2002) · Zbl 0996.68126
[8] Banderier, C.; Bousquet-Mélou, M.; Denise, A.; Flajolet, P.; Gardy, D.; Gouyou-Beauchamps, D., Generating functions for generating trees. Formal power series and algebraic combinatorics (Barcelona, 1999), Discrete Math., 246, 29-55 (2002) · Zbl 0997.05007
[9] Banderier, C., Fédou, J.-M., Garcia, C., Merlini, D., 2003. Algebraic succession rules and lattice paths with an infinite set of jumps, unpublished.; Banderier, C., Fédou, J.-M., Garcia, C., Merlini, D., 2003. Algebraic succession rules and lattice paths with an infinite set of jumps, unpublished.
[10] Barbier, É., 1887. Généralisation du probl ème résolu par M.J. Bertrand, Comptes Rendus de l’Acadé mie des Sciences, Paris 105, 407.; Barbier, É., 1887. Généralisation du probl ème résolu par M.J. Bertrand, Comptes Rendus de l’Acadé mie des Sciences, Paris 105, 407.
[11] Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., A construction for the enumerating \(k\)-coloured Motzkin paths, (Lecture Notes in Computer Science, vol. 959 (1995), Springer: Springer Berlin), 254-263
[12] Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., ECO: a methodology for the enumeration of combinatorial objects, J. Differ. Equations Appl., 5, 435-490 (1999) · Zbl 0944.05005
[13] Barcucci, E.; Pergola, E.; Pinzani, R.; Rinaldi, S., ECO-systems for Dyck and Schröder paths, Pure Math. Appl., 11, 401-407 (2000) · Zbl 0980.05004
[14] Barcucci, E.; Pergola, E.; Pinzani, R.; Rinaldi, S., ECO-method and hill-free generalized Motzkin paths, Sem. Lothar. Combin., 46, 14 (2001/2002), Art. B46b · Zbl 0982.05007
[15] Barcucci, E.; Rinaldi, S., Some linear recurrences and their combinatorial interpretations by means of regular languages, Theoret. Comput. Sci., 255, 679-686 (2001) · Zbl 0974.68101
[16] Barnabei, M., Polynomial sequences of integral type and recursive matrices, Umbral calculus and its applications (Cortona, 1998). Comput. Math. Appl., 41, 1125-1141 (2001) · Zbl 0981.05013
[17] Barton, D. E.; Mallows, C. L., Some aspects of the random sequence, Annals of Mathematical Statistics, 36, 236-260 (1965) · Zbl 0128.13001
[18] Behrend, R., 2008. Osculating paths and oscillating tableaux. Elect. J. Combin 15, 1 R9; Behrend, R., 2008. Osculating paths and oscillating tableaux. Elect. J. Combin 15, 1 R9 · Zbl 1180.05006
[19] Bernoulli, J., 1713. Ars Conjectandi.; Bernoulli, J., 1713. Ars Conjectandi.
[20] Bertrand, J., Solution d’un probleme, Comptes Rendus de l’Academie des Science, Paris, 105, 369 (1887) · JFM 19.0200.03
[21] Bertrand, J., Observations, Comptes Rendus de l’Academie des Science, Paris, 105, 437-439 (1887) · JFM 19.0200.06
[22] Bertrand, J., 1907. Calcul des probabilités. Paris, Gauthier-Villars.; Bertrand, J., 1907. Calcul des probabilités. Paris, Gauthier-Villars.
[23] Bizley, M. T.L., Derivation of a new formula for the number of minimal lattice paths from (0,0) to (km, kn) having just \(t\) contacts with the line; and a proof of Grossman’s formula for the number of paths which may touch but do not rise above this line, J. Inst. Actuar., 80, 55-62 (1954) · Zbl 0055.00702
[24] Bonin, J.; Shapiro, L. W.; Simion, R., Some q-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Statist. Plann. Inference, 34, 35-55 (1993) · Zbl 0783.05008
[25] Bousquet-Mélou, M., Counting walks in the quarter plane, (Mathematics and Computer Science, II, Trends Math (2002), Birkhäuser: Birkhäuser Basel), 49-67 · Zbl 1026.05004
[26] Bousquet-Mélou, M.; Petkovšek, M., Linear recurrences with constant coefficients: the multivariate case, Discrete Math., 225, 51-75 (2000) · Zbl 0963.05005
[27] Brak, R., 1997. Osculating lattice paths and alternating sign matrices. In: Proceedings of 9th Formal Power Series and Algebraic Combinatorics Conference (Vienna, 1997).; Brak, R., 1997. Osculating lattice paths and alternating sign matrices. In: Proceedings of 9th Formal Power Series and Algebraic Combinatorics Conference (Vienna, 1997).
[28] Brak, R.; Essam, J. W., Return polynomials for non-intersecting paths above a surface on the directed square lattice, J. Phys. A, 34, 10763-10782 (2001) · Zbl 0996.82033
[29] Brak, R.; Essam, J. W., Bicoloured Dyck paths and the contact polynomial for \(n\) non-intersecting paths in a half-plane lattice, Electron. J. Combin., 10, 18 (2003), R35 · Zbl 1023.05006
[30] Brown, W. G., Historical note on a recurrent combinatorial problem, Amer. Math. Monthly, 72, 973-977 (1965) · Zbl 0136.21204
[31] Chandrasekar, S., Stochastic problems in physics and astronomy, Rev. Modern Phys., 15, 1-89 (1943) · Zbl 0061.46403
[32] Chorneyko, I. Z.; Mohanty, S. G.; Sen, K., Enumeration of restricted three-dimensional lattice paths with fixed number of turns and an application, J. Statist. Plann. Inference, 34, 57-62 (1993) · Zbl 0777.05005
[33] Coker, C., Enumerating a class of lattice paths, Discrete Math., 271, 13-28 (2003) · Zbl 1027.05002
[34] Comtet, L., Advanced Combinatorics. (Translated from French in 1974 by J. W. Nienhuys) (1970), D. Reidel Publishing Company
[35] Corsani, C.; Merlini, D.; Sprugnoli, R., Left inversion of combinatorial sums, Discrete Math., 180, 107-122 (1998) · Zbl 0903.05005
[36] De Moivre, A., De Mensura Sortis, Philosophical Trans. London., 27, 213-264 (1711)
[37] De Moivre, A., The Doctrine of Chances (1756), Chelsea Publishing Co.: Chelsea Publishing Co. New York, 1967 · Zbl 0153.30801
[38] Deutsch, E., A bijection on Dyck paths and its consequences, Discrete Math., 197, 253-256 (1998) · Zbl 0890.05005
[39] Deutsch, E., Dyck path enumeration, Discrete Math., 204, 167-202 (1999) · Zbl 0932.05006
[40] Deutsch, E., An involution on Dyck paths and its consequences, Discrete Math., 204, 163-166 (1999) · Zbl 0932.05005
[41] Deutsch, E.; Prodinger, H., A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoret. Comput. Sci., 307, 319-325 (2003) · Zbl 1048.05024
[42] Deutsch, E.; Shapiro, L. W., A survey of the Fine numbers, Discrete Math., 241, 241-265 (2001) · Zbl 0992.05011
[43] Deutsch, E.; Shapiro, L. W., A bijection between ordered trees and 2-Motzkin paths and its many consequences, Discrete Math., 256, 655-670 (2002) · Zbl 1012.05050
[44] Donaghey, R.; Shapiro, L. W., Motzkin numbers, J. Combinatorial Theory (A), 23, 291-301 (1977) · Zbl 0417.05007
[45] Dvoretzky, A.; Motzkin, T. H., A problem of arrangements, Duke Math. J., 14, 305-313 (1947) · Zbl 0030.16701
[46] Elizalde, S., 2004. Statistics on pattern avoiding permutations. Ph.D. Thesis, MIT.; Elizalde, S., 2004. Statistics on pattern avoiding permutations. Ph.D. Thesis, MIT.
[47] Elizalde, S.; Deutsch, E., A simple and unusual bijection for Dyck paths and its consequences, Ann. Comb., 7, 281-297 (2003) · Zbl 1047.05001
[48] Elizalde, S.; Pak, I., Bijections for refined, restricted permutations, J. Combin. Theory. Ser. A, 105, 209-217 (2004) · Zbl 1048.05003
[49] Eu, S.-P.; Liu, S.-C.; Yeh, Y.-N., Dyck paths with peaks avoiding or restricted to a given set, Stud. Appl. Math., 111, 453-465 (2003) · Zbl 1141.05307
[50] Feller, W., 1950. An Introduction to Probability Theory and its Applications, vol. 1, first ed., John Wiley & Sons, Inc.; Feller, W., 1950. An Introduction to Probability Theory and its Applications, vol. 1, first ed., John Wiley & Sons, Inc. · Zbl 0039.13201
[51] Feller, W., 1957. An Introduction to Probability Theory and its Applications, vol. 1, second ed. John Wiley & Sons, Inc.; Feller, W., 1957. An Introduction to Probability Theory and its Applications, vol. 1, second ed. John Wiley & Sons, Inc. · Zbl 0077.12201
[52] Feller, W., 1968. An Introduction to Probability Theory and its Applications, vol. 1, third ed., John Wiley & Sons, Inc.; Feller, W., 1968. An Introduction to Probability Theory and its Applications, vol. 1, third ed., John Wiley & Sons, Inc. · Zbl 0155.23101
[53] Ferrari, L.; Pinzani, R., A linear operator approach to succession rules, Linear Algebra Appl., 348, 231-246 (2002) · Zbl 1003.05007
[54] Fray, R. S.; Roselle, D. P., Weighted lattice paths, Pacific J. Math., 37, 85-95 (1971) · Zbl 0196.02703
[55] Fulmek, M., On pairs of lattice paths with a given number of intersections, J. Combin. Theory Ser. A, 78, 154-161 (1997) · Zbl 0874.05004
[56] Fulmek, M., Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three, Adv. in Appl. Math., 30, 607-632 (2003) · Zbl 1020.05008
[57] Gessel, I. M., A factorization for formal Laurent series and lattice path enumeration, J. Combin. Theory Ser. A., 28, 321-337 (1980)
[58] Gessel, I. M., A probabilistic method for lattice path enumeration, J. Statist. Plann. Inference, 14, 49-58 (1986) · Zbl 0602.05006
[59] Gessel, I. M.; Viennot, G., Binomial determinants, paths, and hook length formulae, Adv. in Math., 58, 300-321 (1985) · Zbl 0579.05004
[60] Gessel, I. M.; Zeilberger, D., Random walk in a Weyl chamber, Proc. Amer. Math Soc., 115, 27-31 (1992) · Zbl 0792.05148
[61] Gessel, I. M.; Goddard, W.; Shur, W.; Wilf, H.; Yen, L., Counting pairs of lattice paths by intersections, J. Combin. Theory Ser. A., 74, 173-187 (1996) · Zbl 0853.05003
[62] Gessel, I. M.; Shur, W., Even and odd pairs of lattice paths with multiple intersections, J. Combin. Theory Ser. A., 75, 243-253 (1996) · Zbl 0866.05002
[63] Gessel, I. M.; Ree, S., Lattice paths and Faber polynomials, (Advances in Combinatorial Methods and Applications to Probability and Statistics (1997), Birkhäuser, Inc.), 3-13 · Zbl 0882.05005
[64] Gnedenko, B.V. 1954. The Theory of Probability (translated from Russian by B. D. Seckler in 1962). Chelsea, NY.; Gnedenko, B.V. 1954. The Theory of Probability (translated from Russian by B. D. Seckler in 1962). Chelsea, NY.
[65] Gnedenko, B. V.; Koroljuk, V. S., On the maximum discrepancy between two empirical distributions. (Russian), Doklady Akad. Nauk SSSR (N.S.), 80, 525-528 (1951) · Zbl 0044.13602
[66] Goodman, E.; Narayana, T. V., Lattice paths with diagonal steps, Canad. Math. Bull., 12, 847-855 (1969) · Zbl 0211.49503
[67] Grossman, H. D., Fun with lattice points - 4,4a,5, Scripta Math., 12, 223-225 (1946)
[68] Gray, A., Lord Kelvin (1908), Chelsea Publishing Co.: Chelsea Publishing Co. New York, 1973 · JFM 27.0027.02
[69] Guttman, A. J.; Owczarek, A. L.; Viennot, X. G., Vicious walkers and Young tableaux. I. Without walls, J. Phys. A., 31, 8123-8135 (1998) · Zbl 0930.05098
[70] Guttman, A. J.; Vöge, M., Lattice paths: vicious walkers and friendly walkers, J. Statist. Plann. Inference, 101, 107-131 (2002) · Zbl 0993.05007
[71] Handa, B. R.; Mohanty, S. G., On lattice paths with several diagonal steps, Canad. Math. Bull., 11, 537-545 (1968) · Zbl 0186.30403
[72] Handa, B. R.; Mohanty, S. G., Higher dimensional lattice paths with diagonal steps, Discrete Math., 15, 137-140 (1976) · Zbl 0344.05016
[73] Handa, B. R.; Mohanty, S. G., Enumeration of higher dimensional paths under restrictions, Discrete Math., 26, 119-128 (1979) · Zbl 0417.05038
[74] Handa, B. R.; Mohanty, S. G., On q-binomial coefficients and some statistical applications, SIAM J. Math. Anal., 11, 1027-1035 (1980) · Zbl 0448.05002
[75] Hendry, J., 1986. James Clerk Maxwell and the Theory of the Electromagnetic Field. Adam Hilger, Ltd.; Hendry, J., 1986. James Clerk Maxwell and the Theory of the Electromagnetic Field. Adam Hilger, Ltd.
[76] Humphreys, K.; Niederhausen, H., Counting lattice paths with privileged access using Sheffer sequences, Congr. Numerantium, 143, 141-160 (2000) · Zbl 0971.05013
[77] Humphreys, K.; Niederhausen, H., Counting lattice paths taking steps in infinitely many directions under special access restrictions, Theoretical Computer Science, 319, 385-409 (2004) · Zbl 1043.05008
[78] Humphreys, K.; Niederhausen, H., Counting lattice paths that have infinite step sets that can not be reinterpreted as weighted, finite step sets, Congr. Numerantium, 169, 33-54 (2004) · Zbl 1064.05026
[79] Huygens, C., Treatise on light., Translated by S. P. Thompson 1912 (1690), University of Chicago Press 1950
[80] Jani, M.; Rieper, R., Continued fractions and Catalan problems, Electron. J. Combin., 7, 8 (2000), R45 · Zbl 1047.05500
[81] Kemperman, J. H.M., The Passage Problem for a Stationary Markov Chain (1961), University of Chicago Press: University of Chicago Press Chicago, Illinois
[82] Koroljuk, V. S., On the discrepancy of empiric distributions for the case of two independent samples, Izv. Akad. Nauk SSSR Ser. Math., 19, 81-96 (1955), IMS & AMS Selected translations Math. Statist. Prob. 4(1963), 105-122
[83] Krattenthaler, C., Counting lattice paths with a linear boundary. I and II, Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II, 198, 87-107 (1989), 171-199 · Zbl 0695.05003
[84] Krattenthaler, C., Enumeration of lattice paths and generating functions for skew plane partitions, Manuscripta Math., 63, 129-155 (1989) · Zbl 0672.05011
[85] Krattenthaler, C., Generating functions for shifted plane partitions, J. Statist. Plann. Inference, 34, 197-208 (1993) · Zbl 0777.05009
[86] Krattenthaler, C., The major counting of nonintersecting lattice paths and generating functions for tableaux, Mem. Amer. Math. Soc., 115, vi+109 (1995) · Zbl 0830.05003
[87] Krattenthaler, C., Counting nonintersecting lattice paths with respect to weighted turns, Sém. Lothar. Combin., 34 (1995), Art. B34i · Zbl 0855.05004
[88] Krattenthaler, C., Oscillating tableaux and nonintersecting lattice paths, J. Statist. Plann. Inference, 54, 75-85 (1996) · Zbl 0863.05079
[89] Krattenthaler, C., The enumeration of lattice paths with respect to their number of turns, (Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol (1997), Birkhäuser Boston: Birkhäuser Boston MA), 29-58 · Zbl 0882.05004
[90] Krattenthaler, C., Permutations with restricted patterns and Dyck paths, Adv. Appl. Math., 27, 510-530 (2001) · Zbl 0994.05001
[91] Krattenthaler, C.; Guttman, A. J.; Viennot, X. G., Vicious walkers, friendly walkers, and Young tableaux. II. With a wall, J. Phys. A., 33, 8835-8866 (2000) · Zbl 0970.82016
[92] Krattenthaler, C.; Guttman, A. J.; Viennot, X. G., Vicious walkers, friendly walkers, and Young tableaux. III. Between two walls, J. Statist. Phys., 110, 1069-1086 (2003) · Zbl 1016.82017
[93] Krattenthaler, C.; Niederhausen, H., Lattice paths with weighted left turns above a parallel to the diagonal, Congr. Numer., 124, 73-80 (1997) · Zbl 0903.05002
[94] Krattenthaler, C.; Prohaska, M., A remarkable formula for counting nonintersecting lattice paths in a ladder with respect to turns, Trans. Amer. Math. Soc., 351, 1015-1042 (1999) · Zbl 0908.05004
[95] Krattenthaler, C.; Rubey, M., A determinantal formula for the Hilbert series of one-sided ladder determinantal rings, (Algebra, Arithmetic and Geometry with Applications (2004), Springer: Springer Berlin), 525-551 · Zbl 1095.13518
[96] Krattenthaler, C.; Sulanke, R., Counting pairs of nonintersecting lattice paths with respect to weighted turns, Discrete math., 153, 189-198 (1996) · Zbl 0853.05004
[97] Kreweras, G., Sur une classe de problems de denombrement liés au treillis des partitions des entiers, Cahiers du Bur. Univ. de Rech. Opér., 6, 5-105 (1965)
[98] Kreweras, G.; Niederhausen, H., Solution of an enumerative problem connected with lattice paths, European J. Combin., 2, 55-60 (1981) · Zbl 0471.05004
[99] Kulkarni, D. M., Counting of paths and coefficients of the Hilbert polynomial of a determinantal ideal, Discrete Math., 154, 141-151 (1996) · Zbl 0853.05005
[100] Labelle, J.; Yeh, Y. N., Dyck paths of knight moves, Discrete Appl. Math., 24, 213-221 (1989) · Zbl 0691.05004
[101] Labelle, J., Generalized Dyck languages, Ann. Sci. Math. Québec, 17, 53-64 (1993) · Zbl 0795.05004
[102] Labelle, J., On pairs of noncrossing generalized Dyck paths, J. Statist. Plann. Inference, 34, 209-217 (1993) · Zbl 0771.05011
[103] Labelle, J., Paths in the Cartesian, triangular, and hexagonal lattices, Bull. Inst. Combin. Appl., 17, 47-61 (1996) · Zbl 0851.05001
[104] Lindström, B., On the vector representation of induced matroids, Bull. London Math. Soc., 5, 85-90 (1973) · Zbl 0262.05018
[105] Loehr, N., Trapezoidal lattice paths and multivariate analogues, Adv. in Appl. Math., 31, 597-629 (2003) · Zbl 1065.05008
[106] Loehr, N., Note on André’s reflection principle, Discrete Mathematics, 280, 233-236 (2004) · Zbl 1041.05002
[107] Lu, Q., A note on lattice paths with diagonal steps in three dimensional space, J. Math. Res. Exposition, 25, 447-450 (2005)
[108] MacMahon, P. A., Memoir on the theory of the compositions of numbers, Philosophical Transaction of the Royal Society of London. Series A, 184, 835-901 (1893) · JFM 25.0258.01
[109] MacMahon, P. A., Memoir on the theory of the partitions of numbers. Part IV. On the probability that the successful candidate at an election by ballot may never at any time have fewer votes than the one who is unsuccessful; on a generalization of this question; and on its connexion with other questions of partition, permutation, and combination, Philosophical Transaction of the Royal Society of London. Series A, 209, 153-175 (1909) · JFM 40.0281.04
[110] Mansour, T., Counting peaks at height \(k\) in a Dyck path, J. Integer Seq., 5, 9 (2002), Art. 02.1.1 · Zbl 1012.05004
[111] Mansour, T., Statistics on Dyck paths, J. Integer Seq., 9, 13 (2006), Art. 06.1.5 · Zbl 1101.05006
[112] Maxwell, J.C., 1892. A Treatise on Electricity and Magnetism, vol. I, II third ed. Reprinted by Oxford Univ. Press, 1937.; Maxwell, J.C., 1892. A Treatise on Electricity and Magnetism, vol. I, II third ed. Reprinted by Oxford Univ. Press, 1937.
[113] Maxwell, J.C., 1846-1879. The Scientific Letters and Papers of James Clerk Maxwell, vol. I, II, III. ed. by P.M. Harman. Cambridge University Press, 1990; Maxwell, J.C., 1846-1879. The Scientific Letters and Papers of James Clerk Maxwell, vol. I, II, III. ed. by P.M. Harman. Cambridge University Press, 1990
[114] Maxwell, J.C., Garber, E., Brush, S., Everitt, C.W.F., (Eds.), 1986. Maxwell on Molecules and Gases. The MIT Press.; Maxwell, J.C., Garber, E., Brush, S., Everitt, C.W.F., (Eds.), 1986. Maxwell on Molecules and Gases. The MIT Press.
[115] McGregor, J. R.; Narayana, T. V.; Ozsoyoglu, Z. M., On touchings, crossings and meetings of lattice paths with the diagonal, Utilitas Math., 30, 45-51 (1986) · Zbl 0632.05011
[116] Merlini, D., Sprugnoli, R., Verri, M.C., 1994. Algebraic and combinatorial properties of simple, coloured walks. Trees in algebra and programming—CAAP (Edinburgh, 1994), Lecture Notes in Computer Science, vol. 787. Springer, Berlin, pp. 218-233.; Merlini, D., Sprugnoli, R., Verri, M.C., 1994. Algebraic and combinatorial properties of simple, coloured walks. Trees in algebra and programming—CAAP (Edinburgh, 1994), Lecture Notes in Computer Science, vol. 787. Springer, Berlin, pp. 218-233. · Zbl 0938.05500
[117] Merlini, D.; Rogers, D. G.; Sprugnoli, R.; Verri, M. C., On some alternative characterizations of Riordan arrays, Canadian J. Math., 49, 301-320 (1997) · Zbl 0886.05013
[118] Merlini, D.; Verri, M. C., Generating trees and proper Riordan arrays, Discrete Math., 218, 167-183 (2000) · Zbl 0949.05004
[119] de Mier, A.; Noy, M., A solution to the tennis ball problem, Theoret. Comput. Sci., 346, 254-264 (2005) · Zbl 1078.05006
[120] Mohanty, S. G., Lattice Path Counting and Applications (1979), Academic Press · Zbl 0455.60013
[121] Mohanty, S. G.; Watanabe, T., On an inclusion-exclusion formula based on the reflection principle, Discrete Math., 64, 281-288 (1987) · Zbl 0617.05008
[122] Mozer, L.; Zayachkowski, W., Lattice paths with diagonal steps, Scripta Math., 26, 223-229 (1963) · Zbl 0111.24105
[123] Munarini, E.; Zagaglia Salvi, N., Binary strings without zigzags, Sém. Lothar. Combin., 49, 15 (2002-2004), Art. B49h · Zbl 1186.05015
[124] Narayana, T. V., A combinatorial problem and its applications to probability theory I, J. Indian Soc. Agric. Statist., 7, 169-178 (1955)
[125] Narayana, T. V., Lattice Path Combinatorics with Statistical Applications (1979), University of Toronto Press · Zbl 0437.05001
[126] Netto, E., 1900. Lehrbuch der Combinatorik. Teubner, Leipzig.; Netto, E., 1900. Lehrbuch der Combinatorik. Teubner, Leipzig.
[127] Niederhausen, H., Lattice paths with three step directions, Congr. Numer., 24, 753-774 (1979)
[128] Niederhausen, H., Sheffer polynomials in path enumeration, Congr. Numer., 26, 281-294 (1980) · Zbl 0444.05005
[129] Niederhausen, H., An enumeration problem and some consequences, Congr. Numer., 33, 261-273 (1981)
[130] Niederhausen, H., How many paths cross at least l given lattice points?, Congr. Numer., 36, 161-173 (1982) · Zbl 0511.60011
[131] Niederhausen, H., A formula for explicit solutions of certain linear recursions on polynomial sequences, Congr. Numer., 49, 87-98 (1985)
[132] Niederhausen, H., The enumeration of restricted random walks by Sheffer polynomials with applications to statistics, J. Statist. Plann. Inference, 14, 95-114 (1986) · Zbl 0619.05004
[133] Niederhausen, H., Counting intersecting weighted pairs of lattice paths using transforms of operators, Congr. Numer., 102, 161-173 (1994) · Zbl 0835.05001
[134] Niederhausen, H., Symmetric Sheffer sequences and their applications to lattice path counting, J. Statist. Plann. Inference, 54, 87-100 (1996) · Zbl 0857.05013
[135] Niederhausen, H., Lattice path enumeration and umbral calculus, (Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol (1997), Birkhäuser Boston: Birkhäuser Boston MA), 15-27 · Zbl 0880.05003
[136] Niederhausen, H., Lattice paths between diagonal boundaries, Electron. J. Combin., 5, 37 (1998), R30 · Zbl 0909.05004
[137] Niederhausen, H., Recursive initial value problems for Sheffer sequences, Discrete Math., 204, 319-327 (1999) · Zbl 0944.05004
[138] Niederhausen, H., Generalized Sheffer sequences satisfying piecewise functional conditions, Computers and Mathematics with Applications, 41, 1155-1171 (2001) · Zbl 0999.05009
[139] Niederhausen, H., Catalan traffic at the beach, Electron. J. Combin., 9, 17 (2002), R33 · Zbl 1005.05004
[140] Niederhausen, H., Rota’s umbral calculus and recursions, Algebra Universalis, 49, 435-457 (2003) · Zbl 1093.05005
[141] Niederhausen, H., Sullivan, S., 2010. Pattern Avoiding Ballot Paths and Finite Operator Calculus in this issue of the J. Statist. Plann. Inference.; Niederhausen, H., Sullivan, S., 2010. Pattern Avoiding Ballot Paths and Finite Operator Calculus in this issue of the J. Statist. Plann. Inference. · Zbl 1278.05019
[142] Olive, G., The ballot problem revisited, Stud. Appl. Math., 78, 21-30 (1988) · Zbl 0712.05007
[143] Peacock, J., Proof of a Theorem in permutations, The Mathematical Gazette, 18, 124 (1934)
[144] Peacock, J., On “Al Capone and the Death Ray”, The Mathematical Gazette, 26, 218-219 (1942)
[145] Peart, P.; Woan, W.-J., A divisibility property for a subgroup of Riordan matrices, Discrete Appl. Math., 98, 255-263 (2000) · Zbl 0944.05016
[146] Peart, R.; Woan, W.-J., Dyck paths with no peaks at height \(k\), J. Integer Seq., 4, 6 (2001), Art. 01.1.3 · Zbl 0969.05002
[147] Perrin, J., 1920. Atoms. English translation of Les Atomes, 4th ed. by D. Hammick. Nostrand Co.; Perrin, J., 1920. Atoms. English translation of Les Atomes, 4th ed. by D. Hammick. Nostrand Co.
[148] Planck, M., 1931. Maxwell’s Influence on Theoretical Physics in Germany. In: Maxwell, J.C., A commemoration Volume. Cambridge University Press, Cambridge, 45-65.; Planck, M., 1931. Maxwell’s Influence on Theoretical Physics in Germany. In: Maxwell, J.C., A commemoration Volume. Cambridge University Press, Cambridge, 45-65.
[149] Poincaré, H., 1896. Calcul des probabilit és. Paris, G. Carré.; Poincaré, H., 1896. Calcul des probabilit és. Paris, G. Carré.
[150] Polya, G., 1970. Proceedings of the Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, pp. 381-384.; Polya, G., 1970. Proceedings of the Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, pp. 381-384.
[151] Renault, M., Lost (and found) in translation: André’s actual method and its application to the generalized ballot problem, American Mathematical Monthly, 115, 358-363 (2008) · Zbl 1142.60004
[152] Renault, M., Four proofs of the ballot theorem, Mathematics Magazine, 80, 345-352 (2007) · Zbl 1144.05303
[153] Robertson, A.; Saracino, D.; Zeilberger, D., Refined restricted permutations, Ann. Comb., 6, 427-444 (2002) · Zbl 1017.05014
[154] Rogers, D. G.; Shapiro, L. W., Some correspondences involving the Schröder numbers and relations, (Combinatorial Mathematics, Lecture Notes in Math., vol. 686 (1978), Springer: Springer Berlin) · Zbl 0469.05005
[155] Rogers, D. G.; Shapiro, L. W., Deques, trees and lattice paths, (Combinatorial Mathematics, VIII (Geelong, 1980), Lecture Notes in Math., vol. 884 (1981), Springer: Springer Berlin, New York) · Zbl 0469.05005
[156] Rohatgi, V. K., A note on lattice paths with diagonal steps, Canad. Math. Bull., 7, 470-472 (1964) · Zbl 0123.00303
[157] Rohatgi, V. K., Some combinatorial identities involving lattice paths, Amer. Math. Monthly, 73, 507-508 (1966) · Zbl 0136.24608
[158] Rota, G.-C.; Kahaner, D.; Odlyzko, A., On the foundations of combinatorial theory VIII: Finite operator calculus, Journal of Mathematical Analysis and Applications, 42, 684-760 (1973) · Zbl 0267.05004
[159] Sapounakis, A.; Tsikouras, P., Counting peaks and valleys in \(k\)-colored Motzkin paths, Electron. J. Combin., 12, 20 (2005), R16 · Zbl 1060.05009
[160] Sato, M., Generating functions for the number of lattice paths between two parallel lines with a rational incline, Math. Japon, 34, 123-137 (1989) · Zbl 0689.05005
[161] Seneta, E., Marian Smoluchowski, (Statisticians of the Centuries (2001), Springer: Springer Berlin), 299-302
[162] Shapiro, L. W.; Getu, S.; Woan, W. J.; Woodson, L. C., The Riordan group. Combinatorics and theoretical computer science (Washington, DC, 1989), Discrete Appl. Math., 34, 229-239 (1991)
[163] Shapiro, L. W., Random walks with absorbing points, Discrete Appl. Math., 39, 57-67 (1992) · Zbl 0770.05005
[164] Shapiro, L. W.; Stephens, A. B., Bootstrap percolation, the Schröder numbers, and the N-kings problem, SIAM J. Discrete Math., 4, 275-280 (1991) · Zbl 0736.05008
[165] Shapiro, L. W.; Sulanke, R. A., Bijections for the Schröder numbers, Math Mag., 73, 369-376 (2000)
[166] Slutsky, M., Diffusion in half space: from Lord Kelvin to path integrals, American Journal of Physics, 73, 308-314 (2005)
[167] Smith, D.E., 1929. A Source Book in Mathematics, New York, 546-565.; Smith, D.E., 1929. A Source Book in Mathematics, New York, 546-565.
[168] Smoluchowski. M. v., 1913. Einge Beispeile Brown’scher Molekularbewegung unter einfluss äusserer Kräfte.. Bulletin Internation de l’Académie des Sciences de Cracovie, Classe des Sciences Mathématiques et Naturelles, série A, 418-434.; Smoluchowski. M. v., 1913. Einge Beispeile Brown’scher Molekularbewegung unter einfluss äusserer Kräfte.. Bulletin Internation de l’Académie des Sciences de Cracovie, Classe des Sciences Mathématiques et Naturelles, série A, 418-434.
[169] Smoluchowski, M.v., Über “Durchschnittliche maximale Abweichung” bei brown’scher Molekularbewegung und Brillouin’s Diffusionsversuche, Sitzungsberichte der Akademie der Wissenschafter in Wien; Marem. -naturw. Klasse, Abteilung IIa, 124, 263-276 (1915), Band, 3 und 4, Heft
[170] Smoluchowski, M.v., 1923. Abhandlungen uber die Brownsche Bewegung und verwandte Erscheinungen, R. Furth, ed. Ostwald’s Klassiker der exakten Wissenschaften 207, Academische Verlagsgesellschaft, Leipzig.; Smoluchowski, M.v., 1923. Abhandlungen uber die Brownsche Bewegung und verwandte Erscheinungen, R. Furth, ed. Ostwald’s Klassiker der exakten Wissenschaften 207, Academische Verlagsgesellschaft, Leipzig.
[171] Smoluchowski, M. (1924-1928). Pisma Mariana Smoluchowskiego (Collected Works of Marian Smoluchowski). 3 vol., ed. by W. Natanson. PAU, Krakow.; Smoluchowski, M. (1924-1928). Pisma Mariana Smoluchowskiego (Collected Works of Marian Smoluchowski). 3 vol., ed. by W. Natanson. PAU, Krakow.
[172] Sprugnoli, R., Riordan arrays and combinatorial sums, Discrete Math., 132, 267-290 (1994) · Zbl 0814.05003
[173] Sprugnoli, R., Riordan arrays and the Abel-Gould identity, Discrete Math., 142, 213-233 (1995) · Zbl 0832.05007
[174] Stanley, R.P., 1986. Enumerative Combinatorics, vol. 1. Wadsworth & Brooks/Cole.; Stanley, R.P., 1986. Enumerative Combinatorics, vol. 1. Wadsworth & Brooks/Cole. · Zbl 0608.05001
[175] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001
[176] Stembridge, J. R., Nonintersecting paths, Phaffians, and plane partitions, Adv. Math., 83, 96-131 (1990) · Zbl 0790.05007
[177] Stocks, D. R., Lattice paths in \(E^3\) with diagonal steps, Canad. Math. Bull., 10, 653-658 (1967) · Zbl 0157.03505
[178] Sulanke, R., A recurrence restricted by a diagonal condition: generalized Catalan arrays, Fibonacci Quart., 27, 33-46 (1989) · Zbl 0666.10008
[179] Sulanke, R., Refinements of the Narayana numbers, Bull. Inst. Combin. Appl., 7, 60-66 (1993) · Zbl 0804.05004
[180] Sulanke, R., Bijective recurrences concerning Schröder paths, Electr. J. Combin., 5, R40 (1998) · Zbl 0913.05007
[181] Sulanke, R., Catalan paths statistics having the Narayana distribution, Discrete Math., 180, 369-389 (1998) · Zbl 0896.05002
[182] Sulanke, R., Constraint-sensitive Catalan path statistics having the Narayana distribution, Discrete Math., 204, 397-414 (1999) · Zbl 0936.05004
[183] Sulanke, R., Moments of generalized Motzkin paths, J. Integer Seq., 3 (2000), Article 00.1.1 · Zbl 1012.05013
[184] Sulanke, R., Counting lattice paths by Narayana polynomials, Electon. J. Combin., 7, 9 (2000), R40 · Zbl 0953.05006
[185] Sulanke, R., Bijective recurrences for Motzkin paths, Adv. in Appl. Math., 27, 627-640 (2001) · Zbl 0992.05015
[186] Sulanke, R., Objects counted by the central Delannoy numbers, J. Integer Seq., 6, 19 (2003), Article 03.1.5 · Zbl 1012.05008
[187] Sulanke, R., Three dimensional Narayana and Schroder numbers, Theor. Comput. Sci., 346, 455-468 (2005) · Zbl 1082.68078
[188] Tamm, U., Lattice paths not touching a given boundary, J. Statist. Plann. Inference, 105, 433-448 (2002) · Zbl 1004.05005
[189] Takács, L., Combinatorial Methods in the Theory of Stochastic Processes (1967), John Wiley & Sons · Zbl 0162.21303
[190] Takács, L., On the ballot theorems, (Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol. (1997), Birkhäuser Boston: Birkhäuser Boston MA), 97-114 · Zbl 0888.60012
[191] Takács, L., Reflection Principle, Enclyclopedia of Statistical Sciences, 7, 670-673 (1986)
[192] Thompson, S.P., 1910. The Life of William Thomson, Baron Kelvin of Largs, vol.1, 11. MacMillan and Co.; Thompson, S.P., 1910. The Life of William Thomson, Baron Kelvin of Largs, vol.1, 11. MacMillan and Co. · JFM 41.0019.01
[193] Thomson, W., Extrait D’une lettre de M. Willam Thomson, Journal de Mathématiques, 10, 364-367 (1845), ed. A.M. Liouville
[194] Thomson, W., Extraits de deux lettres adress ées A. M. Liouville, Journal de Mathématiques, 12, 256-265 (1847), ed. A.M. Liouville
[195] Todhunter, I., A History of the Theory of Probability (1865), Chelsea Publishing Co., 1965
[196] Tolstoy, I., James Clerk Maxwell, A Biography (1981), University of Chicago Press
[197] Ulam, S., Marian Smoluchowski and the Theory of Probabilities in Physics, American Journal of Physics, 25, 475-481 (1957)
[198] van Rensburg, B., Adsorbing staircase walks and staircase polygons, Ann. Comb., 3, 451-473 (1999) · Zbl 0933.05004
[199] Wagner, C. G., The Carlitz lattice path polynomials, Discrete Math., 222, 291-298 (2000) · Zbl 0969.05003
[200] Whitworth, W. A., Arrangements of m things of one sort and n things of another sort under certain conditions of priority, Messenger of Math., 8, 105-114 (1878)
[201] Whitworth, W.A., 1886. Choice and Chance, fourth ed. Deighton Bell, Cambridge.; Whitworth, W.A., 1886. Choice and Chance, fourth ed. Deighton Bell, Cambridge.
[202] Whitworth, W.A., 1901. Choice and Chance, 5th ed. G.E Stechert & Co., NY.; Whitworth, W.A., 1901. Choice and Chance, 5th ed. G.E Stechert & Co., NY. · JFM 11.0163.02
[203] Woan, W.-J.; Shapiro, L. W.; Rogers, D. G., The Catalan numbers, the Lebesgue integral and \(4^{n−2}\), Amer. Math. Monthly, 104, 926-931 (1997) · Zbl 0920.05006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.