\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
The Lagrange Inversion Formula and \\
\vskip .1in
Divisibility Properties
}
\vskip 1cm
\large
Wen-jin Woan\footnote{Author's current address: 
2103 Opal Ridge, Vista, CA 92081, USA.} \\
Howard University \\
Washington, DC 20059 \\
USA\\
\href{mailto:wjwoan@sbcglobal.net}{\tt wjwoan@sbcglobal.net} \\
\end{center}

\vskip .2 in

\begin{abstract}
Wilf stated that the Lagrange inversion formula (LIF) is a remarkable tool for
solving certain kinds of functional equations, and at its best it can give
explicit formulas where other approaches run into stone walls. Here we
present the LIF combinatorially in the form of lattice paths,
and apply it to the
divisibility property of the coefficients of a formal power series expansion.
For the LIF, the coefficients are in a commutative ring with identity.
As for divisibility, we require the coefficients to be in a principal ideal
domain.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}





\newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{%
defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{remar}[theorem]{Remark} \newenvironment{remark}{\begin{remar}%
\normalfont\quad}{\end{remar}} \newtheorem{algo}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{algo}\normalfont\quad}{\end{algo}}

\definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} %
\setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} %
\setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} %
\setlength{\textheight}{8.9in}

\section{Introduction}

Wilf \cite{HW} stated that the Lagrange inversion formula (LIF) is a remarkable
tool for solving certain kinds of functional equations, and at its best it
can give explicit formulas where other approaches run into stone walls. Here
we present the LIF combinatorially in the form of lattice paths and apply it
to the
divisibility property of the coefficients of formal power series expansion.\
For the LIF the coefficients are in a commutative ring with identity.
As for
divisibility, we require the coefficients to be in a principal ideal
domain (PID).

We consider those weighted lattice paths in the Cartesian plane beginning at
$(0,0)$ and proceeding with weighted steps from $S=\{w_{-m}=(1,-m),$ $%
m=-1,0,1,2,...\},$ where $w_i$ represents the step and also the weight. We
normalize the weight by setting $w_1=1$ and let $w(y)=\sum_{i\leq 1}w_iy^i$
be the $weight\;generating\;function.\;$Let $p(x)=x(w(x^{-1}))=\sum
w_ix^{1-i}=1+w_0x+w_{-1}x^2+w_{-2}x^3+...$ be the $weight\;formal\;power%
\;series$. The weight of a lattice path is the product of the weights of the
steps. Let $A(n,k)$ be the set of all weighted lattice paths ending at the
point $(n,k)$ (the terminal point) and for $k>0$, let $B(n,k)\subset A(n,k)$
denote the set of paths that stay above the $x$-axis except the initial
point. Let $a_{n,k}=w(A(n,k))$ be the sum of the weights of all paths in $%
A(n,k)$ and $b_{n,k}=w(B(n,k))$ be the sum of the weights of all paths in $%
B(n,k)$. Note that the generating function of the $n^{th}$ row of $(a_{n,k})$
is $w(y)^n,$ i.e.,
$a_{n,k}=[y^k](w(y))^n=\sum_{i\leq 1}w_ia_{n-1,(k-1)+1-i},$
where the summation represents the partition of the paths in $%
A(n,k)$ by the positions preceding to the last step.$\;$ 
Similarly we can write
$b_{n,k}=\sum_{i\leq 1}w_ib_{n-1,(k-1)+1-i},\;$for\ $k>0.$

In combinatorics the weights are non-negative integers, and $a_{n,k}\;$
count the number of colored paths.

\section{Some Examples}

\begin{example}
\label{one}$w_1=w_{-1}=1$ and $w_i=0,$ otherwise. Then $%
w(y)=y+y^{-1}=y(1+y^{-2}),\;p(x)=1+x^2$ and $a_{n,k}=\binom{2m+k}m\;$is the
binomial coefficient, where $n=2m+k$. Some entries of $(a_{n,k})$ and $%
(b_{n,k})$ are as follows:
\end{example}

