\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage{graphicx}
\usepackage{enumitem}
\usepackage{makecell}
\usepackage{diagbox}


\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\sdiag}{sdiag}

\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}
\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}}}

\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
Enumeration of Certain $k$-Block Partitions\\
\vskip .12in
of Barry}
\vskip 1cm
\large
Bulat Khaidarov\\
Grintek Ltd.\\
Khuroson 1, Ulugbek\\
100214 Tashkent\\
Uzbekistan\\
\href{mailto:bulat.khaidarov@gmail.com}{\tt bulat.khaidarov@gmail.com} \\
\end{center}

\vskip .2in

\begin{abstract}
The OEIS sequence \seqnum{A080416}, proposed by Barry, is a Stirling-like number triangle defined by a paired decomposition of $C(n+3,3)$. The recurrence formula for this sequence can be derived from an article by Corcino et al. However, explicit formulas have not been discovered. In this paper, we derive two formulas for calculating the members of this sequence. One of them involves matrix multiplication, while the other one does not require it. We also generalize the approach for sequences defined by counting North-East lattice paths with weights.
\end{abstract}


\section{Introduction}
The sequence \seqnum{A080416} from the {\it On-Line Encyclopedia of Integer
Sequences} (OEIS) was first proposed by Barry in 2003 \cite{OEIS}. As stated by Gonzalez, it ``gives the number of ways to construct pairs of $k$-block partitions from $1$ to $n$ such that the sum of the minima of the $i$\textsuperscript{th} block of the first partition and the $(k-i+1)$\textsuperscript{th} block of the second partition is $n+1$" \cite{OEIS}.

In 2022, Lavrov \cite{stackexchange, OEIS} noted that the results of a paper by Corcino et al.\ \cite{corcino} imply the following recursive formula for this sequence:
\begin{equation}\label{int1}s(\beta, n, k) = \begin{cases}
      1, & \text{if $n=k=0$;} \\
      0, & \text{if $n=0$ XOR $k=0$;} \\
      s(\beta+1, n-1,k-1) + \beta \cdot k \cdot s(\beta, n-1, k), & \text{otherwise.}
   \end{cases}
   \end{equation}
   
The triangle given by $s(0,n,k)$ looks as follows \cite{stackexchange}:
\begin{equation}\label{int2}\begin{matrix}
 s(0,2,2) & & & & \\
 s(0,3,2) & s(0,3,3) & & & \\
 s(0,4,2) & s(0,4,3) & s(0,4,4) & & \\
 s(0,5,2) & s(0,5,3) & s(0,5,4) & s(0,5,5) & \\
 s(0,6,2) & s(0,6,3) & s(0,6,4) & s(0,6,5) & s(0,6,6) \\
\end{matrix}
= 
\begin{matrix}
 & 1 & & & & \\
 & 1 & 1 & & & \\
 & 1 & 4 & 1 & & \\
 & 1 & 12 & 10 & 1 & \\
 & 1 & 32 & 67 & 20 & 1 \\
\end{matrix}.\end{equation}

We will start from the recursive formula \eqref{int1} and derive two non-recursive formulas. The first of them involves matrix multiplication, while the second one is matrix-free.

\section{Deriving a matrix-based formula}

Formula \eqref{int1} represents recurrence relations in three dimensions. However, if we fix $k$, we notice that all the recurrence relations needed to calculate $s(0,n,k)$ lie in one plane. Thus, for $s(0,n,k)$ with fixed $k$, we can reconstruct the recurrence in two dimensions.

Let $j = n-k$, $a=k+\beta$, and $S_a(k,j) = s(a-k,j+k,k)$. The $(k,j)$ coordinate system allows us to use North-East lattice paths with weights $1$ (East) and $k(a-k)$ (North):
\begin{displaymath}
S_a(k,j) = \begin{cases}
    1, & \text{if $j = k = 0$;} \\
    0, & \text{if $j<0$ or $k<0$;} \\
    S_a(k-1,j) + k\cdot (a-k)\cdot S_a(k,j-1), & \text{otherwise.}
   \end{cases}
\end{displaymath}

Thus,
\begin{displaymath}s(0,n,a) = S_a(a,n-a)=S_a(a-1, n-a) + 0 = S_a(a-1, n-a).\end{displaymath}

