Riordan paths and derangements

DOI10.1016/J.DISC.2007.05.001zbMATH Open1147.05008arXivmath/0602298OpenAlexW2108437740MaRDI QIDQ2483401FDOQ2483401

Authors: William Y. C. Chen, Eva Y. P. Deng, Laura L. M. Yang 

Publication date: 28 April 2008

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

Abstract: Riordan paths are Motzkin paths without horizontal steps on the x-axis. We establish a correspondence between Riordan paths and $$-avoiding derangements. We also present a combinatorial proof of a recurrence relation for the Riordan numbers in the spirit of the Foata-Zeilberger proof of a recurrence relation on the Schr"oder numbers.

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

Recommendations

• Paths, chains, and antipaths
• The square of paths and cycles
• Riordan group involutions
• Rainbow paths
• The Rado path decomposition theorem
• LABYRINTH CHAOS
• The model of paths
• Meanders, knots, labyrinths and mazes
• On the rainbow Turán number of paths

zbMATH Keywords

(321,3\(\bar 1\)42)-avoiding derangementRiordan numberRiordan path

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Paths and cycles (05C38)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Catalan, Motzkin, and Riordan numbers
• A classic proof of a recurrence for a very classical sequence
• Motzkin numbers
• Motzkin paths and reduced decompositions for permutations with forbidden patterns
• A general bijective algorithm for trees.
• Bijective recurrences concerning Schröder paths
• A bijection between ordered trees and 2-Motzkin paths and its many consequences
• Bijective recurrences for Motzkin paths
• Three recurrences for parallelogram polyominoes

Cited In (5)

• Title not available (Why is that?)
• Pattern avoidance of generalized permutations
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Disjoint compatibility graph of non-crossing matchings of points in convex position
• Semiorders and Riordan numbers

Uses Software

• OEIS

This page was built for publication: Riordan paths and derangements

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