×

The Narayana distribution. (English) Zbl 1001.05009

In 1955, T. V. Narayana [C. R. Acad. Sci. Paris 240, 1188-1189 (1955; Zbl 0064.12705)] introduced the distribution \(N_{n,k}= {n\choose k-1}{n\choose k}/n\) for \(1\leq k\leq n\). Define the \(n\)th Narayana polynomial as \(N_n(z)= \sum_{1\leq k\leq n}N_{n,k} z^k\) for \(n\geq 1\). In this paper the author gives a combinatorial proof of a recurrence for Narayana polynomials.

MSC:

05A15 Exact enumeration problems, generating functions

Citations:

Zbl 0064.12705
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barcucci, E.; Del Lungo, A.; Fezzi, S.; Pinzani, R., Some combinatorial interpretations of \(q\)-analogues of Schröder numbers. COMBINATORICS’96 (1996), Assisi: Assisi Italy
[2] Benchekroun, S.; Moszkowski, P., A bijective proof of an enumerative property of legal bracketings, European J. Combin., 17, 605-611 (1996) · Zbl 0863.05005
[3] Bonin, J.; Shapiro, L.; Simion, R., Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Statistical Planning Inference, 34, 35-55 (1993) · Zbl 0783.05008
[4] Cayley, A., On the analytical form called trees, Part II, Philos. Mag. (4), 18, 374-378 (1859)
[5] Delest, M.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. Comp. Sci., 34, 169-206 (1984) · Zbl 0985.68516
[6] Deutsch, E., A bijection on Dyck paths and its consequences, Discrete Math., 179, 253-256 (1998) · Zbl 0890.05005
[7] Euler, L., 1758/59. Summarium, Novi Commentarii academiae scientiarum Petropolitanae, 7, 13-15. (reprinted in Opera Omnia (1) 1953, 26, XVI-XVIII).; Euler, L., 1758/59. Summarium, Novi Commentarii academiae scientiarum Petropolitanae, 7, 13-15. (reprinted in Opera Omnia (1) 1953, 26, XVI-XVIII).
[8] Foata, D.; Zeilberger, D., A classic proof of a recurrence for a very classical sequence, J. Combin. Theory -Ser. A., 80, 380-384 (1997) · Zbl 0883.05007
[9] Habsieger, L.; Kazarian, M.; Lando, S., On the second number of Plutarch, Am. Math. Monthly, 105, 446 (1998) · Zbl 0917.01011
[10] Kirkman, T. P., On the \(k\)-partitions of the \(r\)-gon and \(r\)-ace, Phil. Trans. Roy. Soc. London, 147, 217-272 (1857)
[11] Kreweras, G.; Moszkowski, P., A new enumerative property of the Narayana numbers, J. Statist. Plan. Inference, 14, 63-67 (1986) · Zbl 0601.05005
[12] Kreweras, G., 1986. Joint distributions of three descriptive parameters of bridges. Combin. énumérative Proceedings, Montreal, 1985, Lecture Notes in Mathematics, 1234, Springer, New York, 177-191.; Kreweras, G., 1986. Joint distributions of three descriptive parameters of bridges. Combin. énumérative Proceedings, Montreal, 1985, Lecture Notes in Mathematics, 1234, Springer, New York, 177-191.
[13] van Lint, J. H.; Wilson, R. M., A Course in Combinatorics (1992), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0769.05001
[14] Łukasiewicz, J., 1970. In: Borkowski, L., (Ed.), Selected Works. North-Holland, Amsterdam.; Łukasiewicz, J., 1970. In: Borkowski, L., (Ed.), Selected Works. North-Holland, Amsterdam. · Zbl 0212.00902
[15] Narayana, T. V., Sur les treillis formés par les partitions d’un entier; leurs applications à la théorie des probabilités, Comp. Rend. Acad. Sci. Paris, 240, 1188-1189 (1955) · Zbl 0064.12705
[16] Narayana, T. V., A partial order and its application to probability theory, Sankhyā, 21, 91-98 (1959) · Zbl 0168.39202
[17] Narayana, T.V., 1979. Lattice Path Combinatorics with Statistical Applications. University of Toronto Press.; Narayana, T.V., 1979. Lattice Path Combinatorics with Statistical Applications. University of Toronto Press. · Zbl 0437.05001
[18] Pergola, E., Sulanke, R.A., 1998. Schröder Triangles, Paths, and Parallelogram Polyominoes. J. Integer Sequences, Article 98.1.7 (1998), http://www.research.att.com/ ̃njas/sequences/JIS/.; Pergola, E., Sulanke, R.A., 1998. Schröder Triangles, Paths, and Parallelogram Polyominoes. J. Integer Sequences, Article 98.1.7 (1998), http://www.research.att.com/ ̃njas/sequences/JIS/. · Zbl 0974.05003
[19] Rémy, J-L., Un procédé itératif de dénombrement d’arbres binaires et son application à leur génération aléatoire, RAIRO Inform. Théor., 19, 179-195 (1985) · Zbl 0565.05037
[20] Rogers, D.G., Shapiro, L.W., 1978. Some correspondence involving the Schröder numbers and relations. Comb. Math., Proceedings of the International Conference, Camberra 1977, Lecture Notes in Mathematics 686. Springer, Berlin, 267-276.; Rogers, D.G., Shapiro, L.W., 1978. Some correspondence involving the Schröder numbers and relations. Comb. Math., Proceedings of the International Conference, Camberra 1977, Lecture Notes in Mathematics 686. Springer, Berlin, 267-276.
[21] Rogers, D. G., The enumeration of a family of ladder graphs part II: Schröder and superconnective relations, Quart. J. Math. Oxford (2), 31, 491-506 (1980) · Zbl 0451.05034
[22] Rogers, D.G., Shapiro, L.W., 1981. Deques, trees and lattice paths. Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference. Lecture Notes in Mathematics, vol. 882. Springer, Berlin, 293-303.; Rogers, D.G., Shapiro, L.W., 1981. Deques, trees and lattice paths. Combinatorial Mathematics VIII: Proceedings of the Eighth Australian Conference. Lecture Notes in Mathematics, vol. 882. Springer, Berlin, 293-303. · Zbl 0469.05005
[23] Riordan, J., Combinatorial Identities (1968), Wiley: Wiley New York · Zbl 0194.00502
[24] de Segner, A., Enumeratio modorum, quibus figurae planae rectilineae per diagonales dividuntur in triangula, Novi Commentarii academiae scientiarum Petropolitanae, 7, 203-209 (17581759)
[25] Schröder, E., Vier Kombinatorische Probleme, Z. Math. Phys., 15, 361-376 (1870)
[26] Shapiro, L. W.; Sulanke, R. A., Bijections for the Schröder numbers, Math. Mag., 71, 369-376 (2000)
[27] Stanley, R. P., Hipparchus, Plutarch, Schröder and Hough, Am. Math. Monthly, 104, 344-350 (1997) · Zbl 0873.01002
[28] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001
[29] Sulanke, R. A., A symmetric variation of a distribution of Kreweras and Poupard, J. Stat. Plan. Inference, 34, 291-303 (1993) · Zbl 0771.05013
[30] Sulanke, R. A., Catalan Path Statistics Having the Narayana distribution, Discrete Math., 180, 369-389 (1998) · Zbl 0896.05002
[31] Sulanke, R. A., Bijective recurrences concerning Schröder paths, Electron. J. Combin., 5, 1 (1998) · Zbl 0913.05007
[32] Sulanke, R. A., Constraint sensitive catalan path statistics having the Narayana distribution, Discrete Math., 204, 397-414 (1999) · Zbl 0936.05004
[33] Sulanke, R. A., Three recurrences for parallelogram polyominoes, J. Diff. Equations Appl., 5, 155-176 (1999) · Zbl 0924.05017
[34] Zeilberger, D., Six etudes in generating functions, Int. J. Comput. Math., 29, 201-215 (1989) · Zbl 0689.05003
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.