Deux propriétés combinatoires des nombres de Schröder. (Two combinatorial properties of Schröder numbers).(French)Zbl 0669.05002

We establish that the Schröder number $$R_ n=\sum^{n}_{i=0}\left( \begin{matrix} 2n-i\\ i\end{matrix} \right)C_{n-i}$$ (where $$C_ n$$ is the Catalan number $$(2n)!/n!(n+1)!)$$ satisfies the formula: $$R_{n+1}=2\sum^{\lfloor n/2\rfloor}_{i=0}3^{n-2i}2^ i\left( \begin{matrix} n\\ 2i\end{matrix} \right)C_ i$$. As a corollary we prove that $$(R_ nR_{n+2}-R_{n+1}R_{n+1})/2$$ counts a family of coloured lattice paths. Proofs are purely bijective and use intermediate objects as trees and paths in the plane.

MSC:

 05A15 Exact enumeration problems, generating functions
Full Text:

Online Encyclopedia of Integer Sequences:

Large Schröder numbers (or large Schroeder numbers, or big Schroeder numbers).

References:

 [1] 1. R. ALTER, Some Remarks and Results on Catalan Numbers, in Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, 1971, p. 109-132. Zbl0299.05002 MR329910 · Zbl 0299.05002 [2] 2. W. G. BROWN, Historical Note on a Recurrent Combinatorial Problem, Amer. Math. Monthly, vol.72, 1965, p. 973-977. Zbl0136.21204 MR1533479 · Zbl 0136.21204 [3] 3. L. COMTET, Advanced Combinatorics, D. Reidel publ. comp., Boston, 1974, p. 56. Zbl0283.05001 MR460128 · Zbl 0283.05001 [4] 4. R. DONAGHEY, Restricted Plane Tree Representations of Four Motzkin-Catalan Equations, J.C.T., Ser. B, 22, 1977, p. 114-121. Zbl0352.05028 MR432532 · Zbl 0352.05028 [5] 5. R. DONAGHEY, Automorphisms on Catalan Trees and Bracketings, J.C.T., Ser. B, 29, 1980, p. 75-90. Zbl0463.05038 MR584162 · Zbl 0463.05038 [6] 6. R. DONAGHEY et L. W. SHAPIRO, Motzkin Numbers, J.C.T., Ser. A, 23, 1977, p. 291-301. Zbl0417.05007 MR505544 · Zbl 0417.05007 [7] 7. W. J. R. EPLETT, A Note About the Catalan Triangle, Discrete Math., vol. 25, 1979, p. 289-291. Zbl0393.05014 MR534947 · Zbl 0393.05014 [8] 8. P. FLAJOLET, Combinatorial Aspects of Continued Fractions, Discrete Math., vol. 32, 1980, p. 125-161. Zbl0445.05014 MR592851 · Zbl 0445.05014 [9] 9. I. GESSEL, A. Non Commutative Generalization of q-Analog of the Lagrange Inversion Formula, Trans. Amer. Math. Soc., vol. 257, 1980, p. 455-481. Zbl0459.05014 MR552269 · Zbl 0459.05014 [10] 10. I. M. GESSEL et G. VIENNOT, Binomials Determinants, Paths and Hook Length Formulae, Advance in Maths., vol. 58, 1985, p. 300-321. Zbl0579.05004 MR815360 · Zbl 0579.05004 [11] 11. H. W. GOULD, Research Bibliography of Two Special Number Sequences, rev. ed., Combinatorial Research Institute, Morgantown, W. Va., 1977. Zbl0327.10001 MR401633 · Zbl 0327.10001 [12] 12. D. GOUYOU-BEAUCHAMPS, Deux propriétés combinatoires du langage de Lukasiewicz, R.A.I.R.O, vol. 3, 1975, p. 13-24. Zbl0337.05010 MR395351 · Zbl 0337.05010 [13] 13. D. GOUYOU-BEAUCHAMPS, Chemins sous-diagonaux et tableaux de Young, in Combinatoire énumérative, p. 112-125, Lecture Notes in Math., n^\circ 1234, G. LABELLE et P. LEROUX éd., Springer-Verlag, Berlin, 1986. Zbl0611.05003 MR927762 · Zbl 0611.05003 [14] 14. D. GOUYOU-BEAUCHAMPS et G. VIENNOT, Equivalence of the Two-Dimensional Directed Animal Problem to a One-Dimensional Path Problem, in Adv. in Appl. Math. (à paraître). Zbl0727.05036 MR956559 · Zbl 0727.05036 [15] 15. W. B. JONES et W. J. THRON, Continued Fractions, Analytic Theory and Applications, Encyclopedia of Math. and its Appl., vol. 11, G. C. ROTA éd., Addison-Wesley, Reading, 1980. Zbl0603.30009 MR595864 · Zbl 0603.30009 [16] 16. C. JORDAN, Calculus of Finites Differences, Chelsea Publishing Company, New York, 1950, p. 449. Zbl0154.33901 MR183987 · Zbl 0154.33901 [17] 17. D. A. KLARNER, Correspondance Between Plane Trees and Binary Sequences, J.C.T., vol. 9, 1970, p. 401-411. Zbl0205.54702 MR292690 · Zbl 0205.54702 [18] 18. D. E. KNUTH, The art of Computer Programming, vol. 1, Fundamental Algorithms, 2nd ed., Addison Wesley, Reading, Ma., 1973, p. 235-239 et 533-534. MR378456 [19] 19. G. KREWERAS, Sur les éventails de segments, Cahiers du B.U.R.O., vol. 15, 1970, p. 3-41. [20] 20. G. KREWERAS, Sur les partitions non croisées d’un cycle, Discrete Mathematics, vol. 1, n^\circ 4, 1972, p. 333-350. Zbl0231.05014 MR309747 · Zbl 0231.05014 [21] 21. G. KREWERAS, Sur les hiérarchies de segments, Cahiers du B.U.R.O., vol. 20, 1973, p. 3-61. [22] 22. G. KREWERAS, Aires des chemins surdiagonaux à étapes obliques permises, Cahiers du B.U.R.O., vol. 24, 1976, p. 9-18. [23] 23. L. MOSER et W. ZAYACHKOWSKI, Lattice Paths with Diagonal Steps, Scripta math., vol. 26, 1963, p. 223-229. Zbl0111.24105 MR150064 · Zbl 0111.24105 [24] 24. T. MOTZKIN, Relation Between Hypersurface Cross Ratio and a Combinatorial Formula for Partitions of a Polygon, for Permanent Preponderance and for Non-Associative Products, Bul. Amer. Math. Soc., vol. 54, 1948, p. 352-360. Zbl0032.24607 MR24411 · Zbl 0032.24607 [25] 25. G. POLYA, On the Number of Certain Lattice Polygons, J. Comb. Theory, vol. 6, 1969, p. 102-105. Zbl0327.05010 MR236031 · Zbl 0327.05010 [26] 26. J. RIORDAN, Combinatorial Identities, Wiley, New York, 1968, p. 148 Zbl0194.00502 MR231725 · Zbl 0194.00502 [27] 27. J. RIORDAN, Enumeration of Plane Trees by Branchs and Endpoints, J.C.T., Ser. A, 19, 1975, p. 214-222. Zbl0308.05115 MR409241 · Zbl 0308.05115 [28] 28. J. RIORDAN, The Distribution of Crossing of Chords Joining Pairs of 2n Points on a Circle, Math. Comput., vol. 29, 1975, p. 215-222. Zbl0319.05004 MR366686 · Zbl 0319.05004 [29] 29. D. G. ROGERS, A Schröder Triangle: Three Combinatorial Problems, Comb. Math. V: Proc. Fifth Aust. Conf., Lecture Notes in Math., 622, Springer-Verlag, Berlin, 1977. Zbl0368.05004 MR462964 · Zbl 0368.05004 [30] 30. D. G. ROGERS, The Enumeration of a Family of Ladder Graphs Part I: Connective Relations, Quart. J. Math. Oxford, (2), 28, 1977, p. 421-431. Zbl0373.05045 MR491365 · Zbl 0373.05045 [31] 30. D. G. ROGERS, The Enumeration of a Family of Ladder Graphs Part II: Schröder and Superconnective Relations, Quart. J. Math. Oxford, (2),31, 1980, p. 491-506. Zbl0451.05034 MR596981 · Zbl 0451.05034 [32] 32. D. G. ROGERS, Pascal Triangles, Catalan Numbers and Renewal Arrays, Discrete Math., vol. 22, 1978, p. 301-310. Zbl0398.05007 MR522725 · Zbl 0398.05007 [33] 33. D. G. ROGERS et L. W. SHAPIRO, Some Correspondance Involving the Schröder Numbers and Relations, in Comb. Math., Proc. of the Intern. Conf., Camberra, 1977, Lecture Notes in Math., vol. 686, Springer-Verlag, Berlin, 1978, p. 267-276. MR526754 [34] 34. D. G. ROGERS et L. W. SHAPIRO, Deques, Trees and Lattice Paths, in Comb. Math. VIII Proc., Geelong, Australia, 1980, Lecture Notes in Math., vol. 884, Springer-Verlag, Berlin, 1981, p. 293-303. Zbl0469.05005 MR641254 · Zbl 0469.05005 [35] 35. L. W. SHAPIRO, A Short Proof of an Identity of Touchard’s Concerning Catalan Numbers, J.C.T., Ser. A, 20, 1976, p. 375-376. Zbl0337.05012 MR406819 · Zbl 0337.05012 [36] 36. L. W. SHAPIRO, A Catalan Triangle, Discrete Math., vol. 14, 1976, p. 83-90. Zbl0323.05004 MR387069 · Zbl 0323.05004 [37] 37. SCHRÖDER, Vier Kombinatorische Probleme, Z. fur M. Phys., 15, 1870, p. 361-376. [38] 38. N. J. A. SLOANE, A Handbook of Integer Sequences, Academic Press, New York, 1973. Zbl0286.10001 MR357292 · Zbl 0286.10001 [39] 39. R. G. STANTON et D. D. COWAN, Note on a ”Square” Functional Equation, S.I.A.M. Review, vol. 12, n^\circ 2, 1970, p. 277-279. Zbl0206.29301 MR260602 · Zbl 0206.29301 [40] 40. J. TOUCHARD, Sur certaines équations fonctionnelles, in Proc. Inter. Congr. Mat., p. 465-472, Univ. of Toronto Press, Toronto, 1928. JFM54.0440.03 · JFM 54.0440.03 [41] 41. M. VAUCHAUSSADE DE CHAUMONT et G. VIENNOT, Polynômes orthogonaux et problèmes d’énumération en biologie moléculaire, Proc. Séminaire Lotharingien, Sainte-Croix-aux-Mines, mai 1983. Zbl0977.33500 · Zbl 0977.33500 [42] 42. M. VAUCHAUSSADE DE CHAUMONT et G. VIENNOT, Enumeration of RNAs secondary structure by complexity, in Mathematics in Medecine and Biology, V. CAPASSO, E. GROSSO and S. L. PAVEN-FONTANA éd., Lecture Notes in Biomath., n^\circ 57, Springer-Verlag, Berlin, 1985, p. 360-365. Zbl0579.92012 · Zbl 0579.92012 [43] 43. G. VIENNOT, Une théorie combinatoire des polynômes orthogonaux généraux, 217 p., Astérisque, Soc. Math. France (à paraître). [44] 44. G. VIENNOT, Une théorie combinatoire des approximants de Padé, Réunion d’été de la Soc. Math, du Can., Québec, juin 1985, rapport Bordeaux, n^\circ 8611. [45] 45. G. VIENNOT, Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki, 36e année, 1983/1984. exposé n^\circ 626, in Astérisque, Soc. Math. France, n^\circ 121-122, 1985, p. 225-246. Zbl0563.60095 MR768962 · Zbl 0563.60095
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.