\[
(a_{n,k})\rightarrow \left[
\begin{array}{cccccccccccc}
n\backslash k & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 1 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & 3 & 0 & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
4 & 4 & 0 & 6 & 0 & 4 & 0 & 1 & 0 & 0 & 0 & 0 \\
5 & 0 & 10 & 0 & 10 & 0 & 5 & 0 & 1 & 0 & 0 & 0 \\
6 & 15 & 0 & 20 & 0 & 15 & 0 & 6 & 0 & 1 & 0 & 0 \\
7 & 0 & 35 & 0 & 35 & 0 & 21 & 0 & 7 & 0 & 1 & 0 \\
8 & 56 & 0 & 70 & 0 & 56 & 0 & 28 & 0 & 8 & 0 & 1
\end{array}
\right] ,
\]

$\ $

\[
(b_{n,k})\rightarrow \left[ \
\begin{array}{cccccccccc}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
4 & 0 & 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 \\
5 & 0 & 2 & 0 & 3 & 0 & 1 & 0 & 0 & 0 \\
6 & 0 & 0 & 5 & 0 & 4 & 0 & 1 & 0 & 0 \\
7 & 0 & 5 & 0 & 9 & 0 & 5 & 0 & 1 & 0 \\
8 & 0 & 0 & 14 & 0 & 14 & 0 & 6 & 0 & 1
\end{array}
\right] .
\]

\begin{example}
\label{two}$w_i=1\;$for $i=1,0,-1$ and $0,$ otherwise. In this example $%
w(y)=y+1+y^{-1}=y(1+y^{-1}+y^{-2}),$ $p(x)=1+x+x^2\;$and $(a_{n,k})\;$are
the trinomial coefficients. Some entries of $(a_{n,k})$ and $(b_{n,k})$ are
as follows:
\end{example}

\[
(a_{n,k})\rightarrow \left[
\begin{array}{cccccccccc}
n\backslash k & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
2 & 1 & 2 & 3 & 2 & 1 & 0 & 0 & 0 & 0 \\
3 & 3 & 6 & 7 & 6 & 3 & 1 & 0 & 0 & 0 \\
4 & 10 & 16 & 19 & 16 & 10 & 4 & 1 & 0 & 0 \\
5 & 30 & 45 & 51 & 45 & 30 & 15 & 5 & 1 & 0 \\
6 & 90 & 126 & 141 & 126 & 90 & 50 & 21 & 6 & 1
\end{array}
\right] .
\]

The generating function of $\ $row 5 is$\;w(y)^5=(y(1+y^{-1}+y^{-2})\
)^5=y^{-5}+5y^{-4}+15y^{-3}+30y^{-2}+45y^{-1}+51+45y+30y^2+15y^3+5y^4+y^5,$

\[
(b_{n,k})\rightarrow \left[
\begin{array}{ccccccccc}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & 2 & 2 & 1 & 0 & 0 & 0 & 0 \\
4 & 0 & 4 & 5 & 3 & 1 & 0 & 0 & 0 \\
5 & 0 & 9 & 12 & 9 & 4 & 1 & 0 & 0 \\
6 & 0 & 21 & 30 & 25 & 14 & 5 & 1 & 0 \\
7 & 0 & 51 & 76 & 69 & 44 & 20 & 6 & 1
\end{array}
\right] .
\]

\begin{example}
\label{three}$w_1=1,\;w_0=3,\;w_{-1}=2$ and $0$ otherwise. In this example $%
w(y)=y+3+2y^{-1}\ =y(\ 1+3y^{-1}+2y^{-2})\;$and $p(x)=1+3x+2x^2$. Some
entries of $(a_{n,k})$ and $(b_{n,k})$ are as follows:
\end{example}

\[
(a_{n,k})\rightarrow \left[
\begin{array}{ccccccccc}
n\backslash k & -2 & -1 & 0 & 1 & 2 & 3 & 4 & 5 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 2 & 3 & 1 & 0 & 0 & 0 & 0 \\
2 & 4 & 12 & 13 & 6 & 1 & 0 & 0 & 0 \\
3 & 36 & 66 & 63 & 33 & 9 & 1 & 0 & 0 \\
4 & 248 & 360 & 321 & 180 & 62 & 12 & 1 & 0 \\
5 & 1560 & 1970 & 1683 & 985 & 390 & 100 & 15 & 1
\end{array}
\right] .
\]

