\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{enumerate} \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} \newcommand\BD{\mathrm{B}} \newcommand\SD{\mathrm{S}} \newcommand{\N}{{\mathbb N}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\C}{{\mathcal C}} \newcommand{\A}{{\mathcal A}} \newcommand{\F}{{\mathcal F}} \begin{center} \vskip 1cm{\LARGE\bf Further Results on Paths in an \emph{n}-Dimensional Cubic Lattice\\ \vskip 1cm} \large Rigoberto Fl\'orez\\ Department of Mathematics and Computer Science\\ The Citadel\\ Charleston, SC 29409\\ USA\\ \href{mailto:rigo.florez@citadel.edu}{\tt rigo.florez@citadel.edu} \\ \ \\ Leandro Junes\\ Department of Mathematics, Computer Science and Information Systems\\ California University of Pennsylvania\\ California, PA 15419\\ USA\\ \href{mailto:junes@calu.edu}{\tt junes@calu.edu}\\ \ \\ Jos\'e L. Ram\'{\i}rez\\ Departamento de Matem\'aticas\\ Universidad Nacional de Colombia\\ Bogot\'a\\ Colombia\\ \href{mailto:jlramirezr@unal.edu.co}{\tt jlramirezr@unal.edu.co} \end{center} \vskip .2 in \begin{abstract} We study paths formed by integer $n$-tuples in an $n$-dimensional cubic lattice. We establish some connections between these paths, Riordan arrays, coefficients of Chebyshev polynomials of the second kind, and $k$-colored Motzkin paths. \end{abstract} \section{Introduction} A three-dimensional cubic lattice is a lattice in $\mathbb{R}^{3}$ formed by integer triplets. We study properties of three-dimensional lattice walks in the upper half of the three-dimensional cubic lattice. In particular, we count the number of paths of length $k$ that are in three-dimensional cubic lattice beginning at the origin and ending on the $xy$-plane. This gives another answer to a question raised by Deutsch \cite{deutsch} in 2000. The problem asks:\emph{ A 3-dimensional lattice walk of length $n$ takes $n$ successive unit steps, each in one of the six coordinate directions. How many 3-dimensional lattice walks of length $n$ are there that begin at the origin and never go below the horizontal plane?} The answer to Deutsch's question is \cite{brawner,deutsch} $$\sum_{k=0}^n\binom nk \binom{k}{\lceil k/2 \rceil}4^{n-k}.$$ This problem generalizes, naturally, to an $n$-dimensional cubic lattice. Deutsch's problem is a generalization, to three dimensions, of the following problem proposed by Sands \cite{Sands} in 1990: \emph{What is the number of different walks, in the plane, with $n$ steps such that each step moves one unit either north, south, east, or west, starting at the origin and remaining in the upper half-plane?} Hirschhorn \cite{hirschhorn} proved in 1991 that the number of such paths is $\binom{2n+1}{n}.$ Later, Guy \cite{GuyCatwalks} gave a short proof of the same result. In the same paper, Guy studied this problem from the point of view of one-dimensional and two-dimensional arrays using the Pascal semi-triangle and Pascal semi-pyramid, respectively. He found some interesting relations with Catalan numbers as well as several combinatorial identities that were used in the entries of the mentioned arrays. Guy, Krattenthaler, and Sagan \cite{krattenthalerguy} gave combinatorial proofs for several two-dimensional results. The three-dimensional case was also studied by Guy \cite{GuyCatwalks}. In this paper we answer an open question that Guy proposed in \cite{krattenthalerguy}. \emph{Is it possible to find a closed formula for the number of paths, in the three-dimensional cube, that can not go below the plane $z=0$?} We give such a formula as well as other closed formulas. In addition, Nkwanta \cite{Nka} generalizes several problems proposed by Sands and Deutsch to $n$-dimensional case using Riordan arrays. He also shows a bijection between the lattice paths of length $k$ and $k$-colored Motzkin paths. In 2017, Dershowitz \cite{Dershowitz} obtained a bijection between Dyck paths and 2-dimensional lattice paths that end in the $x$-axis. He also considered the $n$-dimensional case with the same condition. We provide several relations and counting results involving walks in the $n$-dimensional cubic lattice and Riordan arrays. We also study Riordan arrays from the perspective of the \emph{height} of a path. The \emph{height} at which a path $P$ ends, in the $n$-dimensional cubic lattice, is the last value of the last $n$-tuple (vertex or point) of the path. For simplicity, we call this value the \emph{height} of $P$. Those heights give rise to a Riordan array $\A_3$. We have found that the entries of $\A_{3}^{-1}$ are the coefficients of Chebyshev polynomials of the second kind (shifted four units up). Using the generating function obtained from $\A_3,$ we find a closed formula that answers the open question given by Guy in \cite{GuyCatwalks}. Since $\A_3$ and $\A_3^{-1}$ are infinite matrices, we found a fractal associated to those matrices. Visually, these fractals look like half of the Sierpi{\'n}ski fractal. Finally, we provide several sequences and conjectures about paths in the $3$-dimensional cubic lattice. These sequences/conjectures are based on numerical experimentation. Most proofs in this paper use generating functions that are constructed using the symbolic method introduced by Flajolet and Sedgewick \cite{flajolet2}. \section{Background} An $n$-dimensional cubic lattice is a lattice $L$ in $\mathbb{R}^{n}$ formed by points in $\Z^n$. If $p_i$ is a point in $\Z^n$ with $p_0=(0,0, \dots, 0)$, then a path $P = (p_0,p_1, \ldots, p_m)$ of length $m$ is a concatenation of $p_0, p_1, \ldots, p_m$ where the distance between $p_i$ and $ p_{i+1}$ is one for $i\in \{0, 1, \dots, m-1\}$. A \emph{step} in $P$ is a pair of two consecutive points $(p_{i},p_{i+1})$ for $i\in \{0, \ldots, m-1\}$. We identify the path $P= (p_0,p_1, \ldots, p_m)$ with its broken-line graph obtained by joining $p_{i}$ to $p_{i+1}$ with a line segment for $i \in \{0,\ldots,m-1\}$. We denote by $e_i$ the $n$-tuple $(0, \dots, 1, \dots, 0)$ where $1$ is in the $i$-th position and zeros elsewhere for $1\leq i \leq n$. Since $p_0=(0,0, \dots, 0)$, we have that $p_1=e_i$ for some $1\leq i \leq n$. It is easy to see that $p_j$ can be written in either of the forms $p_j=p_{j-1}+e_{r}$ or $p_j=p_{j-1}-e_{r}$, for some $1\leq r \leq n$ and $1\leq j \leq m$. Note that $e_r$ gives the orientation of the step $p_{j-1}p_{j}$. For example, if a path $P$ is in $\Z^3$ with $p_5=p_4+(0,1,0)$, then the step $p_4p_5$ is parallel to the positive direction of the $y$-axis. Now it is easy to see that a path $P= (p_0,p_1,p_3, \ldots, p_{m-1}, p_m)$ can be written in the form $P= (p_0, p_0\pm e_{j_1}, p_1 \pm e_{j_2}, \ldots, p_{m-1}\pm e_{j_m})$ where $\pm$ indicates the orientation of each step. For simplicity, we represent $P= (p_0, p_0\pm e_{j_1}, p_1 \pm e_{j_2}, \ldots, p_{m-1}\pm e_{j_m})$ as $P=(\pm e_{j_1})(\pm e_{j_2})\cdots (\pm e_{j_m})$ and we say that $(\pm e_{j_1}), (\pm e_{j_2}), \ldots, (\pm e_{j_m})$ are the components of $P$, (see Figures \ref{two:dimen} and \ref{3dimen}). We use $\C_n^{\pm}(k)$ to mean the set of all paths of length $k$ in the $n$-dimensional cubic lattice. We divide $\C_n^{\pm}(k)$ into subfamilies depending on the behavior of the path. We now give definitions and notation for those families. If $P=(\pm e_{j_1})(\pm e_{j_2})\cdots (\pm e_{j_k})$, then we define $V_r:= (\pm e_{j_1})+(\pm e_{j_2})+\cdots + (\pm e_{j_r})$, the algebraic combination of the first $r$ components of $P$ for $0n$ (see Guy \cite{GuyCatwalks}). This sequence gives rise to an infinite lower triangular matrix. It is denoted by $\A_3=\left[a_3(n,k)\right]_{n,k\geq 0}$. So, $$\A_3=\left[a_3(n,k)\right]_{n,k\geq 0}= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 17 & 8 & 1 & 0 & 0 & 0 & 0 & 0 \\ 76 & 50 & 12 & 1 & 0 & 0 & 0 & 0 \\ 354 & 288 & 99 & 16 & 1 & 0 & 0 & 0 \\ 1704 & 1605 & 700 & 164 & 20 & 1 & 0 & 0 \\ 8421 & 8824 & 4569 & 1376 & 245 & 24 & 1 & 0 \\ 42508 & 48286 & 28476 & 10318 & 2380 & 342 & 28 & 1 \\ \vdots& \vdots& \vdots& \vdots & \vdots& \vdots & \vdots & \vdots \\ \end{bmatrix}. $$ From Theorem \ref{Mer1} we can prove that the matrix $\A_3$ is a Riordan matrix. Guy \cite{GuyCatwalks} also found a relation between this matrix and the sequences \seqnum{A005572}, \seqnum{A005573}, \seqnum{A052177}, \seqnum{A052178} and \seqnum{A052179}. \begin{theorem}\label{teoA1} The infinite triangular matrix $\A_3=\left[a_3(n,k)\right]_{n,k\geq 0}$ has a Riordan array expression given by \begin{align*} \A_3=\left( T_3(z), zT_3(z)\right), \end{align*} where $$T_3(z)=\frac{1-4z-\sqrt{1-8z+12z^2}}{2z^2}.$$ \end{theorem} \begin{proof} From the recurrence relation \eqref{recu1}, we know that the $A$-sequence is $(1, 4, 1, 0, 0, \dots)$. Therefore, $A(z)=1+4z+z^2$. This implies that $f(z)=z(1+4f(z)+f(z)^2)$. Therefore, \[f(z)=\frac{1-4z-\sqrt{1-8z+12z^2}}{2z}=zT_3(z).\] Now, it is easy to see that the generating function of the 0th column is $T_3(x)$. \end{proof} The proof of Theorem \ref{teoA1} shows that the Riordan array $\A_3$ has $A$-sequence $(1,4,1)$. Merlini et al.~\cite{MSV} studied a lattice path model in the plane that has an associated Riordan matrix with $A$-sequence $(a,b,c)$. Merlini and Sprugnoli \cite{MS} study again this type model. In Section \ref{motsec}, we show a relationship between the coloured Motzkin path and the paths in the $n$-dimensional cube. \begin{corollary}\label{Riordan:corollary} In the three-dimensional cube the following hold: \begin{enumerate}[(1)] \item the generating function for the total number of paths of length $i$ in $\C_3^{\geq}$ is given by \[ H_3(z):=\sum_{i=0}^{\infty}b_3(i)z^i=\frac{T_3(z)}{1-zT_3(z)}=\frac{1-6z-\sqrt{1-8z+12z^2}}{2z(6z-1)}, \] \item the number of paths of length $m$ such that the paths never go below the horizontal plane is given by \[ b_3(m)=\sum_{n=0}^m \sum_{k=0}^{\left\lfloor \frac{m-n}{2}\right\rfloor} \binom{n+2k+1}{k}\binom{m}{n+2k}\left(\frac{n+1}{n+2k+1}\right) 4^{m-n-2k}. \] \end{enumerate} \end{corollary} \begin{proof} From the Fundamental Theorem of Riordan arrays we have $$\left( T_3(z), zT_3(z)\right) \frac{1}{1-z}=\frac{T_3(z)}{1-zT_3(z)}=\sum_{n=0}^\infty\sum_{k=0}^na_3(n,k) z^n=\sum_{n=0}^\infty b_3(n)z^n=H_3(z).$$ After simplification we obtain the result that proves part (1). \medskip \noindent Proof of part (2): It is easy to see that \begin{equation*} H_3(z)=\frac{T_3(z)}{1-zT_3(z)}=\frac{\left(1/(1-4z)\right) C(u)}{1-\left(z/(1-4z)\right) C(u)}, \end{equation*} where $u=z^2/(1-4z)^2$ and $C(z)$ is the generating function of the Catalan numbers. Therefore, \begin{align*} H_3(z)=\frac{1}{1-4z}\sum_{n=0}^\infty\left(\frac{z}{1-4z}\right)^nC^{n+1}(u). \end{align*} From \cite[equation 5.70]{GKP} we know that \begin{align} C^n(z)=\sum_{k=0}^\infty\binom{n+2k}{k}\frac{n}{n+2k}z^k. \label{powerCat} \end{align} This implies that \begin{align*} H_3(z)&=\sum_{n=0}^\infty \sum_{k=0}^\infty \binom{n+2k+1}{k}\left(\frac{n+1}{n+2k+1}\right) \left( \frac{z^n}{(1-4z)^{n+1}}\right) u^k\\ &=\sum_{n=0}^\infty \sum_{k=0}^\infty \binom{n+2k+1}{k} \left(\frac{n+1}{n+2k+1}\right) \left( \frac{z^{n+2k}}{(1-4z)^{n+2k+1}}\right)\\ &=\sum_{n=0}^\infty \sum_{k=0}^\infty\sum_{l=0}^\infty \binom{n+2k+1}{k}\binom{n+2k+l}{l}\left(\frac{n+1}{n+2k+1}\right) 4^l z^{n+2k+l}. \end{align*} This with $t=n+2k+l$ implies \begin{align*} H_3(z)&=\sum_{n=0}^\infty \sum_{k=0}^\infty\sum_{t=n+2k}^\infty \binom{n+2k+1}{k}\binom{t}{n+2k}\left(\frac{n+1}{n+2k+1}\right) 4^{t-n-2k} z^{t}. \end{align*} Therefore, \begin{align*} b_3(m)=[z^m]H_3(z)&=\sum_{n=0}^m \sum_{k=0}^{\left\lfloor \frac{m-n}{2}\right\rfloor} \binom{n+2k+1}{k}\binom{m}{n+2k}\left(\frac{n+1}{n+2k+1}\right) 4^{m-n-2k}. \end{align*} This proves part (2). \end{proof} The following sequence gives some values for the total number of paths of length $0-9$ in three-dimensional cube that never go below the $xy$-plane. This sequence appears in OEIS as \seqnum{A005573}. So, $b_3(m)$ for $m=0,1, \dots,9$ is given by $$1, 5, 26, 139, 758, 4194, 23460, 132339, 751526, 4290838.$$ The previous theorem gives a closed formula that answers Guy's question. Theorem \ref{entries:ofA} gives a closed formula for all entries of $\A_3$. \begin{theorem}\label{entries:ofA} If $m$ and $n$ are non-negative integers, then \[ a_3(n,k)=\frac{k+1}{n+1}\sum_{l=0}^{\lfloor \frac{n-k}{2} \rfloor} \binom{n+1}{n-k-l}\binom{n-k-l}{l}4^{n-k-2l}. \] \end{theorem} \begin{proof} Let $M(z)=zT_3(z)$ then from \eqref{ecuacion1a} we obtain $$M(z)=z(M(z)^2+4M(z)+1)=zP(z),$$ where $P(z)=z^2+4z+1$. From the Lagrange Inversion Formula (cf. \cite{Lagrange}) \begin{align*} a_3(n,k)&=[z^n]\left(z^k T_3(z)^{k+1}\right)=[z^{n+1}]M(z)^{k+1}\\ &=\frac{k+1}{n+1}[z^{n-k}]\left(z^2+4z+1\right)^{n+1}\\ &=\frac{k+1}{n+1}[z^{n-k}]\left(\sum_{i=0}^{n+1}\binom{n+1}{i}z^i(z+4)^i\right)\\ &=\frac{k+1}{n+1}[z^{n+1}]\left(\sum_{i=0}^{n+1}\sum_{l=0}^i\binom{n+1}{i}\binom{i}{l}4^{i-l}z^{i+l+k+1}\right)\\ &=\frac{k+1}{n+1}[z^{n+1}]\left(\sum_{m=0}^{2n+2}\sum_{l=0}^{\lfloor \frac m2\rfloor}\binom{n+1}{m-l}\binom{m-l}{l}4^{m-2l}z^{m+k+1}\right). \end{align*} If we take $m=n-k$, we obtain the desired result. \end{proof} \begin{theorem}\label{main:diagonals} In the three-dimensional cube the following hold: \begin{enumerate}[(1)] \item the generating function $U_3(z)$ for the total number of paths of length $i$ in $\C_3^+$ with no level steps at height 0 is given by \[ U_3(z):=\sum_{n=0}^\infty u_3(n)z^n=\frac{1}{1-z^2T_3(z)},\] \item the sum of entries of the rising diagonal of the Riordan array $\A_3=\left[a_3(n,k)\right]_{n,k\geq 0}$ is \[u_3(n+2)=\sum_{i=0}^{\lfloor \frac n2 \rfloor }a(n-i,i).\] \end{enumerate} \end{theorem} \begin{proof} From the first return decomposition a nonempty three-dimensional lattice path $P$ in $\C_3^+$ with no level steps at height 0 may be decomposed as $e_3P^{\prime}(-e_3)P^{\prime\prime}$ where $P^{\prime}$ and $P^{\prime\prime}$ are three dimensional lattice paths (possibly empty) in $\C_3^+$ such that $P^{\prime\prime}$ does not have level steps at height 0. Then \begin{align*} U_3(z)=1+z^2T_3(z)U_3(z). \end{align*} This proves part (1). \medskip \noindent Proof of part (2): From the definition of the Riordan array we have \begin{eqnarray*} L(z) &=&\sum_{n=0}^\infty\sum_{k=0}^\infty a(n-k,k)z^n\\ &=&\sum_{n=0}^\infty\sum_{k=0}^\infty [z^{n-k}]gf^{k}z^n\\ &=&\sum_{n=0}^\infty\sum_{k=0}^\infty gf^{k}z^{k}\\ &=&\dfrac{g}{1-zf}=\dfrac{T_3(z)}{1-z^2T_3(z)}. \end{eqnarray*} Therefore, comparing coefficients we get that $$U_3(z)=z^2L(z)+1.$$ This proves part (2). \end{proof} The following sequence gives some values for the total number of paths of length $0-10$ in paths $\C_3^+$ with no level steps at height 0. This sequence appears in OEIS as \seqnum{A185132}. So, $u_3(n)$ for $n=0,1, \dots,10$ is given by $$1, 4, 18, 84, 405, 2004, 10126, 52048, 271338, 1431400, 7627348.$$ \subsubsection{The inverse matrix of the Riordan array} Since $\A_3=\left[a_3(n,k)\right]_{n,k\geq 0}$ is a Riordan matrix and the set of all Riordan matrices is a group, the inverse matrix of $\A_3$ exists. So, it is natural to ask: what properties does the inverse matrix of $\A_3$ satisfy? In this section we analyze the inverse matrix $\A_3^{-1}$ and in particular, we study the combinatorial interpretation of the unsigned entries of the matrix $\A_3^{-1}$. We found that there is a combinatorial relation between the entries of $\A_3^{-1}$ and the words over the alphabet $\{ \texttt{0, 1, 2, 3}\}$. There is also another relation between the matrix $\A_3^{-1}$ and the matrix of coefficients of Chebyshev's polynomials of the second kind. Finally we present two fractals resulting from both matrices $\A_3$ and $\A_3^{-1}$. From \eqref{invRiordan} we obtain that the inverse matrix $\A_3^{-1}$ is given by the Riordan matrix \begin{equation}\label{Ref_equa} \widetilde{\F}:=\left[\widetilde{f}(n,k)\right]_{n,k\geq 0}=\A_3^{-1}=\left(\frac{1}{1+4z+z^2}, \frac{z}{1+4z+z^2} \right). \end{equation} In general if a Riordan matrix $[a_{n,k}]_{n, k\geq 0}=(g(z),f(z))$ is given, then the alternating Riordan matrix defined by $[(-1)^{n+k}a_{n,k}]_{n, k\geq 0}$ can be found by the product of Riordan matrices as follows $$(1,-z)(g(z),f(z))(1,-z)=(g(-z),-f(-z)).$$ Now from \eqref{Ref_equa} it is easy to see that $g(z)=1/(1+4z+z^2)$ and $f(z)=z/(1+4z+z^2)$. Therefore, $$\F:=\left[f(n,k)\right]_{n,k\geq 0}:=\left[(-1)^{n+k}\widetilde{f}(n,k)\right]_{n,k\geq 0}=\left(\frac{1}{1-4z+z^2}, \frac{z}{1-4z+z^2} \right).$$ We now express this matrix explicitly as follows (see also \seqnum{A207823}). $$\F=\left[f(n,k)\right]_{n,k\geq 0}= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 15 & 8 & 1 & 0 & 0 & 0 & 0 & 0 \\ 56 & 46 & 12 & 1 & 0 & 0 & 0 & 0 \\ 209 & 232 & 93 & 16 & 1 & 0 & 0 & 0 \\ 780 & 1091 & 592 & 156 & 20 & 1 & 0 & 0 \\ 2911 & 4912 & 3366 & 1200 & 235 & 24 & 1 & 0 \\ 10864 & 21468 & 17784 & 8010 & 2120 & 330 & 28 & 1 \\ \vdots&\vdots &\vdots & \vdots & \vdots &\vdots &\vdots &\vdots \\ \end{bmatrix}. $$ From the Fundamental Theorem of Riordan arrays we have \begin{align*} F(x,y)&:=\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}f(n,m)x^mz^n= \left(\frac{1}{1-4z+z^2}, \frac{z}{1-4z+z^2} \right) \frac{1}{1-xz}\\ &=\frac{1}{1-(4+x)z+z^2}. \end{align*} Therefore, the element $f(n,m)$ satisfies the following recurrence relation. \begin{align}\label{recf} f(n,m)=4f(n-1,m)+f(n-1,m-1)-f(n-2,m), \end{align} with $n, m\geq 1$, and the initial values $f(0,0)=1$ and $f(n,m)=0$ if $m>n$. Note that from \cite[Theorems 4.1 and 4.2]{HS} we obtain generating functions for the $A$-sequence and the $Z$-sequence of the Riordan array $\widetilde{\F}$ (and therefore for $\F$). So, we have \begin{eqnarray*} A_{\widetilde{\F}}(z)&=&\frac{z}{zT_3(z)}=\frac{1-4 z+\sqrt{1-8z+12z^2}}{2}\\ Z_{\widetilde{\F}}(z)&=&\frac{1}{zT_3(z)}(1-T_3(z))=\frac{-1-4 z+\sqrt{1-8z+12z^2}}{2z} \end{eqnarray*} and \begin{eqnarray*} A_{\F}(z)&=&\frac{z}{zT_3(-z)}=\frac{1+4z+\sqrt{1+8z+12z^2}}{2}\\ &=&1+4 z-z^2+4 z^3-17 z^4+76 z^5-354 z^6+1704 z^7-8421 z^8+\cdots\\ \end{eqnarray*} \begin{eqnarray*} Z_{\F}(z)&=&\frac{1}{zT_3(-z)}(1-T_3(-z))=\frac{-1+4 z+\sqrt{1+8z+12z^2}}{2z}\\ &=&4-z+4 z^2-17 z^3+76 z^4-354 z^5+1704 z^6-8421 z^7+ \cdots \end{eqnarray*} Therefore, the element $f(n,m)$ can be calculated by a complex linear combination of elements in the previous row: $$f(n+1,k+1)=f(n,k) + 4f(n,k+1)-f(n,k+2)+4f(n,k+3)-17f(n,k+4)+\cdots$$ This observation was made by the anonymous referee. The generating function $A_{\F}(z)$ can be also obtain from Theorem 3.2 of \cite{Merlini}. We observe that the matrix $\F$ is related to the coefficients of Chebyshev polynomials of the second kind $U_n(x)$. Recall that those polynomials are defined recursively as follows: $U_0(x)=1$, $U_1(x) =2x$ and $U_n(x)=2xU_{n-1}(x)-U_{n-2}(x)$ for $n\geq 2$. Equivalently, \begin{align} U_n(x)&=\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}(-1)^k\binom{n-k}{k}(2x)^{n-2k}\\ &=\sum_{k=0}^{n}(-1)^{(n-k)/2}\binom{(n+k)/2}{k}\left(\frac{1+(-1)^{n-k}}{2}\right)(2x)^{k}. \label{chebyeq} \end{align} The ordinary generating function of the polynomials $U_n(x)$ is $$U(x,z):=\sum_{n=0}^{\infty}U_n(x)z^n=\frac{1}{1-2xz+z^2}.$$ Thus, $$U\left(\frac{x+4}{2},z\right)=\frac{1}{1-(x+4)z+z^2}=F(x,y).$$ Therefore, this proves the following theorem. \begin{theorem}\label{teocheby} If $m$ and $n$ are non-negative integers, then \[ f(n,m)=u(n,m), \text{ where }u(n,m)=[z^nx^m]U\left((x+4)/2,z\right). \] \end{theorem} The following theorem gives an explicit expression for the entries $f(n,m)$. \begin{theorem} If $m$ and $n$ are non-negative integers, then \[f(n,m)=\sum_{k=m}^{n}(-1)^{(n-k)/2} \binom{(n+k)/2}{k}\binom{k}{m} \left(\frac{1+(-1)^{n-k}}{2}\right)4^{k-m}.\] \end{theorem} \begin{proof} Theorem \ref{teocheby} and Equation \eqref{chebyeq} imply that \begin{align*} f(n,m)&=[x^m]U_n\left(\frac{x+4}{2} \right)\\ &=[x^m]\sum_{k=0}^{n}(-1)^{(n-k)/2}\binom{(n+k)/2}{k}\left(\frac{1+(-1)^{n-k}}{2}\right)(x+4)^{k}\\ &=[x^m]\sum_{k=0}^{n}\sum_{j=0}^k (-1)^{(n-k)/2}\binom{(n+k)/2}{k} \binom {k}{j}\left(\frac{1+(-1)^{n-k}}{2}\right)4^{k-j}x^j\\ &=[x^m]\sum_{j=0}^n \left[\sum_{k=j}^{n}(-1)^{(n-k)/2} \binom{(n+k)/2}{k} \binom {k}{j} \left(\frac{1+(-1)^{n-k}}{2}\right)4^{k-j}\right]x^j\\ &=\sum_{k=m}^{n} (-1)^{(n-k)/2} \binom{(n+k)/2}{k} \binom{k}{m} \left(\frac{1+(-1)^{n-k}}{2}\right)4^{k-m}. \end{align*} This completes the proof. \end{proof} Using the combinatorial interpretation given in the sequence \seqnum{A261711} we obtain the following theorem. \begin{theorem} The entry $f(n,m)$ of the matrix $\F$ counts the number of words over the alphabet $\Sigma:=\{ \texttt{0, 1, 2, 3}\}$ of length $n+m$ having exactly $m$ occurrences of the word 01. \end{theorem} \begin{proof} Let $g(n,m)$ be the number of words over the alphabet $\Sigma:=\{ \texttt{0, 1, 2, 3}\}$ of length $n+m$ with exactly $m$ occurrences of the word $\texttt{01}$. For example, $g(3,2)=12$ with the words being \begin{align*} \texttt{01010} &&\texttt{01011} &&\texttt{01012} &&\texttt{01013} && \texttt{01001} &&\texttt{01101} \\ \texttt{01201} &&\texttt{01301} &&\texttt{00101} &&\texttt{10101} &&\texttt{20101} &&\texttt{30101}. \end{align*} We show that $g(n,m)$ satisfies the recurrence relation given in \eqref{recf} with the same initial values. Let $w$ be a word over the alphabet $\Sigma$ where $w$ has length $n+m$ and with exactly $m$ occurrences of the word \texttt{01}. Thus, $|w|=n+m$ and $|w|_{\texttt{01}}=m$ (the number of \texttt{01}'s in $w$). The word $w$ can be written in the form $w=w_1a$ where $a$ and $w$ are words over $\Sigma$ with $|a|=1$, $|w_1|=n+m-1$ and $|w_1|_{\texttt{01}}=m$, then there are $4g(n-1,m)$ ways. However, we have to subtract the cases where the last symbol of $w_1$ is $\texttt{0}$ and $a=\texttt{1}$. In this case we have $g(n-2,m)$ ways. On the other hand, the word $w$ can also be written as $w=w_1\texttt{01}$ with $|w_1|=n+m-2$ and $|w_1|_{\texttt{01}}=m-1$. So, there are $g(n-1,m-1)$ ways to do it. Hence, \[g(n,m)=4g(n-1,m)-g(n-2,m)+g(n-1,m-1) \text{ for }n, m\geq 1.\] It is easy to see that that $g(0,0)=1$ and $g(n,m)=0$ for $m>n$. Therefore, this holds $g(n,m)=f(n,m)$. \end{proof} \subsubsection{Fractals from the Riordan arrays} A natural question for infinite numerical arrays is: what is the parity behavior between the entries of the numerical array? (See, for example, the Sierpi{\'n}ski fractal.) Trying to answer this question for our matrices $\A_3$ and $\A_3^{-1}$ we evaluated (using \emph{Mathematica}$^{\text{\textregistered}}$) their entries $\bmod {\;2}$ and we found two interesting fractals (see Figure \ref{fractales}). An easy way to construct both fractals --without using \emph{Mathematica}$^{\text{\textregistered}}$-- is as follows. The entries of the fractal in Figure \ref{fractales} part (a) are obtained by evaluating the equation \eqref{recu1} $\bmod {\;2}$. The entries of the fractal in Figure \ref{fractales} part (b) are obtained by evaluating the equation \eqref{recf} $\bmod {\;2}$. Merlini and Nocentini \cite{MN} have studied some relations between Riordan arrays and fractal patterns. \begin{figure}[ht] \centering \includegraphics[scale=0.45]{sierpinsky_fractalA.eps} \hspace{.5cm} \includegraphics[scale=0.45]{sierpinsky_fractal_AInverse.eps} \caption{(a) Matrix $\A_3 \mod 2$ \hspace{2cm} (b) Matrix $\A_3^{-1} \mod 2$.} \label{fractales} \end{figure} \subsection{Counting paths in three-dimensional cube} The main theorem of this section counts the total number of paths, in three-dimensional cube, of length $m$ that end in the horizontal plane. Again the proof uses generating functions. \begin{theorem} In the three-dimensional cube the following hold: \begin{enumerate}[(1)] \item the generating function for the total number of paths of length $i$ in $\C_3$ is given by \[ G_3(z):=\sum_{i=0}^{\infty}g_3(i)z^i=\frac{1}{\sqrt{1-8z+12z^2}},\] \item the number of paths, in three-dimensional cube, of length $m$ that end in the horizontal plane is given by \[ g_3(m)= \frac{1}{2^m}\sum_{k=0}^{m}\binom{2m-2k}{m-k}\binom{2k}{k}3^k. \] \end{enumerate} \end{theorem} \begin{proof} From the first return decomposition a nonempty three-dimensional lattice path $T$ in $\C_3$ may be decomposed as \[e_3P(-e_3)T^{\prime}; \quad (-e_3)P(e_3)T^{\prime};\quad e_1T^{\prime};\quad -e_1T^{\prime};\quad e_2T^{\prime};\quad -e_2T^{\prime},\] where $P$ is a path (possibly empty) in $\C_3^+$ and $T^{\prime}$ is a path (possibly empty) in $\C_3$. Therefore, \begin{equation*} G_3(z)=2z^2T_3(z)G_3(z)+4zG_3(z)+1. \end{equation*} So, from equation \eqref{ecfibo1a} on page~\pageref{ecfibo1a} we obtain \begin{equation} \label{G3} G_3(z)=\frac{1}{1-4z-2z^2T_3(z)}=\frac{1}{\sqrt{1-8z+12z^2}}. \end{equation} This proves part (1). \medskip \noindent Proof of part (2): Noe \cite{Noe} showed that \[\displaystyle{\sum_{i=0}^\infty T_i x^i=\frac{1}{\sqrt{1-2bx-(b^2-4c)x^2}}},\] \noindent where \[\displaystyle{T_{n}=\frac{1}{4^{n}}\sum_{k=0}^{n} \binom{2n-2k}{n-k}\binom{2k}{k}(b+2\sqrt{c})^k(b-2\sqrt{c})^{n-k}.}\] \noindent Therefore, setting $b=4$ and $c=1$ we obtain the equation in part (2), completing the proof of the theorem. \end{proof} Note that the number $g_3(m)$ is equal to the generalized central trinomial coefficient of $(1+4x+x^2)^n$. Then $$g_3(n)=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{2k}{k}\binom{n}{2k}4^{n-2k}.$$ This sequence appears in OEIS as \seqnum{A081671}. So, $g_3(n)$ for $n=0, 1, \dots, 10$ is given by $$1, 4, 18, 88, 454, 2424, 13236, 73392, 411462, 2325976, 13233628.$$ In the following theorem we obtain another formula to the sequence $g_3(m)$. \begin{theorem} The number of paths, in three-dimensional cube, of length $m$ that end in the horizontal plane is given by \[ g_3(m)=4^m + \sum_{n=1}^m\sum_{k=0}^{\left\lfloor\frac{m-2n}{2}\right\rfloor}\binom{n+2k}{k}\binom{s}{2n+2k}\left(\frac{n}{n+2k}\right)2^{2m-4k-3n}. \] \end{theorem} \begin{proof} The Equations \eqref{relT3} and \eqref{G3} imply that \begin{align*} G_3(z)&=\frac{1}{1-4z-2z^2T_3(z)}=\frac{1}{1-4z-2z^2\left(1/(1-4z) \right)C(u)}\\ &= \frac{1}{1-4z} \left(\frac{1}{1-2uC(u)}\right)= \frac{1}{1-4z} \sum_{n=0}^{\infty}(2uC(u))^n, \end{align*} where $u=z^2/(1-4z)^2$ and $C(z)$ is the generating function of the Catalan numbers. From identity \eqref{powerCat} we have \begin{align*} G_3(z)&= \frac{1}{1-4z} + \sum_{n=1}^{\infty}\sum_{k=0}^{\infty}\binom{n+2k}{k}\left(\frac{n}{n+2k} \right)\left(\frac{z^{2n+2k}}{(1-4z)^{2n+2k+1}}\right)2^n\\ &= \frac{1}{1-4z} + \sum_{n=1}^{\infty}\sum_{k=0}^{\infty}\sum_{l=0}^{\infty}\binom{n+2k}{k}\binom{2n+2k+l}{l}\left(\frac{n}{n+2k}\right)2^{n+2l} z^{2n+2k+l}. \end{align*} This with $t=2n+2k+l$ implies that \begin{align*} G_3(z)&= \frac{1}{1-4z} + \sum_{n=1}^{\infty}\sum_{k=0}^{\infty}\sum_{l=t-2n-2k}^{\infty}\binom{n+2k}{k}\binom{t}{2n+2k}\left(\frac{n}{n+2k}\right) 2^{2t-3n-4k}z^t. \end{align*} Therefore, \begin{align*} [z^m]G_3(z)&= 4^m + \sum_{n=1}^{m}\sum_{k=0}^{\left\lfloor\frac{m-2n}{2}\right\rfloor}\binom{n+2k}{k}\binom{m}{2n+2k}\left(\frac{n}{n+2k}\right) 2^{2m-3n-4k}. \end{align*} This proves the theorem. \end{proof} Theorem \ref{guy:theorem} studies the case in which a path does not need to end in the horizontal plane. That is, we study the family of paths in $\C_3^\pm$. Theorem \ref{guy:theorem} was originally proved by Guy. \begin{theorem}\label{guy:theorem} In three-dimensional cube it holds that \begin{enumerate}[(1)] \item The generating function for the total number of paths of length $i$ in $\C_3^\pm$ is given by \[ W_3(z):=\sum_{i=0}^{\infty}w_3(i)z^i=\frac{1}{1-6z},\] \item the number of paths, in three-dimensional cube, of length $m$ is given by \[ w_3(m)=6^m. \] \end{enumerate} \end{theorem} \begin{proof} First of all we note that from the first return decomposition a nonempty three-dimensional lattice path $J$ in $\C_3^{\pm}$ may be decomposed as $$e_3J^{\prime}; \quad (-e_3)J^{\prime};\quad e_1J^{\prime};\quad (-e_1)J^{\prime};\quad e_2J^{\prime};\quad (-e_2)J^{\prime},$$ where $J^{\prime}$ is a path (possibly empty) in $\C_3^{\pm}$. Therefore, we have that \begin{equation*} W_3(z)=6zW_3(z)+1. \end{equation*} Therefore \begin{align*} W_3(z)=\frac{1}{1-6z}. \end{align*} This proves part (1) and (2). \end{proof} \section{Generating functions for paths in the \emph{n}-space} In this section we generalize the results given in Section \ref{section;three} for paths in three-dimensional cube to paths in the $n$-dimensional cube. In Section \ref{section;three} we classify the families of paths depending on the plane $z=0$. The generalization is focused depending on the hyperplane $x_n=0$. Since the results here are a natural generalization of Section \ref{section;three}, we omit some details. Whoever is interested in these problems from the point of view of Riordan arrays can see Nkwanta \cite{Nka}. \begin{theorem}\label{paths:Cplus} If $C_n$ is the $n$th Catalan number, then \begin{enumerate}[(1)] \item the generating function for the total number of paths of length $i$ in $\C_n^+$ is given by \begin{eqnarray*} T_n(z)&:=&\sum_{i=0}^{\infty}a_n(i)z^i=\frac{1-2(n-1)z-\sqrt{1-4(n-1)z+4(n-2)nz^2}}{2z^2} \\ &=&\cfrac{1}{1-2(n-1)z-\cfrac{z^2}{1-2(n-1)z- \cfrac{z^2}{1-2(n-1)z -\cfrac{z^2}{\ddots}}}} \end{eqnarray*} \item the number of paths in $\C_n^+(m)$ is given by \begin{align} \label{ecfiboo} a_n(m) =\sum_{i=0}^{\left\lfloor m/2\right\rfloor}C_i\binom{m}{2i}(2(n-1))^{m-2i}. \end{align} \end{enumerate} \end{theorem} \begin{proof} We prove part (1), the proof of part (2) is similar to Theorem \ref{TeoFibo1a} and we omit it. From the first return decomposition a nonempty $n$-dimensional lattice path $P$ in $\C_n^+$ may be decomposed as $$e_nP^{\prime}(-e_n)P^{\prime\prime}, \quad \pm e_1P^{\prime}, \quad \pm e_2P^{\prime},\quad \dots \quad , \pm e_{n-1}P^{\prime},$$ where $P^{\prime}$ is a path (possibly empty) in $\C_n^+$. Therefore \begin{equation*} T_n(z)=z^2T_n^2(z)+2(n-1)zT_n(z)+1. \end{equation*} This proves part (1). \end{proof} For example, if $n=2$, we obtain \[ T_2(z)=\frac{1-2z-\sqrt{1-4z}}{2z^2}=\sum_{n=0}^{\infty}C_{n+1}z^n. \] Therefore, $a_2(m)=C_{m+1}$, where $C_m$ is the $m$th Catalan number. Moreover, from Equation \eqref{ecfiboo} we get $$C_{m+1}=\sum_{i=0}^{\left\lfloor m/2 \right\rfloor}C_i\binom{m}{2i}2^{m-2i}.$$ This identity is known as Touchard's formula. In 2017 Dershowitz \cite{Dershowitz} found a bijection between the paths of $\C_2^+$ and Dyck paths. If $a_n(m,k)$ is the total number of lattice paths with height $k$ in $\C_{n}^{+}(m)$, then $a_n(m,k)$ satisfies the third order recurrence relation \begin{equation*} a_n(m,k)=a_n(m-1,k-1)+2(n-1)a_3(m-1,k)+a_3(m-1,k+1). \end{equation*} Therefore, the infinite triangular matrix $\A_n=\left[a_n(m,k)\right]_{m,k\geq 0}$ has the Riordan array expression $$ \A_n=\left(T_n(z), zT_n(z)\right),$$ with $A$-sequence equal to $(1,2(n-1),1)$. \begin{theorem}\label{Riordan:general} In the $n$-dimensional cube the following hold: \begin{enumerate}[(1)] \item the generating function for the total number of paths of length $i$ in $\C_n^{\geq}$ is given by \begin{eqnarray*} H_n(z)&:=&\sum_{i=0}^{\infty}b_n(i)z^i=\frac{T_n(z)}{1-zT_n(z)}\\ &=&\frac{1-2nz-\sqrt{1-4(n-1)z+4(n-2)nz^2}}{2z(2nz-1)}\\ &=&\cfrac{1}{1-2(n-1)z - \cfrac{z^2}{1-2(n-1)z-\cfrac{z^2}{1-2(n-1)z-\cfrac{z^2}{\ddots}}}} \end{eqnarray*} \item the number of paths that belong to $\C_n^{\geq}(m)$ is given by \begin{align}\label{exact} b_n(m)=\sum_{i=0}^{m}\sum_{k=0}^{\left\lfloor \frac{m-i}{2}\right\rfloor} \binom{i+2k+1}{k}\binom{m}{i+2k} \left(\frac{i+1}{i+2k+1}\right)(2(n-1))^{m-2k-i}. \end{align} \end{enumerate} \end{theorem} \begin{proof} We prove part (1), the proof of part (2) is analogous to the proof of Corollary \ref{Riordan:corollary} and we omit it. From the first return decomposition a nonempty $n$-dimensional lattice path $P$ in $\C_n^{\geq}$ may be decomposed as $P^{\prime}, \quad P^{\prime}e_nH^{\prime}$ where $P^{\prime}$ is a path (possibly empty) in $\C_n^+$ and $H^{\prime}$ is a path (possibly empty) in $\C_n^{\geq}$. Therefore \begin{equation*} H_n(z)=T_n(z)+zT_n(z)H_n(z). \end{equation*} This proves part (1). \end{proof} It is easy to see that using Guy \cite[Equation (1)]{GuyCatwalks}, the Equation \eqref{exact} for $n=2$ becomes \begin{align*} b_2(m)=\binom{2m+1}{m}=\sum_{i=0}^{m}\sum_{k=0}^{\left\lfloor \frac{m-i}{2}\right\rfloor} \binom{i+2k+1}{k}\binom{m}{i+2k} \left(\frac{i+1}{i+2k+1}\right)2^{m-2k-i}. \end{align*} Theorem \ref{Riordan:general} part (2) with $n=3$ proves the the problem \textbf{10795} \cite{deutsch}. This problem was originally proposed by Deutsch and solved by Brawner \cite{brawner} (without using generating functions). \begin{theorem}\label{horizonhyperplane} In the $n$-dimensional cube the following hold: \begin{enumerate}[(1)] \item the generating function for the total number of paths of length $i$ in $\C_n$ is given by \[ G_n(z):=\sum_{i=0}^{\infty}g_n(i)z^i=\frac{1}{\sqrt{1-4(n-1)z+4(n-2)nz^2}},\] \item the number of paths, in three-dimensional cube, of length $m$ that end in the horizontal plane is given by \[ g_n(m)=\frac{1}{2^m}\sum_{k=0}^{m}\binom{2m-2k}{m-k}\binom{2k}{k}n^k(n-2)^{n-k}.\] \end{enumerate} \end{theorem} \begin{theorem} In the $n$-dimensional cube the following hold: \begin{enumerate}[(1)] \item the generating function for the total number of paths of length $i$ in $\C_n^\pm$ is given by \[ W_n(z):=\sum_{i=0}^{\infty}w_n(i)z^i=\frac{1}{1-2nz},\] \item the number of paths, in the $n$-dimensional cube, of length $m$ is given by \[ w_n(m)=(2n)^m. \] \end{enumerate} \end{theorem} \section{A relation with the \emph{k}-colored Motzkin paths}\label{motsec} A \emph{Motzkin path} of length $n$ is a lattice path of $\mathbb{Z \times Z}$ running from $(0, 0)$ to $(n, 0)$ that never passes below the $x$-axis and whose permitted steps are the up diagonal step $U=(1, 1)$, the down diagonal step $D=(1,-1)$ and the horizontal step $H=(1, 0)$, called rise, fall, and level step, respectively. The number of Motzkin paths of length $n$ is the $n$th \emph{Motzkin number} $m_{n}$, (see \seqnum{A001006}). A \emph{grand Motzkin path} of length $n$ is a Motzkin path without the condition that it never passes below the $x$-axis. The number of grand Motzkin paths of length $n$ is the $n$th \emph{grand Motzkin number} $gm_{n}$ (see \seqnum{A002426}). A $k$-\emph{colored Motzkin path} is a Motzkin path such that each horizontal step is colored with one of $k$ specific colors. The number of $k$-colored Motzkin paths of length $n$ is the $n$th $k$-\emph{colored Motzkin number} $m_{k,n}$. The generating functions of these type of lattices where also studied by Callan \cite{callan}. Analogously, we have $k$-\emph{colored grand Motzkin paths}, the number of $k$-colored grand Motzkin paths of length $n$ is denoted by $gm_{k,n}$. It is easy to obtain a bijection between the 4-colored Motzkin paths of length $m$ and three-dimensional lattice path of $\C_3^+(m)$. That is, we identify the north-east step $(U)$ with $e_3=(1,0,0)$, the south-east step $(D)$ with $-e_3$ and the 4-colored horizontal steps with $\pm e_{1}$ and $\pm e_{2}$. Therefore, we obtain Theorem \ref{bijection:Motzkin} (it was proved originally by Nkwanta using Riordan arrays). By similar reasons as we obtained Theorem \ref{bijection:Motzkin}, we obtain also Theorem \ref{bijection:Motzkin2}. From Theorem \ref{paths:Cplus} part (2), the bijection given in Theorem \ref{bijection:Motzkin} and the recurrence relation given in \cite{Woan} (see also \cite{Schork}) we obtain the Corollary \ref{Corollary:bijection:Motzkin}. \begin{theorem} \label{bijection:Motzkin} The number of lattice paths of length $k$ in $\C_n^+$ is equal to the number of $2(n-1)$-colored Motzkin paths of length $k$. Thus, $a_n(k)=m_{2(n-1),k}$. \end{theorem} \begin{theorem} \label{bijection:Motzkin2} The number of lattice paths of length $k$ in $\C_n$ is equal to the number of $2(n-1)$-colored grand Motzkin paths of length $k$. Thus, $g_n(k)=gm_{2(n-1),k}$. \end{theorem} \begin{corollary}\label{Corollary:bijection:Motzkin} The numbers $a_n(m)$ given in Theorem \ref{paths:Cplus} part (2), satisfy the recurrence relation $$(m+2)a_n(m)=2(n-1)(2m+1)a_n(m-1)+(6-2n)(m-1)a_n(m-2).$$ \end{corollary} \section{Tables and sequences from experimentation} From formula \eqref{ecfiboo} we obtain the Table \ref{ndimen} (see Theorem \ref{TeoFibo1a} part (2), Theorem \ref{paths:Cplus}). That is, we show the first few terms of the sequence $a_n(m)$ for $n=2, 3, 4, 5$. Note that $a_2(3)=14$ and $a_3(3)=17$, (see Figures \ref{two:dimen} and \ref{3dimen}). From Theorem \ref{Riordan:general} part (2) we obtain the Table \ref{ndimen2z}. That is, we show the first few terms of the sequence $b_n(m)$ for $n=2, 3, 4, 5$. From Theorem \ref{horizonhyperplane} part (2) we obtain the Table \ref{ndimen2}. That is, we show the first few terms of the sequence $g_n(m)$ for $n=2, 3, 4, 5$. Note that the sequence \seqnum{A098410} is equal to the number of paths from $(0,0)$ to $(n, 0)$ using steps $U = (1, 1), H = (1, 0)$ and $D = (1,-1)$, the $H$ steps can have 6 colors. \begin{table} \centering \begin{tabular}{|c|l|c|}\hline $n$ & Sequence & A-Sequence \\ \hline 2 & 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 & \seqnum{A000108} \\ \hline 3 & 1, 4, 17, 76, 354, 1704, 8421, 42508, 218318& \seqnum{A005572} \\ \hline 4 & 1, 6, 37, 234, 1514, 9996, 67181, 458562, 3172478 & \seqnum{A025230} \\ \hline 5 & 1, 8, 65, 536, 4482, 37968, 325509, 2821400 & - \\ \hline \end{tabular} \caption{Sequence $a_n(m)$ for $n=2, 3, 4, 5$.} \label{ndimen} \end{table} \begin{table} \centering \begin{tabular}{|c|l|c|}\hline $n$ & Sequence & A-Sequence \\ \hline 2 & 1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716 & \seqnum{A001700} \\ \hline 3 & 1, 5, 26, 139, 758, 4194, 23460, 132339, 751526, 4290838 & \seqnum{A005573} \\ \hline 4 & 1, 7, 50, 363, 2670, 19846, 148772, 1122995, 8525398, 65030706 & - \\ \hline 5 & 1, 9, 82, 755, 7014, 65658, 618612, 5860611, 55784710, 533147438 & - \\ \hline \end{tabular} \caption{Sequence $b_n(m)$ for $n=2, 3, 4, 5$.} \label{ndimen2z} \end{table} \begin{table} \centering \begin{tabular}{|c|l|c|}\hline $n$ & Sequence & A-Sequence \\ \hline 2 & 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620 & \seqnum{A000984} \\ \hline 3 & 1, 4,18, 88, 454, 2424, 13236, 73392, 411462 & \seqnum{A081671} \\ \hline 4 & 1, 6, 38, 252, 1734, 12276, 88796, 652728 & \seqnum{A098410} \\ \hline 5 & 1, 16, 258, 4192, 68614, 1130976, 18766356 & - \\ \hline \end{tabular} \caption{Sequence $g_n(m)$ for $n=2, 3, 4, 5$.} \label{ndimen2} \end{table} \begin{proposition}\label{prop:easy} For $k\ge 1$, the number of paths in $\C_{3}^{+}(k)$ that are completely contained in the $xy$-plane is $4^{k}$. \end{proposition} Proposition \ref{prop:easy} is easy to prove, we omit it. Motivated by Proposition \ref{prop:easy}, we have the following conjectures. \noindent {\bf Conjecture 1:} For $k\ge 1$, the number of paths in $\C_{3}^{+}(k)$ that are completely contained in the $xz-$plane is (see Table \ref{XZplane} first line) \[\displaystyle{\sum_{i=1}^{k+1}\frac{\binom{2\,i}{i}\, \binom{k}{i-1}}{i+1}}.\] \noindent {\bf Conjecture 2:} For $k\ge 1$, the number of paths in $\C_{3}^{+}(k)$ that are completely contained in the $yz-$plane is \[\displaystyle{\sum_{i=1}^{k+1}\frac{\binom{2\,i}{i} \binom{k}{i-1}}{i+1}}.\] For the Conjecture 1 see Table \ref{XZplane} first line and for the Conjecture 2 see Table \ref{XZplane} second line. Notice that first and second lines in Tables \ref{XZplane} are exactly the same. The following sequences/conjectures are based on our experimentation. We do not prove and/or provide any closed formulas for any of them here. We leave them as conjectures for future work. \begin{table} \centering \begin{tabular}{|c|c|c|}\hline plane &Sequence & A-Sequence \\ \hline $xz$-plane &3, 10, 36, 137, 543, 2219, 9285, 39587, 171369 & \seqnum{A002212}$(k+1)$ \\ \hline $yz$-plane &3, 10, 36, 137, 543, 2219, 9285, 39587, 171369 & \seqnum{A002212}$(k+1)$ \\ \hline \end{tabular} \caption{Paths in $\C_{3}^{+}(k)$ completely contained in the $xz$-plane or the $yz$-plane.} \label{XZplane} \end{table} If we define the \emph{altitude} of a path $P$ in $\C_{3}^{+}(k)$ as the largest $z$-value of all the points in $P,$ then we have the following conjecture. \noindent {\bf Conjecture 3:} The number of paths in $\C_{3}^{+}(k)$ that have altitude 1 is $$\dfrac{3^k}{2}-4^k+\dfrac{5^k}{2}.$$ \begin{table} \centering \begin{tabular}{|c|l|c|}\hline $h$ & Sequence & A-Sequence \\ \hline 0 & 4, 16, 64, 256, 1024, 4096, 16384, 65536 & \seqnum{A002212} \\ \hline 1 & 0, 1, 12, 97, 660, 4081, 23772, 133057, 724260 & \seqnum{A016753} \\ \hline 2 & 0, 0, 0, 1, 20, 243, 2324, 19271, 145404 & - \\ \hline 3 & 0, 0, 0, 0, 0, 1, 28, 453, 5556 & - \\ \hline \end{tabular} \caption{All paths of altitude $h$ in $\C_{3}^{+}(k).$} \label{altitude} \end{table} We say that a path $P = (p_0,p_1, \ldots, p_k)$ in $\C_{3}^{+}(k)$ has a \emph{right corner}, if there are three points $p_{i}, p_{i+1}, p_{i+2} \in \{p_0,p_1, \ldots, p_k\}$ such that the vectors $\overrightarrow{p_{i}p_{i+1}}$ and $\overrightarrow{p_{i+1}p_{i+2}}$ are perpendicular. Using this definition, we have Table \ref{rightCorner}. \begin{table} \centering \begin{tabular}{|c|l|c|}\hline $r$ & Sequence & A-Sequence \\ \hline 0 & 4, 9, 16, 34, 64, 133, 256, 526, 1024 & - \\ \hline 1 & 0, 8, 40, 112, 304, 736, 1768, 4048, 9232 & - \\ \hline 2 & 0, 0, 20, 136, 552, 1808, 5380, 14760, 38936 & - \\ \hline 3 & 0, 0, 0, 72, 512, 2576, 9856, 33832, 104832 & - \\ \hline \end{tabular} \caption{All paths in $\C_{3}^{+}(k)$ with exactly ``$r$'' right corners.} \label{rightCorner} \end{table} We say that a path $P = (p_0,p_1, \ldots, p_k)$ in $\C_{3}^{+}(k)$ has an \emph{overlap}, if there are four points $p_{i}, p_{i+1}, p_{i+2}, p_{i+3} \in \{p_0,p_1, \ldots, p_k\}$ such that $p_{i}=p_{i+3}$ and $p_{i+1}=p_{i+2}$. Using this definition, we have Table \ref{overlap}. \begin{table} \centering \begin{tabular}{|c|l|c|}\hline $t$ & Sequence & A-Sequence \\ \hline 0 & 4, 12, 40, 152, 608, 2476, 10240, 42972, 182904 & - \\ \hline 1 & 0, 5, 32, 132, 580, 2764, 13420, 64260, 306388 & - \\ \hline 2 & 0, 0, 4, 65, 416, 2052, 10448, 55688, 297516 & - \\ \hline 3 & 0, 0, 0, 5, 96, 953, 6212, 34904, 197824 & - \\ \hline \end{tabular} \caption{All paths in $\C_{3}^{+}(k)$ with exactly ``$t$'' overlaps.} \label{overlap} \end{table} \begin{remark} Some of the results of this paper were discovered by using the counting automata methodology (see De Castro et al.~\cite{ramirez}). \end{remark} \section{Acknowledgments} The authors thank the referees for their comments which helped to improve the article. The first author was partially supported by The Citadel Foundation and the Mathematics department of Universidad Sergio Arboleda. The last author started working on this project when he was in a short research visit at The Citadel. \begin{thebibliography}{99} \bibitem{brawner} J.~Brawner, Three-dimensional lattice walks in the upper half-space, solution of problem \#10795, \emph{Amer. Math. Monthly}, {\bf 108} (2001), 980. \bibitem{callan} D.~Callan, On generating functions involving the square root of a quadratic polynomial, \emph{J. Integer Seq.} {\bf 10} (2007), \href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Callan/callan301.html}{Article 07.5.2}. \bibitem{cheon} G.~S.~Cheon, H.~Kim, and L.~W. Shapiro, A generalization of Lucas polynomial sequence, \emph{Discrete Appl. Math.} {\bf 157} (2009), 920--927. \bibitem{ramirez} R.~De~Castro, A.~Ram\'irez, and J.~L.~Ram\'irez, Applications in enumerative combinatorics of infinite weighted automata and graphs, \emph{Sci. Ann. Comput. Sci.} {\bf 24} (2014), 137--171. \bibitem{deutsch} E.~Deutsch, Problem \#10795: Three-dimensional lattice walks in the upper half-space, \emph{Amer. Math. Monthly}, {\bf 107} (2000), 367. \bibitem{Dershowitz} N.~Dershowitz, Touchard's Drunkard, \emph{J. Integer Seq.} \textbf{20} (2017), \href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Dershowitz/dersh3.html}{Article 17.1.5}. \bibitem{flajolet2} P.~Flajolet and R.~Sedgewick, \emph{Analytic Combinatorics}, Cambridge, 2009. \bibitem{GKP} R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik, \emph{Concrete Mathematics: A Foundation for Computer Science}, Addison-Wesley, 1994. \bibitem{GuyCatwalks} R.~K.~Guy, Catwalks, sandsteps and Pascal pyramids, \emph{J. Integer Seq.} {\bf 3} (2000), \href{https://cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html}{Article 00.1.6}. \bibitem{krattenthalerguy} R.~K.~Guy, C.~Krattenthaler, and B.~Sagan, Lattice paths, reflections, and dimension-changing bijections, \emph{Ars Combin.} {\bf 34} (1992), 3--15. \bibitem{HS} T-X.~He and R.~Sprugnoli, the, \emph{Discrete Appl. Math.} {\bf 309} (2009), 3962--3974. \bibitem{hirschhorn} M.~Hirschhorn, Problem 1517, \emph{Crux Mathematicorum} {\bf 17} (1991), 119--122. \bibitem{MN} D.~Merlini and M.~Nocentini, Patterns in Riordan arrays, \emph{Second International Symposium on Riordan Arrays and Related Topics}, Lecco, Italy, 2015. \bibitem{Merlini} D.~Merlini, D.~G.~Rogers, R.~Sprugnoli, and M.~C.~Verri, On some alternative characterizations of Riordan arrays, \emph{Canadian J. Math.} {\bf 49} (1997), 301--320. \bibitem{Sprugnoli2} D.~Merlini, D.~G.~Rogers, R.~Sprugnoli, and M.~C.~Verri, Underdiagonal lattice paths with unrestricted steps, \emph{Discrete Appl. Math.} {\bf 91} (1999), 197--213. \bibitem{MS} D.~Merlini and R.~Sprugnoli, Arithmetic into geometric progressions through Riordan arrays, \emph{Discrete Math.} {\bf 340} (2017), 160--174. \bibitem{Lagrange} D.~Merlini, R.~Sprugnoli, and M.~C.~Verri, Lagrange inversion: when and how, \emph{Acta Appl. Math}. \textbf{94} (2006), 233--249. \bibitem{MSV} D.~Merlini, R.~Sprugnoli, and M.~C.~Verri, Algebraic and combinatorial properties of simple, coloured walks, in \emph{Trees in Algebra and Programming: Prod. CAAP 1994}, Lecture Notes in Comput. Sci., Vol. 787, Springer, 1994, pp. 218--233. \bibitem{Noe} T.~D.~Noe, On the divisibility of generalized central trinomial coefficients, \emph{J. Integer Seq.} {\bf 9} (2006), \href{https://cs.uwaterloo.ca/journals/JIS/VOL9/Noe/noe35.html}{Article 06.2.7}. \bibitem{Nka} A.~Nkwanta, Riordan matrices and higher-dimensional lattice walks, \emph{J. Statist. Plann. Inference}, {\bf 140} (2010), 2321--2334. \bibitem{RAM} J.~L.~Ram\'irez and V.~F.~Sirvent, A generalization of the $k$-bonacci sequence from Riordan arrays, \emph{Electron. J. Combin.} {\bf 22} (2015), Art. P1.38. \bibitem{RAM2} J.~L.~Ram\'irez and V.~F.~Sirvent, Generalized Schr\"{o}der matrix and its combinatorial interpretation, \emph{Linear Multilinear Algebra}, In Press, 2017. \bibitem{Rogers} D.~G.~Rogers, Pascal triangles, Catalan numbers and renewal arrays, \emph{Discrete Math.} {\bf 22} (1978), 301--310. \bibitem{Sands} B.~Sands, Problem 1517, \emph{Crux Mathematicorum}, {\bf 16} (1990), 44. \bibitem{Schork} M.~Schork, On the recursion relation of Motzkin numbers of higher rank, \emph{Online J. Anal. Comb.} \textbf{2} (2007). \bibitem{Riordan} L.~W.~Shapiro, S.~Getu, W.~Woan, and L.~Woodson, The Riordan group, \emph{Discrete Appl. Math.} {\bf 34} (1991), 229--239. \bibitem{Sprugnoli} R.~Sprugnoli, Riordan arrays and combinatorial sums, \emph{Discrete Math.} {\bf132} (1994), 267--290. \bibitem{OEIS} N.~J.~A. Sloane, \emph{The On-Line Encyclopedia of Integer Sequences}, \url{http://oeis.org}. \bibitem{Woan} W.~Woan, A recursive relation for weighted Motzkin, \emph{J. Integer Seq.} {\bf 8} (2005), \href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Woan/woan11.html}{Article 05.1.6}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A19, 15A24. \noindent \emph{Keywords: } lattice paths, Riordan arrays, combinatorial proof. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A000984}, \seqnum{A001006}, \seqnum{A001700}, \seqnum{A002426}, \seqnum{A005572}, \seqnum{A005573}, \seqnum{A025230},\seqnum{A052177}, \seqnum{A052178}, \seqnum{A052179}, \seqnum{A081671}, \seqnum{A098410}, \seqnum{A185132}, \seqnum{A207823}, \seqnum{A261711}) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 16 2017; revised versions received October 11 2017; November 20 2017. Published in {\it Journal of Integer Sequences}, December 20 2017. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}