We can evaluate $S_a(a-1, n-a)$ by calculating the values of $S_a(k, j)$ at diagonals starting from the $(a-1)$-element diagonal $\{(1,0),(2,-1),\ldots,(a-1,-a+2)\}$ (we choose the first element of this diagonal to be at $(1,0)$ due to the fact that $S_a(1,0) = S_a(0,0)$, while $S_a(0,j) = 0$ for all $j \neq 0$). The corresponding values of $S_a(k, j)$ for this diagonal can be accumulated in the vector
\begin{displaymath}c_0 = \begin{bmatrix}
1\\
0\\
\vdots\\
0\\
0
\end{bmatrix}.\end{displaymath}

The values of $S_a(k, j)$ for the higher diagonal $\{(1,1),(2,0),\ldots,(a-1,-a+3)\}$ can be calculated by matrix-vector multiplication:
\begin{equation}\label{int5}c_1= A\cdot c_0 = \begin{bmatrix}
a-1 & 0 & 0 & \cdots & 0 & 0 & \cdots\\
1 & 2(a-2) & 0 & \cdots & 0 & 0 & \cdots\\
0 & 1 & 3(a-3) & \cdots & 0 & 0 & \cdots\\
\vdots\\
0 & 0 & 0 & \cdots & 1 &k(a-k)&\cdots \\
\vdots
\end{bmatrix} \cdot \begin{bmatrix}
1\\
0\\
\vdots\\
0\\
0
\end{bmatrix}.\end{equation}
In formula \eqref{int5}, $k$ is the column number of the $(a-1)\times(a-1)$ matrix $A$.

The value of $S_a(a-1, n-a)$ is the last entry of the vector $c_{n-2}$:
\begin{displaymath}c_{n-2}= A^{n-2}\cdot c_0.\end{displaymath}

Thus, for all $n\geq a \geq 2$:
\begin{equation}\label{int7}s(0,n,a) = \begin{bmatrix}0 & \cdots & 0 & 1\end{bmatrix}\cdot\begin{bmatrix}
a-1 & 0 & 0 & \cdots & 0 & 0 & \cdots\\
1 & 2(a-2) & 0 & \cdots & 0 & 0 &\cdots\\
0 & 1 & 3(a-3) & \cdots & 0 & 0 &\cdots\\
\vdots\\
0 & 0 & 0 & \cdots & 1 &k(a-k)& \cdots \\
\vdots
\end{bmatrix}^{n-2} \cdot \begin{bmatrix}
1\\
0\\
\vdots\\
0\\
0\\
\end{bmatrix}.
\end{equation}

Using formula \eqref{int7}, we evaluated the first entries of the sequence and listed them in Table~\ref{tab:1}.

\begin{table}[h]
\centering
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|}
\hline
\diagbox{n}{a} & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$  \\
\hline\hline
$2$ & $1$ & & & & & & & & & \\ \hline
$3$ & $1$ & $1$ & & & & & & & & \\ \hline
$4$ & $1$ & $4$ & $1$ & & & & & & & \\ \hline
$5$ & $1$ & $12$ & $10$ & $1$ & & & & & & \\ \hline
$6$ & $1$ & $32$ & $67$ & $20$ & $1$ & & & & & \\ \hline
$7$ & $1$ & $80$ & $376$ & $252$ & $35$ & $1$ & & & & \\ \hline
$8$ & $1$ & $192$ & $1909$ & $2560$ & $742$ & $56$ & $1$ & & & \\ \hline
$9$ & $1$ & $448$ & $9094$ & $22928$ & $12346$ & $1848$ & $84$ & $1$ & & \\ \hline
$10$ & $1$ & $1024$ & $41479$ & $189120$ & $177599$ & $46912$ & $4074$ & $120$ & $1$ & \\ \hline
$11$ & $1$ & $2304$ & $183412$ & $1472704$ & $2318149$ & $1013936$ & $149644$ & $8184$ & $165$ & $1$ \\ \hline
\end{tabular}
\caption{Triangular array of the numbers $s(0,n,a)$ up to $n=11$.}\label{tab:1}
\end{table}

In the OEIS \cite{OEIS}, there is a list of values of the first 50 members of the sequence, and they are the same as given in Table~\ref{tab:1}.


\section{Deriving a matrix-free formula}

The value of $s(0,n,a)$ is given in the $(a-1,1)$ entry (the bottom left corner) of the $(a-1)\times(a-1)$ matrix $A^{n-2}$.

Let $C_w$ denote a matrix in which all entries located $w$ positions to the left of the main diagonal are $1$, while all other entries are $0$. In this case,
\begin{displaymath}A= D + C_1 = \diag (a-1, 2(a-2), \ldots, i(a-i), \ldots)+C_1,\end{displaymath}
where $i$ is the row number.

The matrices $C_w$ have the following property:
\begin{equation}\label{int8}C_w = C_1^w.
\end{equation}