The generating function of$\;$row 4 is $w(y)^4=(y+3+2y^{-1})^4\
=16y^{-4}+96y^{-3}+248y^{-2}+360y^{-1}+321+180y+62y^2+12y^3+y^4,$

\[
(b_{n,k})\rightarrow \ \left[
\begin{array}{ccccccccc}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 3 & 1 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & 11 & 6 & 1 & 0 & 0 & 0 & 0 \\
4 & 0 & 45 & 31 & 9 & 1 & 0 & 0 & 0 \\
5 & 0 & 197 & 156 & 60 & 12 & 1 & 0 & 0 \\
6 & 0 & 903 & 785 & 360 & 98 & 15 & 1 & 0 \\
7 & 0 & 4279 & 3978 & 2061 & 684 & 145 & 18 & 1
\end{array}
\right] .
\]

Note that $(b_{n,1})\;$is the Schr\"oder sequence of the first kind.

\begin{example}
\label{four}Let $w_i=2-i$ for $i\leq 1$. Then $%
w(y)=y(1+2y^{-1}+3y^{-2}+4y^{-3}+...)\ $ and some entries of $(a_{n,k})$ and
$(b_{n,k})$ are as follows:
\end{example}

\[
(a_{n,k})\rightarrow \left[
\begin{array}{ccccccc}
n\backslash k & -2 & -1 & 0 & 1 & 2 & 3 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 \\
1 & 4 & 3 & 2 & 1 & 0 & 0 \\
2 & 35 & 20 & 10 & 4 & 1 & 0 \\
3 & 252 & 126 & 56 & 21 & 6 & 1 \\
4 & 1716 & 792 & 330 & 120 & 36 & 8 \\
5 & 11440 & 5005 & 2002 & 715 & 220 & 55 \\
6 & 75582 & 31824 & 12376 & 4368 & 1365 & 364 \\
7 & 497420 & 203490 & 77520 & 27132 & 8568 & 2380
\end{array}
\right] .
\]

The generating function of row 4 is $w(y)^4\ $with coefficients the same as $%
\;p(x)^4=(\frac
1{(1-x)^2})^4=1+8x+36x^2+120x^3+330x^4+792x^5+1716x^6+3432x^7+6435x^8+O%
\left( x^9\right) ,$

\[
(b_{n,k})\rightarrow \left[
\begin{array}{ccccccccc}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & 7 & 4 & 1 & 0 & 0 & 0 & 0 \\
4 & 0 & 30 & 18 & 6 & 1 & 0 & 0 & 0 \\
5 & 0 & 143 & 88 & 33 & 8 & 1 & 0 & 0 \\
6 & 0 & 838 & 455 & 182 & 52 & 10 & 1 & 0 \\
7 & 0 & 4096 & 2558 & 1020 & 320 & 75 & 12 & 1
\end{array}
\right] .
\]

$\ $

\begin{example}
Let $w_1=1$ and $w_i=2\ \ $for $i\leq 0.$ Then $%
w(y)=y(1+2y^0+2y^{-1}+2y^{-2}+...+2y^{-n}+...)$ and $p(x)=\frac{1+x}{1-x}$.
Some entries of $(a_{n,k})$ and $(b_{n,k})$ are as follows:

$\ $

\[
(a_{n,k}\ )\rightarrow \ \left[
\begin{array}{cccccccc}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\
2 & 8 & 4 & 1 & 0 & 0 & 0 & 0 \\
3 & 38 & 18 & 6 & 1 & 0 & 0 & 0 \\
4 & 192 & 88 & 32 & 8 & 1 & 0 & 0 \\
5 & 1002 & \ 450 & \ 170 & 50 & 10 & 1 & 0
\end{array}
\right] ,
\]

