\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}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf The Super Patalan Numbers } \vskip 1cm \large Thomas M. Richardson \\ 3438 N. Applecrest Ct., SE \\ Ada, MI 49301\\ USA \\ \href{mailto:ribby@umich.edu}{\tt ribby@umich.edu} \\ \end{center} \vskip .2 in \begin{abstract} We introduce the super Patalan numbers, a generalization of the super Catalan numbers in the sense of Gessel, and prove a number of properties analogous to those of the super Catalan numbers. The super Patalan numbers generalize the super Catalan numbers similarly to how the Patalan numbers generalize the Catalan numbers. \end{abstract} \section{Introduction} We introduce the super Patalan numbers as a generalization of the super Catalan numbers. The super Catalan numbers (sequence \seqnum{A068555} in the {\it On-Line Encyclopedia of Integer Sequences} \cite{OEIS}) were studied by Gessel in his paper on the super ballot numbers \cite{GESSEL}. (The term super Catalan numbers is also used to refer to a different sequence. We are generalizing the term as used by Gessel.) Just as the super Catalan numbers form a two-dimensional array that extends the Catalan numbers, the super Patalan numbers of order $p$ form a two-dimensional array that extends the Patalan numbers of order $p$. The super Patalan numbers have a number of properties that generalize the corresponding properties of the super Catalan numbers, in particular Eqs.~\eqref{BINOMIAL_IDENT}, \eqref{COLUMN_ONE_EQN}, \eqref{RECURRENCE_TWO_VAR}, and \eqref{GEN_FCN_TWO_VAR}. We also prove that the super Patalan numbers are integers, and we give a convolutional recurrence for the Patalan numbers, that generalizes the well known recurrence for the Catalan numbers. We start with the definitions of the super Catalan numbers and of the Patalan numbers. \begin{definition} Define the \emph{super Catalan numbers} $S(m,n)$ by \begin{equation*} S(m,n) = \frac{(2m)!(2n)!}{m!n!(m+n)!}. \end{equation*} \end{definition} The Catalan numbers $C_n$ are contained in the super Catalan numbers as $2C_n = S(n,1) = \frac{2(2n)!}{n!(n+1)!}$. \begin{definition} \label{PATALAN_DEF} Let $p$ be a positive integer with $p>1,$ and let $q$ be a positive integer with $q1$, the left hand side of \eqref{COMPOSITIONAL_INVERSE_EQN} is equal to 0. Setting $0$ equal to the degree $n$ term of the right hand side of Eq.~\eqref{COMPOSITIONAL_INVERSE_EQN} gives \begin{equation*} 0=-\sum_{k=1}^p \binom{p}{k} p^{k-2} \sum_{i_1+\ldots+i_k=n} \prod_{j=1}^k a(i_j-1) (-1)^kx^n. \end{equation*} Solving for the term with $k=1$ gives \begin{equation*} a(n-1) x^n =\sum_{k=2}^p \binom{p}{k} p^{k-2} \sum_{i_1+\ldots+i_k=n} \prod_{j=1}^k a(i_j-1) (-1)^kx^n. \end{equation*} Shifting indices and equating the coefficients gives \begin{equation} \label{CONVOLUTIONAL_RECURRENCE_EQN} a(n) =\sum_{k=2}^p \binom{p}{k} p^{k-2}(-1)^k \sum_{i_1+\ldots+i_k=n-k+1} \prod_{j=1}^k a(i_j). \end{equation} Because we are working with the compositional inverse of $xA(x)$, not of $A(x)$, the sum of the indices of each term on the right hand side of \eqref{CONVOLUTIONAL_RECURRENCE_EQN} is less than the index of the left hand side by one less than the number of factors in the term. It is easily verified that for $p=2$, Eq.~\eqref{CONVOLUTIONAL_RECURRENCE_EQN} reduces to Eq.~\eqref{CATALAN_RECURRENCE}. For $p=3$, Eq.~\eqref{CONVOLUTIONAL_RECURRENCE_EQN} reduces to \begin{equation} \label{PATALAN3_RECURRENCE} a(n) = \sum_{k=0}^{n-1} 3a(k)a(n-k-1) - \sum_{i+j+k=n-2} 3a(i)a(j)a(k). \end{equation} Eq.~\eqref{CONVOLUTIONAL_RECURRENCE_EQN} for $n=1$ has only one non-trivial term on the right hand side, and it implies that $a(1) = \binom{p}{2}$. \section{The super Patalan numbers are integers} \label{SP_INT_SEC} Lang proved that the Patalan numbers are integers \cite[Note 4, Lemma 19]{LANG}. We give an alternate proof that the Patalan numbers are integers, and we also prove that the super Patalan numbers are integers. \begin{theorem} The Patalan numbers of order $p$ are integers. \end{theorem} \begin{proof} Let $p>1$ be an integer and let $a(n)$ be the sequence of Patalan numbers of order $p$. By the definition $a(0) = 1$ and Eq.~\eqref{CONVOLUTIONAL_RECURRENCE_EQN}, it follows that $a(n)$ is an integer for all $n\ge 0$. \end{proof} \begin{theorem} \label{PATALAN_INTEGER_THM} The $(p,q)$-Patalan numbers are integers. \end{theorem} \begin{proof} By Eq.~\eqref{GF_PAT_1}, the generating function of the Patalan numbers of order $p$ is $f(x)=\frac{1-(1-p^2x)^{1/p}}{px}$, and from Eq.~\eqref{GF_PAT_PQ}, the generating function of the $(p,q)$-Patalan numbers is $g(x)=\frac{1-(1-p^2x)^{q/p}}{px}$. It follows that $g(x) = \frac{1-(1-pxf(x))^q}{px}$, and so $g(x) = \sum_{k=1}^q(-1)^{k+1}\binom{q}{k}(pxf(x))^k$. Thus the $(p,q)$-Patalan numbers may be expressed as an integral linear combination of the $k\textsuperscript{th}$ convolution powers of the Patalan numbers of order $p$, for $1\le k\le q$, and thus they are integers. \end{proof} \begin{theorem} \label{SUPER_PATALAN_INTEGER_THM} The $(p,q)$-super Patalan numbers are integers. \end{theorem} \begin{proof} Let $Q(i,j)$ be the $(p,q)$-super Patalan numbers. By \eqref{COLUMN_ONE_EQN}, the super Patalan numbers $Q(n,1)$ are an integer multiple of the $(p,q)$-Patalan numbers, so they are integers. Now rewriting \eqref{RECURRENCE_TWO_VAR} as $Q(i,j+1) = p^2Q(i,j) - Q(i+1,j)$ shows that $Q(i,j)$ is an integer for $j > 1$. Similarly, since by definition $Q(0,0)=1$, rewriting \eqref{RECURRENCE_TWO_VAR} as $Q(i+1,j) = p^2Q(i,j) - Q(i,j+1)$ shows that $Q(i,0)$ is an integer. \end{proof} \section{Factorization of the super Patalan matrix} \begin{definition} Define the \emph{reciprocal Pascal matrix} to be the matrix $R$ with $R(i,j) = \binom{i+j}{i}^{-1}$. \end{definition} \begin{lemma} \label{FACTORIZATION_LEMMA} Let $Q$ be the $(p,q)$-super Patalan numbers, let $G_{p,q}$ be the diagonal matrix with $G_{p,q}(i,i) = Q(i,0)$, and let $F_{p,q}$ be the diagonal matrix with $F_{p,q}(i,i) = Q(0,i)$. Then \begin{equation} \label{FACTORIZATION_EQN} Q = G_{p,q} R F_{p,q}. \end{equation} \end{lemma} \begin{proof} The $(i,j)$ entry of the right hand side is \begin{align*} G_{p,q}(i,i)R(i,j)F_{p,q}(j,j) &=\binom{i-q/p}{i}\binom{i+j}{i}^{-1}\binom{-q/p}{j} \\ &=\frac{(i-q/p)!}{i!(-q/p)!}\frac{i!j!}{(i+j)!}\frac{(-q/p)!}{j!(-j-q/p)!} \\ &=\frac{(i-q/p)!}{(i+j)!(-j-q/p)!} \end{align*} and this last expression is $Q(i,j)$. \end{proof} The author previously used the factorization of Eq.~\eqref{FACTORIZATION_EQN}, for the case $p = 2$, to prove that the inverse of the reciprocal Pascal matrix is an integer matrix \cite{RPM}. Next we prove that the inverse of the Hadamard inverse of the super Patalan matrix is an integer matrix. \begin{theorem} \label{INVERSE_SUPER_PATALAN_THM} Let $Q$ be the $(p,q)$-super Patalan matrix, and let $H$ be the $n \times n$ matrix given by $H(i,j) = \frac{1}{Q(i,j)}$ for $0 \le i,j < n$. Then the inverse of $H$ is an integer matrix. \end{theorem} \begin{proof} Let $G(n)$ and $F(n)$ be the upper left $n \times n$ sections of $G_{p,q}$ and $F_{p,q}$, respectively. Lemma \ref{FACTORIZATION_LEMMA}, and the fact that $G(n)$ and $F(n)$ are diagonal, show that \begin{equation*} H = G(n)^{-1} B F(n)^{-1}, \end{equation*} where $B$ is the $n \times n$ Pascal matrix with $B(i,j) = \binom{i+j}{i}$, for $0 \le i,j < n$. Then \begin{equation*} H^{-1} = F(n) B^{-1} G(n). \end{equation*} Since $B^{-1}$, $G(n)$, and $F(n)$ are all integer matrices, it follows that $H^{-1}$ also is an integer matrix. \end{proof} \begin{thebibliography}{9} \bibitem{ALLEN} Emily Allen and Irina Gheorghiciuc, A weighted interpretation for the super Catalan numbers, {\it J. Integer Seq.} {\bf 17} (2014), \href{https://https://cs.uwaterloo.ca/journals/JIS/VOL17/Allen/gheo.html}{Article 14.10.7}. \bibitem{GESSEL} Ira M. Gessel, Super ballot numbers, {\it J. Symbolic Comput.} {\bf 14} (1992), 179--194. \bibitem{XIN} Ira M. Gessel and Guoce Xin, A combinatorial interpretation of the numbers $6(2n)!/n!(n+2)!$, {\it J. Integer Seq.} {\bf 8} (2005), \href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Gessel/xin.html} {Article 05.2.3}. \bibitem{LANG} Wolfdieter Lang, Generalizations of the Stirling number triangle, {\it J. Integer Seq.} {\bf 3} (2000), \href{https://cs.uwaterloo.ca/journals/JIS/VOL3/LANG/lang.html} {Article 00.2.4}. \bibitem{RPM} Thomas M. Richardson, The reciprocal Pascal matrix, preprint, 2014, \url{http://arxiv.org/abs/1405.6315}. \bibitem{OEIS} N. J. A. Sloane, {\it Online Encyclopedia of Integer Sequences}. Published electronically at \url{http://oeis.org}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 5A10; Secondary 11B37, 11B75, 15A36. \noindent \emph{Keywords: } Catalan number, Patalan number, super Catalan number, super Patalan number, generating function, Pascal matrix. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A025748}, \seqnum{A025749}, \seqnum{A025750}, \seqnum{A025751}, \seqnum{A025752}, \seqnum{A025753}, \seqnum{A025754}, \seqnum{A025755}, \seqnum{A025756}, \seqnum{A025757}, \seqnum{A068555}, \seqnum{A097188}, \seqnum{A248324}, \seqnum{A248325}, \seqnum{A248326}, \seqnum{A248328}, \seqnum{A248329}, and \seqnum{A248332}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 27 2014; revised version received January 27 2015. Published in {\it Journal of Integer Sequences}, February 10 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .