\documentclass[12pt,reqno]{article} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{xcolor} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{fullpage} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \renewcommand{\theenumi}{\alph{enumi}} \renewcommand{\labelenumi}{(\theenumi)} \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} \begin{center} \vskip 1cm{\LARGE\bf An Explicit Formula and a Recurrence\\ \vskip .1in for OEIS \seqnum{A265233} } \vskip 1cm \large Juntao Jin\\ Central South University\\ Changsha 410083\\ China\\ \href{mailto:7805240210@csu.edu.cn}{\tt 7805240210@csu.edu.cn} \\ \end{center} \vskip .2 in \begin{abstract} We give an explicit formula for OEIS sequence \seqnum{A265233} as a binomial sum involving the Franel numbers. The sequence counts three-row arrays that contain equally many copies of each of three symbols and have no equal vertically adjacent entries. Reading the array row by row, we label the symbols in order of first occurrence. A decomposition of the column-counting polynomial yields the explicit formula and a proof of Mathar's conjectured recurrence. We then derive the hypergeometric generating function recorded by van Hoeij and the asymptotic formula conjectured by Kotesovec. The latter follows from a logarithmic singular expansion with an explicit error estimate. \end{abstract} \section{Introduction}\label{sec:introduction} Let $a_n$ count the $3\times n$ arrays over $\{0,1,2\}$ with the following properties: \begin{enumerate} \item\label{cond:balance} Each symbol occurs exactly $n$ times in the array. \item\label{cond:vertical} Vertically adjacent entries are distinct. Thus a column $(c_1,c_2,c_3)^{\mathsf T}$ satisfies $c_1\ne c_2$ and $c_2\ne c_3$, while equality between $c_1$ and $c_3$ is allowed. \item\label{cond:order} When we read the entries from left to right across the first row, then the second, and then the third, the first occurrences of the symbols appear in the order $0,1,2$. \end{enumerate} We include the empty array by setting $a_0=1$. These numbers form sequence \seqnum{A265233} in the On-Line Encyclopedia of Integer Sequences (OEIS)~\cite{OEIS}. For example, the seven arrays counted by $a_2$ are \[ \begin{pmatrix}0&0\\1&2\\2&1\end{pmatrix},\quad \begin{pmatrix}0&1\\2&2\\0&1\end{pmatrix},\quad \begin{pmatrix}0&1\\2&0\\1&2\end{pmatrix},\quad \begin{pmatrix}0&1\\2&2\\1&0\end{pmatrix},\quad \begin{pmatrix}0&0\\1&1\\2&2\end{pmatrix},\quad \begin{pmatrix}0&1\\1&0\\2&2\end{pmatrix},\quad \begin{pmatrix}0&1\\1&2\\2&0\end{pmatrix}. \] We give an explicit binomial-sum formula for $a_n$ and use the formula to prove the recurrence conjectured by Mathar in 2015. The formula expresses the array count in terms of the Franel numbers, which are sums of cubes of binomial coefficients. Their classical recurrence then gives the recurrence for $a_n$. \begin{theorem}\label{thm:main} The sequence $(a_n)_{n\geq0}$ has the following properties. \begin{enumerate} \item For every integer $n\geq1$, we have \begin{equation}\label{eq:explicit} a_n=\frac{1}{6}\sum_{m=0}^{n}\binom{n}{m}4^{n-m} \sum_{k=0}^{m}\binom{m}{k}^{3}. \end{equation} \item For every integer $n\geq4$, the sequence satisfies the recurrence \begin{equation}\label{eq:mathar} n^2a_n-(19n^2-19n+6)a_{n-1} +96(n-1)^2a_{n-2} -144(n-1)(n-2)a_{n-3}=0, \end{equation} with initial values $a_0=1$, $a_1=1$, $a_2=7$, and $a_3=56$. \end{enumerate} \end{theorem} The OEIS entry also contains an asymptotic formula conjectured by Kotesovec in 2023 and a hypergeometric generating function recorded by van Hoeij in 2024, conditional on Mathar's recurrence. We derive these as consequences of Theorem~\ref{thm:main}. For $|z|<1$ and $c\notin\{0,-1,-2,\ldots\}$, we define the \emph{Gauss hypergeometric function} by \[ {}_2F_1(a,b;c;z)=\sum_{k\geq0}\frac{(a)_k(b)_k}{(c)_k\,k!}z^k, \] where we define the \emph{Pochhammer symbol} by $(a)_0=1$ and $(a)_k=a(a+1)\cdots(a+k-1)$ for $k\geq1$. \begin{corollary}\label{cor:consequences} The sequence $(a_n)_{n\geq0}$ satisfies the following formulas. \begin{enumerate} \item The ordinary generating function for $(a_n)_{n\geq0}$ is \begin{equation}\label{eq:vanhoeij} A(x)=\sum_{n\geq0}a_nx^n =\frac{{}_2F_1\!\left(\frac13,\frac23;1;27x(1-4x)^2\right)+5}{6}. \end{equation} \item As $n\to\infty$, we have \begin{equation}\label{eq:kotesovec} a_n\sim\frac{\sqrt{3}}{6\pi}\frac{12^n}{n} =\frac{2^{2n-1}3^{n-1/2}}{\pi n}. \end{equation} \end{enumerate} \end{corollary} \section{The column polynomial and the explicit formula}\label{sec:columns} Let $b_n$ count the arrays satisfying conditions~(\ref{cond:balance}) and~(\ref{cond:vertical}), with no restriction on the order of first occurrences. For $n\geq1$, every array uses all three symbols, so its six relabelings are distinct. Exactly one of them satisfies condition~(\ref{cond:order}): relabel the first symbol encountered as $0$, the next new symbol as $1$, and the remaining symbol as $2$. Hence \begin{equation}\label{eq:b6a} b_n=6a_n\qquad(n\geq1). \end{equation} The empty array gives $a_0=b_0=1$. Encode a column by the monomial $x^{e_0}y^{e_1}z^{e_2}$, where the exponent $e_s$ counts the entries equal to $s$. For example, the column $(0,1,0)^{\mathsf T}$ contributes $x^2y$. There are twelve allowed columns: six use all three symbols, and six have equal top and bottom entries. Their counting polynomial is \begin{align} P(x,y,z) &=x^2y+x^2z+xy^2+y^2z+xz^2+yz^2+6xyz\notag\\ &=(x+y)(y+z)(z+x)+4xyz.\label{eq:P} \end{align} Write $[x^iy^jz^k]Q$ for the coefficient of $x^iy^jz^k$ in a polynomial or formal power series $Q$. Since there are no horizontal adjacency restrictions, we multiply the column weights and impose condition~(\ref{cond:balance}) to obtain \begin{equation}\label{eq:bdiag} b_n=[x^ny^nz^n]P(x,y,z)^n. \end{equation} The \emph{Franel numbers}, sequence \seqnum{A000172}, are \[ f_m=\sum_{k=0}^{m}\binom{m}{k}^{3}\qquad(m\geq0). \] The following coefficient identity connects them to the array model. \begin{lemma}\label{lem:diag} For every integer $m\geq0$, we have \begin{equation}\label{eq:franeldiag} [x^my^mz^m]\bigl((x+y)(y+z)(z+x)\bigr)^m=f_m. \end{equation} \end{lemma} \begin{proof} Expand the three factors as \begin{align*} (x+y)^m&=\sum_{i=0}^{m}\binom{m}{i}x^iy^{m-i},\\ (y+z)^m&=\sum_{j=0}^{m}\binom{m}{j}y^jz^{m-j},\\ (z+x)^m&=\sum_{k=0}^{m}\binom{m}{k}z^kx^{m-k}. \end{align*} To obtain $x^my^mz^m$, we require $i=k$, $j=i$, and $k=j$. The coefficient is therefore $\sum_{k=0}^{m}\binom{m}{k}^{3}$. \end{proof} \begin{proof}[Proof of the explicit formula in Theorem~\ref{thm:main}] Apply the binomial theorem to the decomposition in~\eqref{eq:P}. Equations~\eqref{eq:bdiag} and~\eqref{eq:franeldiag} give \begin{align} b_n &=[x^ny^nz^n]\sum_{m=0}^{n}\binom{n}{m}(4xyz)^{n-m} \bigl((x+y)(y+z)(z+x)\bigr)^m\notag\\ &=\sum_{m=0}^{n}\binom{n}{m}4^{n-m}f_m.\label{eq:conv} \end{align} For $n\geq1$, divide by $6$ and use the definition of $f_m$ to obtain \eqref{eq:explicit}. \end{proof} The formula, together with $a_0=1$, gives the first ten terms \[ (a_n)_{n=0}^{9} =(1,1,7,56,495,4686,46456,475392,4976271,52977890), \] in agreement with \seqnum{A265233}. \section{The recurrence}\label{sec:recurrence} Let $\mathcal F(t)=\sum_{m\geq0}f_mt^m$ and $B(x)=\sum_{n\geq0}b_nx^n$ denote the ordinary generating functions for $(f_m)_{m\geq0}$ and $(b_n)_{n\geq0}$, respectively. For every integer $m\geq0$, the binomial identity \[ \sum_{n\geq m}\binom{n}{m}4^{n-m}x^n =\frac{x^m}{(1-4x)^{m+1}} \] and~\eqref{eq:conv} give the binomial-transform identity \begin{equation}\label{eq:euler} B(x)=\frac{1}{1-4x}\mathcal F\!\left(\frac{x}{1-4x}\right). \end{equation} The Franel numbers satisfy \begin{equation}\label{eq:franelrec} m^2f_m-(7m^2-7m+2)f_{m-1}-8(m-1)^2f_{m-2}=0 \qquad(m\geq2), \end{equation} with $f_0=1$ and $f_1=2$. Strehl~\cite[p.\ 4, Eq.\ (2)]{Strehl1992} discusses this classical recurrence and its relation to transforms of sequences. Cusick~\cite{Cusick1989} gives a general method for deriving recurrences for sums of powers of binomial coefficients. The recurrence~\eqref{eq:franelrec} and the initial values are equivalent to \begin{equation}\label{eq:franelode} \begin{split} t(1+t)(1-8t)\mathcal F''(t) +(1-14t-24t^2)\mathcal F'(t)\\ -2(1+4t)\mathcal F(t)=0, \end{split} \end{equation} together with $\mathcal F(0)=1$. \begin{proof}[Proof of the recurrence in Theorem~\ref{thm:main}] Set $t=x/(1-4x)$. By~\eqref{eq:euler}, we have $\mathcal F(t)=(1-4x)B(x)$. The chain rule gives \begin{align*} \mathcal F'(t)&=(1-4x)^3B'(x)-4(1-4x)^2B(x),\\ \mathcal F''(t)&=(1-4x)^5B''(x)-16(1-4x)^4B'(x) +32(1-4x)^3B(x). \end{align*} Substitution into~\eqref{eq:franelode} and division by $1-4x$ yield \begin{equation}\label{eq:Bode} \begin{split} (x-19x^2+96x^3-144x^4)B''(x) +(1-38x+288x^2-576x^3)B'(x)\\ +(-6+96x-288x^2)B(x)=0. \end{split} \end{equation} For $n\geq3$, extracting the coefficient of $x^{n-1}$ gives \begin{equation}\label{eq:brec} \begin{split} n^2b_n-(19n^2-19n+6)b_{n-1} +96(n-1)^2b_{n-2}\\ -144(n-1)(n-2)b_{n-3}=0. \end{split} \end{equation} For $n\geq4$, all four subscripts are positive, so equation~\eqref{eq:b6a} converts~\eqref{eq:brec} into~\eqref{eq:mathar}. The initial values follow from~\eqref{eq:explicit} and $a_0=1$. \end{proof} \section{The hypergeometric generating function}\label{sec:generating} Write $\Phi(z)={}_2F_1(\frac13,\frac23;1;z)$. In the OEIS entry \seqnum{A000172}~\cite{OEIS}, Somos recorded the generating function for the Franel numbers on December 17, 2010: \begin{equation}\label{eq:franelhyper} \mathcal F(t)=\frac{1}{1-2t}\Phi\!\left(\frac{27t^2}{(1-2t)^3}\right). \end{equation} The right-hand side also satisfies~\eqref{eq:franelode} and has constant term $1$, which provides a direct verification of the identity. Combining~\eqref{eq:franelhyper} with~\eqref{eq:euler} gives \[ B(x)=\frac{1}{1-6x}\Phi\!\left( \frac{27x^2(1-4x)}{(1-6x)^3}\right). \] We obtain the form in~\eqref{eq:vanhoeij} directly from the differential equation for $B$. \begin{proof}[Proof of~\eqref{eq:vanhoeij}] The defining series for $\Phi$ satisfies the Gauss differential equation \begin{equation}\label{eq:gauss} z(1-z)\Phi''(z)+(1-2z)\Phi'(z)-\frac{2}{9}\Phi(z)=0. \end{equation} Set \[ w(x)=27x(1-4x)^2,\qquad p(x)=x(1-3x)(1-4x)(1-12x), \] and write \[ \mathcal L(y)=p(x)y''+p'(x)y'-6(1-4x)(1-12x)y. \] Thus equation~\eqref{eq:Bode} is $\mathcal L(B)=0$. Direct differentiation and~\eqref{eq:gauss} give \begin{align} \mathcal L(\Phi\circ w) &=27(1-4x)(1-12x)\bigl(w(x)(1-w(x))\Phi''(w(x))\notag\\ &\qquad{}+(1-2w(x))\Phi'(w(x)) -\tfrac29\Phi(w(x))\bigr)=0.\label{eq:pullback} \end{align} By~\eqref{eq:pullback}, both $B(x)$ and $\Phi(w(x))$ solve the same differential equation, and both have constant term $1$. In~\eqref{eq:Bode}, equating coefficients of $x^{n-1}$ determines the coefficient of $x^n$ in a solution from its preceding coefficients, since the multiplier of that coefficient is $n^2\ne0$ for every $n\geq1$. Consequently, \begin{equation}\label{eq:Bhyper} B(x)=\Phi\!\left(27x(1-4x)^2\right) \end{equation} as power series at $x=0$. Finally, the relations $a_0=b_0=1$ and~\eqref{eq:b6a} give $A(x)=(B(x)+5)/6$, proving~\eqref{eq:vanhoeij}. \end{proof} \section{The asymptotic formula}\label{sec:asymptotics} \begin{proof}[Proof of~\eqref{eq:kotesovec}] Put $\rho=1/12$. We first justify the analytic continuation needed for coefficient extraction. Since there are twelve allowed columns, we have $0\leq b_n\leq12^n$, so the series $B$ is analytic in $|x|<\rho$. The leading coefficient in~\eqref{eq:Bode} factors as \[ p(x)=x(1-3x)(1-4x)(1-12x). \] Fix $R$ with $\rho\theta\}, \qquad 0<\theta<\pi/2. \] The sum of the numerator parameters of $\Phi$ equals its denominator parameter, so the function is \emph{zero-balanced}. The corresponding logarithmic expansion in the NIST Digital Library of Mathematical Functions~\cite[Eq.\ (15.8.10), with $m=0$]{DLMF} gives \begin{equation}\label{eq:zerobalanced} \Phi(z)=-c\log(1-z)+C_0+ O\!\left(|1-z|\bigl(1+|\log(1-z)|\bigr)\right), \end{equation} where \[ c=\frac{1}{\Gamma(1/3)\Gamma(2/3)}=\frac{\sqrt{3}}{2\pi} \] and the quantity $C_0$ is constant. Here the symbol $\Gamma$ denotes the gamma function, and Euler's reflection formula~\cite[Eq.\ (5.5.3)]{DLMF} gives the displayed value of $c$. The regularized hypergeometric function used in the zero-balanced expansion equals $\Phi$, since its normalizing factor is $\Gamma(1)=1$. The full zero-balanced expansion converges and has analytic coefficient functions. Consequently, the expansion continues with the chosen logarithm from a slit neighborhood of $z=1$. The exact identity \begin{equation}\label{eq:factor} 1-w(x)=(1-3x)(1-12x)^2 \end{equation} shows that, with the logarithms real for $0