\[
(b_{n,k})\rightarrow \left[
\begin{array}{cccccccc}
n\backslash k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 \\
3 & 0 & 6 & 4 & 1 & 0 & 0 & 0 \\
4 & 0 & 22 & 16 & 6 & 1 & 0 & 0 \\
5 & 0 & \ 90 & \ 68 & 30 & 8 & 1 & 0 \\
6 & 0 & 394 & 304 & 146 & 48 & 10 & 1
\end{array}
\right] .
\]

Note that $(b_{n,1})\;$is the large Schr\"oder sequence.\ For some of the
above examples please refer to \cite{RS}.
\end{example}

\section{Main Theorems}

Please refer to \cite{FS,MRSV} for the following remark.

\begin{remark}
\label{eight} Let $A_k(x)=\sum a_{n,k}x^n\;$be the generating function of\
the $k^{th\;}$column of $(a_{n,k})_{n\geq k\geq 0}$ and$\;B_k(x)=\sum
b_{n,k}x^n\;$be the generating function of\ the $k^{th\;}$column of $%
(b_{n,k})_{n\geq k}.\;$Let $g=g(x)=A_0(x)$\ and $f=f(x)=B_1(x).\;$The
following generating functions correspond to Examples \ref{one}, \ref{two},
\ref{three}.

\setlength{\unitlength}{.8cm}

\begin{picture} (10,6)

\put(0,1){\line(0,1){4}}

\put(3.0,1){\line(0,1){4}}\put(6.2,1){\line(0,1){4}}\put(8.8,1){\line(0,1){4}}\put(12.4,1){\line(0,1){4}}

\put(0,1){\line(1,0){19}}

\put(0.1,1.3){$1+3x+2x^2$}

\put(0.5,4.3){$p(x)$} \put(3.7,4.3){$f(x)$}\put(6.5,4.3){$g(x)$}\put(9.3,4.3){Sloane A}\put(12.7,4.3){Name}

\put(0.5,3.3){$1+x^2$} \put(3.7,3.3){$\frac{1-\sqrt{1-4x^2}}{2x}$}\put(6.3,3.3){$\frac
1{\sqrt{1-4x^2}}$}\put(9.0,3.3){000108,000984}\put(12.5,3.3){Catalan, Central binomial}

\put(0.5,2.3){$1+x+x^2$} \put(3.0,2.3){$\frac{1-x-\sqrt{1-2x-3x^2}}{2x}$}\put(6.3,2.3){$\frac
1{\sqrt{1-2x-3x^2}}$}\put(9.0,2.3){001006,002426}\put(12.5,2.3){Motzkin, Central trinomial}

 \put(3.0,1.3){$\frac{1-3x-\sqrt{1-6x+x^2}}{4x}$}\put(6.3,1.3){$\frac
1{\sqrt{1-6x+x^2}}$}\put(9.0,1.3){001003,001850}\put(12.5,1.3){Schr\"oder, Central Delannoy}


\put(0,2){\line(1,0){19}}

\put(0,3){\line(1,0){19}}\put(0,4){\line(1,0){19}}\put(0,5){\line(1,0){19}} \put(19,1){\line(0,1){4}}


 \end{picture}
.

Let $P\in A(n,k)$,\ find the last point on $P$ where the second coordinate
is of height $k-1$. This point splits $P$ into subpaths $F,B$ with $P=FB$,\
and $F\in A(j,k-1),\;$ $B\in B(n-j,1).\;\;$Then by induction and by the
convolution property,

$A_k(x)=(gf^{k-1})f=gf^{k\,},$\ $B_k(x)=(f^{k-1})f=f^k.$

From Introduction we have the recurrence relation

$b_{n,k}=\sum_{i\leq 1}w_ib_{n-1,(k-1)+1-i},\;$for\ $k>0.\;$Hence

$f(x)=\sum b_{n,1}x^n=\sum (\sum_{i\leq 1}w_ib_{n-1,\ 1-i})x^n=x(\sum_{i\leq
1}w_i(\sum b_{n-1,1-i}x^{n-1}))$

$=x(\sum_{i\leq 1}w_i\ f^{1-i}))=xp(f)\;$and $p(x)=\frac x{\overline{f}},\;$%
where $\overline{f}\;$is the inverse function of $f.$

