컨텐츠 시작
학술대회/행사
초록검색
제출번호(No.) | 0079 |
---|---|
분류(Section) | Poster Session |
분과(Session) | Mathematics for Information Sciences (IS) |
영문제목 (Title(Eng.)) |
Lattice path counting with a bounded strip restriction |
저자(Author(s)) |
Kwangsoo Park1, Gi-Sang Cheon1 Sungkyunkwan University1 |
초록본문(Abstract) | We consider a path from the origin to the point $(dn,0)$ using the step set $S=\{(a,0),(b,1),(c,-1)\}$ for which the path cannot go below the line $y=-\alpha$ where $a,b,c\in \mathbb{N}$, $d:=gcd(a,b,c)$, $\alpha\in \mathbb{N}_0$. The number counted is denoted by $\phi_n^{(\alpha)}(a,b,c)$. This generalizes a classical counting problem. For instance, $\phi_n^{(0)}(1,1,1)$ and $\phi_{2n}^{(0)}(2,1,1)$ are the same as the $n$th Motzkin number and the $n$th Schr\"oder number, respectively. In this paper, we obtain the generating function for the numbers $\phi_n^{(\alpha)}(a,b,c)$. In particular, if $\alpha=0$ and $a=1$ then for any positive integers $b$ and $c$ we obtain $$\phi_n^{(0)}(1,b,c)=\sum_{k=0}^{\lfloor {n\over{b+c}} \rfloor} {{n-(b+c-2)k}\choose{2k}}c_k.$$ where $c_n$ denotes the $n$th Catalan number. Further we give a combinatorial proof for the following open questions posed by R. J. Mathar in 2012; \begin{eqnarray*} Q1.(n+3)a_n+(-2n-3)a_{n-1}+na_{n-2}+2(-2n+3)a_{n-3}=0 \end{eqnarray*} where $a_n=\phi_n^{(0)}(1,2,1)$. \begin{eqnarray*} Q2.(n+4)b_n+(n+4)b_{n-1}-(5n+8)b_{n-2}+3nb_{n-3}+4(2-n)b_{n-4}+12(3-n)a_{n-5}=0 \end{eqnarray*} where $b_n=\phi_n^{(0)}(1,3,1)$. The concept of Riordan matrix is extensively used throughout this paper. |
분류기호 (MSC number(s)) |
05A15 |
키워드(Keyword(s)) | lattice path, Riordan matrix |
강연 형태 (Language of Session (Talk)) |
Korean |