When we expand $(D+C_1)^{n-2}$, we are interested only in those terms that change the $(a-1,1)$ entry of the final matrix and thus only in those of them that have $a-2$ factors of $C_1$ (due to formula \eqref{int8}). Thus, $s(0,n,a)$ is the $(a-1,1)$ entry of the matrix that is the sum of all possible products of the following form:
\begin{equation} \label{int9}\underbrace{D \cdots D}_{t_1} \cdot C_1 \underbrace{D \cdots D}_{t_2} \cdot C_1 \cdots C_1 \underbrace{D \cdots D}_{t_{a-1}}= D^{t_1}\cdot C_1 \cdot D^{t_2}\cdot C_1\cdots C_1\cdot D^{t_{a-1}},
\end{equation}
where $\sum t_m = n-a$.

This leads to investigating a product of matrices of the form $C_1\cdot D^m$. For this purpose, let us call a matrix that was derived from a diagonal matrix by shifting all its entries by $w$ positions downwards a {\it$w$-shifted diagonal matrix\it}, and let $\sdiag_w (d_i)$ denote it, where $d_i$ is a formula for evaluating the element of the $i$\textsuperscript{th} column on the shifted diagonal.

With this notation,
\begin{align*}
\sdiag_p (x_i)\cdot \sdiag_r (y_i) &= \sdiag_{p+r}( x_{i+r}y_i), \\
C_w &= \sdiag_w (1), \\
D &=\sdiag_0(i(a-i)), \\
C_1\cdot D &= \sdiag_1 (i(a-i)),\\
C_1\cdot D^t &= \sdiag_1 (i^t(a-i)^t).\end{align*}
Then \eqref{int9} is equivalent to
\begin{displaymath}D^{t_1}\prod_{m=2}^{a-1}\sdiag_1 (i^{t_m}(a-i)^{t_m})\end{displaymath}
that can be simplified to
\begin{equation} \label{int10}\sdiag_{a-2}\bigl(\prod_{i=1}^{a-1}i^{t_{a-i}}(a-i)^{t_{a-i}}\bigr).\end{equation}

Let $p_i=t_{a-i}$. Then the $(a-1,1)$ entry of matrix \eqref{int10} is
\begin{displaymath}\prod_{i=1}^{a-1}i^{p_i}(a-i)^{p_i}.\end{displaymath}
The value of $s(0,n,a)$ is a sum of such products for all possible $p_i$ ($p_i \geq 0$, while $\sum_{i=1}^{a-1} p_i = n - a$). Thus,
\begin{equation} \label{int11}s(0,n,a) = \sum_{\sum p_i = n - a}\bigl(\prod_{i=1}^{a-1}i^{p_i}(a-i)^{p_i}\bigr).\end{equation}

Using formula \eqref{int11}, we get for $a=3$ and $4$:
\begin{align*}s(0,n,3) &= (n-2)\cdot 2^{n-3}, \\
s(0,n,4) &= 3^{n-4}\sum_{p_2=0}^{n-4} \bigl( (\frac{4}{3})^{p_2} \cdot (n-3-p_2)\bigr).\end{align*}

\section{Generalization of the approach}

The derivation of formulas \eqref{int7} and \eqref{int11} can be viewed as a special case of investigating the sequence $S_a(a,j)$ with corresponding North-East lattice paths in the $(x,y)$ coordinate system with weights $N(x)$ and $E(x)$ (that may include $a$ and $j$ in their formulas) for North and East directions:
\begin{displaymath}S_a(x,y) = N(x)\cdot S_a(x, y-1) + E(x)\cdot S_a(x-1, y).\end{displaymath}

If we assume the offset $S_a(0,0) = b$, then a matrix-based formula (using $(a+1)\times(a+1)$ matrices, because for the general case, our first diagonal starts at $(0,0)$ and ends at $(a,-a)$) is
\begin{equation} \label{int12}S_a(a,j) = b\begin{bmatrix}
0 & 0 & \cdots & 0 & 1\end{bmatrix}(\sdiag_0(N(i-1))+\sdiag_1(E(i)))^{a+j}\begin{bmatrix}
1\\
0\\
\vdots\\
0\\
0
\end{bmatrix},\end{equation}
while a matrix-free formula is
\begin{equation} \label{int13}S_a(a,j) = b\bigl(\prod_{i=1}^{a}E(i)\bigr)\sum_{\sum_{i=1}^{a+1} p_i = j}\bigl(\prod_{i=1}^{a+1}N^{p_i}(i-1)\bigr).\end{equation}
In our case (\seqnum{A080416}), $j=n-a$, $E(i)=b=1$, $N(i-1) = (i-1)(a+1-i)$.