The following theorem is the LIF (Wilf \cite{HW}).
\end{remark}

\begin{theorem}
\label{five}(LIF) Let $f(x)=x+\sum_{i=2}b_ix^i.\;$Then $[x^n](\overline{f}%
(x))^k=\frac kn[x^{n-k}](\frac x{f(x)})^n$, where $\overline{f}$ is the
inverse function of $f$.
\end{theorem}

The following theorem (The hitting time theorem in probability theory) is
the LIF in the form of lattice paths. A vast literature exists on this subject,
see, e.g., \cite{GS,FS,JW}. This result is well-known for 
$k=1$ in some special cases \cite{W,WW}.

\begin{theorem}
\label{six}For $0<k<n$, $nb_{n,k}=ka_{n,k}.$
\end{theorem}

We shall provide two proofs of Theorem \ref{six}. In the first proof we use
LIF to prove Theorem \ref{six} algebraically whereas in the second proof we
use lattice paths bijection to prove it combinatorially.

\noindent {\it First proof.} 
By Remark \ref{eight} and Theorem \ref{five} we obtain that
$b_{n,k}=[x^n]f^k=\frac kn[x^{n-k}](\frac x{\ \overline{f}(x)})^n=\frac
kn[x^{n-k}](p(x))^n=\frac kn[x^{-k}](w(\frac 1x))^n=\frac
kn[y^{k}](w(y))^n=\frac kna_{n,k}. $

\noindent{\it Second proof}.
We construct a bijection between the set of all pairs $(P,i)$
with $P\in A(n,k)$ and $i$ $\in \{0,1,2,3,...,k-1\}$ and the set of all
pairs $(Q,j)$ with $Q\in B(n,k)$ and $j\in [n]$, as follows: For $P\in
A(n,k) $ and $i$ $\in \{0,1,2,3,...,k-1\}$, let $l(P)$ be the second
coordinate of the lowest point of $P$ and let $j$ be the maximum element of $%
[n]$ such that the point $(j,i+l(P))\in P$. This point splits the path $P$
into two subpaths $F,B$ with $P=FB$.

We define $Q=BF$. Every point of $B$ in $Q$ (apart from the initial point)
lies above the $x$-axis, because of the maximality of $j$.

Moreover, every point of $F$ in $Q$ is elevated by$\;k-(l(P)+i)$ units, so
that the lowest point of $F$ in $Q$ has second coordinate equal to $%
l(P)+k-(l(P)+i)=k-i>0$ and hence $F$ lies above the $x$-axis. This shows
that $Q\in B(n,k)$.

Conversely, for $Q\in B(n,k)$ and $j\in [n]$, the\ $j^{th\;}$point (apart
from the initial point) of $Q\;$splits $Q$ into two subpaths $F,B$ with $%
Q=FB $. Note that in $Q\ ,0<l(B)\leq k,\ $thus $k=l(B)+i$ with $0\leq i<k.\;$%
We define $P=BF\in A(n,k);\ $ the $(n-j)^{th}\;$point of $P$\ splits $P$
into two subpaths $B,F$. Since the second coordinates of the points of $F\;$are\
larger than the second coordinate of the initial point of $F$, $n-j$ is the
maximum element in $[n]$ such that $(n-j,l(P)+i)\in P.\;$Hence the mapping $%
(Q,j)\rightarrow (P,i)\;$is the inverse of the above mapping.\

Note that the mappings involve only switching the steps, and hence they
preserve the weights.$\Box $

Let us use an example to illustrate the mapping in the above theorem.

For$%
\;P=w_{-3}w_0w_1w_1w_0w_{-1}w_1w_0w_1w_1w_1w_0w_1\in A(13,3),\;k=3,\;i=0,1,2$
we have respectively

\begin{center}
$(P,0)=w_{-3}w_0*w_1w_1w_0w_{-1}w_1w_0w_1w_1w_1w_0w_1\rightarrow $

