Counting humps in Motzkin paths

DOI10.1016/J.DAM.2011.08.018zbMATH Open1236.05011DBLPjournals/dam/DingD12arXiv1109.2661OpenAlexW1999722679WikidataQ60692135 ScholiaQ60692135MaRDI QIDQ765354FDOQ765354

Authors: Yun Ding, Rosena R. X. Du 

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: In this paper we study the number of humps (peaks) in Dyck, Motzkin and Schr"{o}der paths. Recently A. Regev noticed that the number of peaks in all Dyck paths of order $n$ is one half of the number of super Dyck paths of order $n$. He also computed the number of humps in Motzkin paths and found a similar relation, and asked for bijective proofs. We give a bijection and prove these results. Using this bijection we also give a new proof that the number of Dyck paths of order $n$ with $k$ peaks is the Narayana number. By double counting super Schr"{o}der paths, we also get an identity involving products of binomial coefficients.

Full work available at URL: https://arxiv.org/abs/1109.2661

Recommendations

• Enumerations of humps and peaks in \((k, a)\)-paths and \((n, m)\)-Dyck paths via bijective proofs
• Counting humps and peaks in generalized Motzkin paths
• Bijective counting of humps and peaks in \((k, a)\)-paths
• Counting Dyck paths with strictly increasing peak sequences
• A bijection on Dyck paths and its consequences

zbMATH Keywords

Dyck pathsbinomial coefficientsNarayana numberpeaksMotzkin pathshumpsSchröder pathsdouble counting super-Schröder paths

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Factorials, binomial coefficients, combinatorial functions (05A10)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Dyck path enumeration
• Title not available (Why is that?)
• Statistics on Dyck paths
• The method of creative telescoping
• Dyck paths with no peaks at height \(k\)
• Title not available (Why is that?)

Cited In (9)

• Motzkin paths, Motzkin polynomials and recurrence relations
• Standard Young tableaux in a \(( 2 , 1 )\)-hook and Motzkin paths
• Counting humps and peaks in generalized Motzkin paths
• Bijective counting of humps and peaks in \((k, a)\)-paths
• Enumerations of humps and peaks in \((k, a)\)-paths and \((n, m)\)-Dyck paths via bijective proofs
• Counting Dyck paths with strictly increasing peak sequences
• Enumerating symmetric pyramids in Motzkin paths
• Analytic combinatorics of lattice paths with forbidden patterns: asymptotic aspects and Borges's theorem
• Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata

Uses Software

• OEIS

This page was built for publication: Counting humps in Motzkin paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765354)