\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 $00$ 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\ ,01.$} \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