$(Q,11)=w_1w_1w_0w_{-1}w_1w_0w_1w_1w_1w_0w_1*w_{-3}w_0$.

$(P,1)=w_{-3}w_0\ w_1w_1w_0w_{-1}*w_1w_0w_1w_1w_1w_0w_1\rightarrow $

$(Q,7)=w_1w_0w_1w_1w_1w_0w_1*w_{-3}w_0\ w_1w_1w_0w_{-1}$.

$(P,2)=w_{-3}w_0w_1w_1w_0w_{-1}w_1w_0*w_1w_1w_1w_0w_1\rightarrow $

$(Q,5)=w_1w_1w_1w_0w_1*w_{-3}w_0w_1w_1w_0w_{-1}w_1w_0$
\end{center}
where the symbol * marks the splitting point of each path.

Graphically, for the second pair of paths (i.e., for $i=1$) we have

\[
(P,1)=\left[
\begin{array}{cccccccccccccc}
&  &  &  &  &  &  &  &  &  &  &  &  & \circ \\
&  &  &  &  &  &  &  &  &  &  & \circ & \circ &  \\
&  &  &  &  &  &  &  &  &  & \circ &  &  &  \\
\times &  &  &  &  &  &  &  &  & \circ &  &  &  &  \\
&  &  &  & \circ & \circ &  & \circ & \circ &  &  &  &  &  \\
&  &  & \circ &  &  & \bullet &  &  &  &  &  &  &  \\
& \circ & \circ &  &  &  &  &  &  &  &  &  &  &
\end{array}
\right] \rightarrow
\]

\[
(Q,7)=\left[
\begin{array}{cccccccccccccc}
&  &  &  &  &  &  &  &  &  &  &  &  &  \\
&  &  &  &  &  &  & \bullet &  &  &  &  &  &  \\
&  &  &  &  & \circ & \circ &  &  &  &  & \circ & \circ &  \\
&  &  &  & \circ &  &  &  &  &  & \circ &  &  & \circ \\
&  &  & \circ &  &  &  &  & \circ & \circ &  &  &  &  \\
& \circ & \circ &  &  &  &  &  &  &  &  &  &  &  \\
\times &  &  &  &  &  &  &  &  &  &  &  &  &
\end{array}
\right]
\]
where $\times \;$\ marks the origin $(0,0).$

For the following divisibility properties please refer to \cite{BS,DS}.

\begin{corollary}
\label{seven} Let $d=g.c.d.(n,k).\;$Then for $0<k<n$

\it{(1) $\frac nd\;$divides $a_{n,k},$}

\it{(2) $\frac kd\;$divides $b_{n,k},$}

\it{(3) $g.c.d.(n,a_{n,k})>1.$}
\end{corollary}

\begin{corollary}
$a_{2n+1,1}=\left( _{\;\;n}^{2n+1}\right) =(2n+1)b_{2n+1,1}\;$ is odd if and
only if $n=2^m-1\;$for some $m.$
\end{corollary}

\begin{proof}
$b_{2n+1,1}=c_n\;$is the Catalan number. It is well known that the
Catalan number $c_n\;$is odd if and only if $n=2^m-1$.
\end{proof}

\begin{corollary}
\label{ten}If $n=p^m\;$for some $m$\ and prime $p$, then $p$ divides $%
a_{n,k} $ for $0<k<n.$
\end{corollary}

For the proof of the next result, it is enough to apply Corollary \ref{ten}
and use the fact that $a_{n,k}=a_{n-1,k-1}+w_0a_{n-1,k}+w_{-1}a_{n-1,k+1}.$

\begin{corollary}
\label{eleven}   If $n=p^m+1\;$for some prime $p\;$and $w_i=0\;$for $i<-1$,
then $p$ divides $a_{n,k}$ for $1<k<n-2.\;$
\end{corollary}

\begin{corollary}
\label{twelve} If $p^m$ divides $n\;$ for some $m$\ and prime $p$, then $p$
divides $b_{n,k}$ for $n\neq 0({mod}(p^m)).$
\end{corollary}

