Some Results on Enumeration of Schröder Pa-

ths with Flaws

 

Sen-Peng Eu and Tung-Shan Fu

Department of Applied Mathematics, National University of Kaohsiung, Kaohsiung, Taiwan

Mathematics Faculty, National Pingtung Institute of Commerce, Pingtung 900, Taiwan

speu@nuk.edu.tw tsfu@npic.edu.tw

 

Abstract.      Full Text PDF

 

Lattice paths associated with the Schröder numbers
 and the small Schröder numbers
 are investigated to derive the Taylor expansions of their generating functions  and . Among many other interpretations, the -th Schröder number  counts the number of lattice paths in the plane  times  from  to  with the north , east  and diagonal  steps that never pass below the line . Such paths are called -Schröder paths. Note that the terms of  are twice of those in . Consequently, the -th small Schröder number  counts the number of -Schröder paths without diagonal steps on the line  for . By a Taylor expansion, a generating function is expanded in a form the remainder part of which is expressed as a functional of the generating function itself. In fact, the -th Taylor expansion of  can be expressed in the form  and the coefficients of the polynomial  are determined. This result is applied to an enumeration problem of Schröder paths with flaws, i.e., some steps of the paths pass below the line . A neat formula for enumerating Schröder paths with flaws is obtained, which is evaluated simply in terms of  and . Meanwhile, some interesting bijections between certain sets of paths are established.