Formulas \eqref{int12} and \eqref{int13} can be applied to sequences defined by counting North-East lattice paths with weights. Some examples of such sequences are given in Table~\ref{tab:2}.

\begin{table}[H]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
$b$ & $N(i)$ & $E(i)$ & Description & Sequence \\
\hline\hline
$1$ & $\text{const}$ & $\text{const}$ & \makecell{triangles of coefficients\\ in expansion\\ of $(E+N\cdot x)^n$} & $\makecell{\seqnum{A013609}\text{--}\seqnum{A013628}\text{, }\seqnum{A027465}\text{--}\\
\seqnum{A027467}\text{, }\seqnum{A038207}\text{, }\seqnum{A038208}\text{,} \\
\seqnum{A038210}\text{, } \seqnum{A038212}\text{, } \seqnum{A038214}\text{--}\\
\seqnum{A038218}\text{, } \seqnum{A038220}\text{--}\seqnum{A038222}\text{,} \\
\seqnum{A038224}\text{, } \seqnum{A038226}\text{--}\seqnum{A038234}\text{,}  \\
\seqnum{A038236}\text{, } \seqnum{A038238}\text{--}\seqnum{A038248}\text{,}\\ \seqnum{A038250}\text{--}\seqnum{A038260}\text{, }\seqnum{A038262}\text{--} \\
\seqnum{A038338}\text{, } \seqnum{A123187}\text{, } \seqnum{A147716}\text{,} \\
\seqnum{A303901}\text{, } \seqnum{A317498} }$ \\ \hline
$1$ & $i$ & $1$ & \makecell{\text{Stirling numbers} \\ \text{of the second kind}} & \seqnum{A008277}  \\ \hline
$1$ & $i+2$ & $1$ & \makecell{\text{a matrix product of} \\ \text{the Stirling numbers} \\ \text{of the second kind with} \\ \text{the binomial coefficients}} & \seqnum{A126351}  \\ \hline
$1$ & $i+1$ & $1$ & $\makecell{\text{the reflected triangle} \\ \text{of Stirling numbers} \\ \text{of the second kind}}$& \seqnum{A008278}  \\ \hline
$1$ & $i+1$ & $i+1$ & $\displaystyle \genfrac{\{}{\}}{0pt}{}{n}{n-k+1}(n-k+1)!$ & \seqnum{A090582}  \\ \hline
$1$ & $i+1$ & $i$ & $\displaystyle\genfrac{\{}{\}}{0pt}{}{n}{k}(k-1)!$ & \seqnum{A028246}, \seqnum{A130850}  \\ \hline
$1$ & $2^i$ & $1$ & $\makecell{\text{the triangle of Gaussian} \\ \text{binomial coefficients } [n,k] \\
\text{for }q = 2}$ & \seqnum{A022166}  \\ \hline
$1$ & $2^i$ & $2^i$ & & \seqnum{A108084}\\ \hline
$1$ & $1$ & $j+i$ & $\displaystyle \frac{n!}{(n-k)!}\genfrac{(}{)}{0pt}{}{n}{k}$ & \seqnum{A144084} \\ \hline
$1$ & $1$ & $a+j+i$ & $\displaystyle \frac{(n+k)!}{(n-k)!\, k!}$ & \seqnum{A113025} \\ \hline
$1$ & $a+i$ & $1$ & $ $ & \seqnum{A143395} \\ \hline

\end{tabular}
\caption{Sequences defined by counting North-East lattice
paths with weights.}\label{tab:2}
\end{table}

\section{Acknowledgments}
The author thanks the anonymous referee for careful reading and helpful suggestions.

\begin{thebibliography}{9}