The following generalization of Corollary \ref{ten} can be proved by
applying Corollary \ref{seven}.

\begin{corollary}
\label{thirteen} If $p^m$ divides $n\;$ for some $m$ and prime $p$, then $p$
divides $a_{n,k}$ for $k\neq 0({mod}(p^m)).$
\end{corollary}

\begin{remark}
\label{fourteen} Let $A(x)=1+2x^1+3x^2+...\ =\left( \frac 1{1-x}\right) ^2\;$%
and $B(x)=xA(x)=x\left( \frac 1{1-x}\right) ^2$.$\;$ Then $\overline{B}(x)=%
\frac{1+2x-\sqrt{1+4x}}{2x}$,\ by Remark \ref{eight}, let $p(x)=\frac x{%
\overline{B}(x)\ }$ and $f=f(x)=xp(f)=B(x).$ By Corollary \ref{twelve}, if $%
p^m$ divides $n\;$ for some $m$\ and prime $p$, and $A(x)^n=\sum
a_{n,k}x^k,\; $then $p$ divides $a_{n,k}$ for $k\neq 0({mod}(p^m)).$
\end{remark}

\begin{remark}
Theorem \ref{six} may be used for a combinatorial proof of 
\cite[Corollary 2.2]{BS}.
\end{remark}

\begin{remark}
In the course of the work we never use the weights of lattice path, so one
may be able to prove the divisibility by using only factorials and
combinations.
\end{remark}

\section{Acknowledgments}

The author wishes to express his gratitude to the referee for several
comments and suggestions, especially for the substantial improvement of the
main result.


\begin{thebibliography}{19}
\bibitem{BS}  M. B\'ona and B. Sagan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Sagan/sagan101.html}{On divisibility of Narayana
numbers by primes}, \textit{J. Integer Seq.} \textbf{8} (2005), Article
05.2.4.

\bibitem{DS}  E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin
numbers and related sequences, \textit{J. Number Theory} \textbf{117}
(2006), 191--215.

\bibitem{GS}  G. R. Grimmett and D. R. Stirzaker, {\it Probability and Random
Processes}, 2nd edition, Oxford Science Publications, 1992.

\bibitem{MRSV}  D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri,
Underdiagonal lattice paths with unrestricted steps, \textit{Discrete Appl.
Math.} \textbf{91} (1999), 197--213.

\bibitem{R}  G. Raney, Functional composition patterns and power series
reversion, \textit{Trans. Amer. Math. Soc.} \textbf{94} (1960), 441--451.

\bibitem{FS}  F. Spitzer, {\it Principles of Random Walk},
Van Nostrand, Princeton, NJ, 1964.

\bibitem{RS}  R. Sprugnoli, Riordan arrays and combinatorial sums, \textit{%
Discrete Math.} \textbf{132} (1994), 267--290.

\bibitem{S}  R. P. Stanley, {\it Enumerative Combinatorics}, Vol. 2, Cambridge
University Press, 1999. Sections 5.3, 5.4.

\bibitem{JW}  J. G. Wendel, Left-continuous random walk and the Lagrange
expansion, \textit{Amer. Math. Monthly} \textbf{82} (1975), 494--499.

\bibitem{HW}  H. S. Wilf, {\it Generatingfunctionology}, Academic Press, 1994.

\bibitem{W}  W. J. Woan, Uniform partitions of Lattice paths and
Chung-Feller generalizations, \textit{Amer. Math. Monthly} \textbf{108}
(2001), 556--559.

\bibitem{WW}  W. J. Woan, \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL8/Woan/woan11.html}{A recursive relation for weighted Motzkin
sequences}, \textit{J. Integer Seq.} \textbf{8} (2005), Article 05.1.6.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 0515; Secondary 05A19, 11B65.

\noindent \emph{Keywords: } 
enumerative combinatorics, lattice paths, Lagrange
inversion formula.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 19 2006;
revised version received  July 26 2007.
Published in {\it Journal of Integer Sequences}, August 2 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

