کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1148377 957831 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Lattice and Schröder paths with periodic boundaries
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Lattice and Schröder paths with periodic boundaries
چکیده انگلیسی
We consider paths in the plane with (1,0), (0,1), and (a,b)-steps that start at the origin, end at height n, and stay strictly to the left of a given non-decreasing right boundary. We show that if the boundary is periodic and has slope at most b/a, then the ordinary generating function for the number of such paths ending at height n is algebraic. Our argument is in two parts. We use a simple combinatorial decomposition to obtain an Appell relation or “umbral” generating function, in which the power zn is replaced by a power series of the form znφn(z), where φn(0)=1. Then we convert (in an explicit way) the umbral generating function to an ordinary generating function by solving a system of linear equations and a polynomial equation. This conversion implies that the ordinary generating function is algebraic. We give several concrete examples, including an alternative way to solve the tennis ball problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Statistical Planning and Inference - Volume 139, Issue 6, 1 June 2009, Pages 2014-2027
نویسندگان
, , , ,