\bibitem{corcino} R. B. Corcino, K. J. M. Gonzales, M. J. C. Loquias, and E. L. Tan, Dually weighted Stirling-type sequences, arxiv preprint arXiv:1302.4694 [math.CO], 2013. Available at \url{https://arxiv.org/abs/1302.4694}.

\bibitem{stackexchange} M. Lavrov, Finding a closed form for this sequence (\seqnum{A080416}), thread answer. Available at \url{https://math.stackexchange.com/questions/4550888}.

\bibitem{OEIS} N. J. A. Sloane et al., \emph{The On-Line Encyclopedia of Integer Sequences}, 2026. Published electronically at \url{https://oeis.org}.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 11B83; Secondary 05A10.

\noindent \emph{Keywords: }
shifted diagonal matrix, Stirling-like number, North-East lattice paths.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A008277},
\seqnum{A008278},
\seqnum{A013609},
\seqnum{A013610},
\seqnum{A013611},
\seqnum{A013612},
\seqnum{A013613},
\seqnum{A013614},
\seqnum{A013615},
\seqnum{A013616},
\seqnum{A013617},
\seqnum{A013618},
\seqnum{A013619},
\seqnum{A013620},
\seqnum{A013621},
\seqnum{A013622},
\seqnum{A013623},
\seqnum{A013624},
\seqnum{A013625},
\seqnum{A013626},
\seqnum{A013627},
\seqnum{A013628},
\seqnum{A022166},
\seqnum{A027465},
\seqnum{A027466},
\seqnum{A027467},
\seqnum{A028246},
\seqnum{A038207},
\seqnum{A038208},
\seqnum{A038210},
\seqnum{A038212},
\seqnum{A038214},
\seqnum{A038215},
\seqnum{A038216},
\seqnum{A038217},
\seqnum{A038218},
\seqnum{A038220},
\seqnum{A038221},
\seqnum{A038222},
\seqnum{A038224},
\seqnum{A038226},
\seqnum{A038227},
\seqnum{A038228},
\seqnum{A038229},
\seqnum{A038230},
\seqnum{A038231},
\seqnum{A038232},
\seqnum{A038233},
\seqnum{A038234},
\seqnum{A038236},
\seqnum{A038238},
\seqnum{A038239},
\seqnum{A038240},
\seqnum{A038241},
\seqnum{A038242},
\seqnum{A038243},
\seqnum{A038244},
\seqnum{A038245},
\seqnum{A038246},
\seqnum{A038247},
\seqnum{A038248},
\seqnum{A038250},
\seqnum{A038251},
\seqnum{A038252},
\seqnum{A038253},
\seqnum{A038254},
\seqnum{A038255},
\seqnum{A038256},
\seqnum{A038257},
\seqnum{A038258},
\seqnum{A038259},
\seqnum{A038260},
\seqnum{A038262},
\seqnum{A038263},
\seqnum{A038264},
\seqnum{A038265},
\seqnum{A038266},
\seqnum{A038267},
\seqnum{A038268},
\seqnum{A038269},
\seqnum{A038270},
\seqnum{A038271},
\seqnum{A038272},
\seqnum{A038273},
\seqnum{A038274},
\seqnum{A038275},
\seqnum{A038276},
\seqnum{A038277},
\seqnum{A038278},
\seqnum{A038279},
\seqnum{A038280},
\seqnum{A038281},
\seqnum{A038282},
\seqnum{A038283},
\seqnum{A038284},
\seqnum{A038285},
\seqnum{A038286},
\seqnum{A038287},
\seqnum{A038288},
\seqnum{A038289},
\seqnum{A038290},
\seqnum{A038291},
\seqnum{A038292},
\seqnum{A038293},
\seqnum{A038294},
\seqnum{A038295},
\seqnum{A038296},
\seqnum{A038297},
\seqnum{A038298},
\seqnum{A038299},
\seqnum{A038300},
\seqnum{A038301},
\seqnum{A038302},
\seqnum{A038303},
\seqnum{A038304},
\seqnum{A038305},
\seqnum{A038306},
\seqnum{A038307},
\seqnum{A038308},
\seqnum{A038309},
\seqnum{A038310},
\seqnum{A038311},
\seqnum{A038312},
\seqnum{A038313},
\seqnum{A038314},
\seqnum{A038315},
\seqnum{A038316},
\seqnum{A038317},
\seqnum{A038318},
\seqnum{A038319},
\seqnum{A038320},
\seqnum{A038321},
\seqnum{A038322},
\seqnum{A038323},
\seqnum{A038324},
\seqnum{A038325},
\seqnum{A038326},
\seqnum{A038327},
\seqnum{A038328},
\seqnum{A038329},
\seqnum{A038330},
\seqnum{A038331},
\seqnum{A038332},
\seqnum{A038333},
\seqnum{A038334},
\seqnum{A038335},
\seqnum{A038336},
\seqnum{A038337},
\seqnum{A038338},
\seqnum{A080416},
\seqnum{A090582},
\seqnum{A108084},
\seqnum{A113025},
\seqnum{A123187},
\seqnum{A126351},
\seqnum{A130850},
\seqnum{A143395},
\seqnum{A144084},
\seqnum{A147716},
\seqnum{A303901},
and \seqnum{A317498}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 6 2026;
revised versions received  January 7 2026; April 13 2026.
Published in {\it Journal of Integer Sequences}, May 3 2026.

\bigskip
\hrule
\bigskip

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


\end{document}