Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Electronic Journal o...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Electronic Journal of Combinatorics
Article . 1998 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 1998
Data sources: zbMATH Open
DBLP
Article . 1998
Data sources: DBLP
versions View all 3 versions
addClaim

Lattice Paths Between Diagonal Boundaries

Lattice paths between diagonal boundaries
Authors: Heinrich Niederhausen;

Lattice Paths Between Diagonal Boundaries

Abstract

A bivariate symmetric backwards recursion is of the form $d[m,n]=w_{0}(d[m-1,n]+d[m,n-1])+\omega_{1}(d[m-r_{1},n-s_{1}]+d[m-s_{1},n-r_{1}])+\dots+\omega_{k}(d[m-r_{k},n-s_{k}]+d[m-s_{k},n-r_{k}])$ where $\omega_{0},\dots\omega_{k}$ are weights, $r_{1},\dots r_{k}$ and $s_{1},\dots s_{k}$ are positive integers. We prove three theorems about solving symmetric backwards recursions restricted to the diagonal band $x+u < y < x-l$. With a solution we mean a formula that expresses $d[m,n]$ as a sum of differences of recursions without the band restriction. Depending on the application, the boundary conditions can take different forms. The three theorems solve the following cases: $d[x+u,x]=0$ for all $x\geq0$, and $d[x-l,x]=0$ for all $x\geq l$ (applies to the exact distribution of the Kolmogorov-Smirnov two-sample statistic), $d[x+u,x]=0$ for all $x\geq0$, and $d[x-l+1,x]=d[x-l+1,x-1]$ for $x\geq l$ (ordinary lattice paths with weighted left turns), and $d[y,y-u+1]=d[y-1,y-u+1]$ for all $y\geq u$ and $d[x-l+1,x]=d[x-l+1,x-1]$ for $x\geq l$. The first theorem is a general form of what is commonly known as repeated application of the Reflection Principle. The second and third theorem are new; we apply them to lattice paths which in addition to the usual North and East steps also make two hook moves, East-North-North and North-East-East. Hook moves differ from knight moves (covered by the first theorem) by being blocked by any piece of the barrier they encounter along their three part move.

Related Organizations
Keywords

lattice paths, Exact enumeration problems, generating functions, symmetric backwards recursion, boundary

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    6
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
6
Average
Average
Average
gold