Enumeration of Certain k-Block Partitions of Barry

Bulat Khaidarov Grintek Ltd. Khuroson 1, Ulugbek 100214 Tashkent Uzbekistan

                   bulat.khaidarov@gmail.com

Abstract The OEIS sequence \underline{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.

1 Introduction

The sequence \underline{A080416} from the On-Line Encyclopedia of Integer Sequences (OEIS) was first proposed by Barry in 2003 [3]. 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^{th} block of the first partition and the (k − i + 1)^{th} block of the second partition is n + 1” [3].

In 2022, Lavrov [2, 3] noted that the results of a paper by Corcino et al. [1] imply the following recursive formula for this sequence:

s(β, n, k) = \begin{cases}1, & if n = k = 0; \\ 0, & if n = 0 XOR k = 0; \\ s(β + 1, n − 1, k − 1) + β · k · s(β, n − 1, k), & otherwise. \end{cases} (1)

The triangle given by s(0, n, k) looks as follows [2]:

\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} = 1 1 1 1 4 1 1 12 10 1 1 32 67 20 1.  (2)

We will start from the recursive formula (1) and derive two non-recursive formulas. The first of them involves matrix multiplication, while the second one is matrix-free.

2 Deriving a matrix-based formula

Formula (1) 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 + β, 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):

S_{a}(k, j) = \begin{cases}1, & if j = k = 0; \\ 0, & if j < 0 or k < 0; \\ S_{a}(k − 1, j) + k · (a − k) · S_{a}(k, j − 1), & otherwise. \end{cases}

Thus,

s(0, n, a) = S_{a}(a, n − a) = S_{a}(a − 1, n − a) + 0 = S_{a}(a − 1, n − a).

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), …, (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 ≠ 0). The corresponding values of S_{a}(k, j) for this diagonal can be accumulated in the vector

c_{0} = [1 0 ⋮ 0 0] .

The values of S_{a}(k, j) for the higher diagonal {(1, 1), (2, 0), …, (a − 1, −a + 3)} can be calculated by matrix-vector multiplication:

c_{1} = A · c_{0} = [a − 1  0  0  ⋯ 0  0  ⋯; 1 2(a − 2)  0  ⋯ 0  0  ⋯; 0  1  3(a − 3) ⋯ 0  0  ⋯; ⋮ ; 0  0  0  ⋯ 1 k(a − k) ⋯; ⋮] · [1 0 ⋮ 0 0] .  (3)

In formula (3), k is the column number of the (a − 1) × (a − 1) matrix A. The value of S_{a}(a − 1, n − a) is the last entry of the vector c_{n−2}:

c_{n−2} = A^{n−2} · c_{0}.

Thus, for all n ≥ a ≥ 2:

s(0, n, a) = [0 ⋯ 0 1] · [a − 1  0  0  ⋯ 0  0  ⋯; 1 2(a − 2)  0  ⋯ 0  0  ⋯; 0  1  3(a − 3) ⋯ 0  0  ⋯; ⋮ ; 0  0  0  ⋯ 1 k(a − k) ⋯; ⋮]^{n−2} · [1 0 ⋮ 0 0] .

(4)

Using formula (4), we evaluated the first entries of the sequence and listed them in Table 1.

n a 2 3  4  5  6  7  8  9  10 11
2  1
3  1 1
4  1 4  1
5  1 12  10  1
6  1 32  67  20  1
7  1 80  376  252  35  1
8  1 192 1909  2560  742  56  1
9  1 448 9094  22928  12346  1848  84  1
10 1 1024 41479 189120 177599 46912  4074 120 1
11 1 2304 183412 1472704 2318149 1013936 149644 8184 165 1

Table 1: Triangular array of the numbers s(0, n, a) up to n = 11.

In the OEIS [3], there is a list of values of the first 50 members of the sequence, and they are the same as given in Table 1.

3 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) × (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,

A = D + C_{1} = diag(a − 1, 2(a − 2), …, i(a − i), …) + C_{1},

where i is the row number.

The matrices C_{w} have the following property:

C_{w} = C_{1}^{w}.  (5)

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 (5)). 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:

\underbrace{D ⋯ D}_{t_{1}} ·C_{1} \underbrace{D ⋯ D}_{t_{2}} ·C_{1} ⋯ C_{1} \underbrace{D ⋯ D}_{t_{a−1}} = D^{t_{1}} · C_{1} · D^{t_{2}} · C_{1} ⋯ C_{1} · D^{t_{a−1}},  (6)

where ∑ t_{m} = n − a.

This leads to investigating a product of matrices of the form C_{1} · 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 w-shifted diagonal matrix, and let sdiag_{w}(d_{i}) denote it, where d_{i} is a formula for evaluating the element of the i^{th} column on the shifted diagonal.

With this notation,

sdiag_{p}(x_{i}) · 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} · D = sdiag_{1}(i(a − i)),
C_{1} · D^{t} = sdiag_{1}(i^{t}(a − i)^{t}).

Then (6) is equivalent to

D^{t_{1}} ∏_{m=2}^{a−1} sdiag_{1}(i^{t_{m}}(a − i)^{t_{m}})

that can be simplified to

sdiag_{a−2}(∏_{i=1}^{a−1} i^{t_{a−i}}(a − i)^{t_{a−i}}).  (7)

Let p_{i} = t_{a−i}. Then the (a − 1, 1) entry of matrix (7) is

∏_{i=1}^{a−1} i^{p_{i}}(a − i)^{p_{i}}.

The value of s(0, n, a) is a sum of such products for all possible p_{i} (p_{i} ≥ 0, while ∑_{i=1}^{a−1} p_{i} = n − a). Thus,

s(0, n, a) = ∑ ; ∑ p_{i}=n−a(∏_{i=1}^{a−1} i^{p_{i}}(a − i)^{p_{i}}).  (8)

Using formula (8), we get for a = 3 and 4:

s(0, n, 3) = (n − 2) · 2^{n−3},
s(0, n, 4) = 3^{n−4} ∑_{p_{2}=0}^{n−4}((\frac{4}{3})^{p_{2}} · (n − 3 − p_{2})).

4 Generalization of the approach

The derivation of formulas (4) and (8) 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:

S_{a}(x, y) = N(x) · S_{a}(x, y − 1) + E(x) · S_{a}(x − 1, y).

If we assume the offset S_{a}(0, 0) = b, then a matrix-based formula (using (a + 1) × (a + 1) matrices, because for the general case, our first diagonal starts at (0, 0) and ends at (a, −a)) is

S_{a}(a, j) = b [0 0 ⋯ 0 1] (sdiag_{0}(N(i − 1)) + sdiag_{1}(E(i)))^{a+j} [1 0 ⋮ 0 0] ,  (9)

while a matrix-free formula is

S_{a}(a, j) = b(∏_{i=1}^{a} E(i)) ∑ ; ∑_{i=1}^{a+1} p_{i}=j(∏_{i=1}^{a+1} N^{p_{i}}(i − 1)).  (10)

In our case (\underline{A080416}), j = n − a, E(i) = b = 1, N(i − 1) = (i − 1)(a + 1 − i).

Formulas (9) and (10) can be applied to sequences defined by counting North-East lattice paths with weights. Some examples of such sequences are given in Table 2.

b N(i)  E(i)  Description  Sequence

1 const const triangles of coefficients in expansion of (E + N · x)^{n}

\underline{A013609}–\underline{A013628}, \underline{A027465}–
\underline{A027467}, \underline{A038207}, \underline{A038208},
\underline{A038210}, \underline{A038212}, \underline{A038214}–
\underline{A038218}, \underline{A038220}–\underline{A038222},
\underline{A038224}, \underline{A038226}–\underline{A038234},
\underline{A038236}, \underline{A038238}–\underline{A038248},
\underline{A038250}–\underline{A038260}, \underline{A038262}–
\underline{A038338}, \underline{A123187}, \underline{A147716},
\underline{A303901}, \underline{A317498}

1 i 1 Stirling numbers of the second kind

\underline{A008277}

1 i + 2 1 a matrix product of the Stirling numbers of the second kind with the binomial coefficients

\underline{A126351}

1 i + 1 1 the reflected triangle of Stirling numbers of the second kind

\underline{A008278}

1 i + 1 i + 1  \left\{{n \atop n − k + 1}\right\}(n − k + 1)!  \underline{A090582}
1 i + 1  i  \left\{{n \atop k}\right\}(k − 1)!  \underline{A028246}, \underline{A130850}

1 2^{i} 1 the triangle of Gaussian binomial coefficients [n, k] for q = 2

\underline{A022166}
1 2^{i}  2^{i}  \underline{A108084}
1 1  j + i  \frac{n!}{(n − k)!}\binom{n}{k}  \underline{A144084}
1 1 a + j + i  \frac{(n + k)!}{(n − k)! k!}  \underline{A113025}
1 a + i  1  \underline{A143395}

Table 2: Sequences defined by counting North-East lattice paths with weights.

5 Acknowledgments

The author thanks the anonymous referee for careful reading and helpful suggestions.

References

[1] 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

   https://arxiv.org/abs/1302.4694.

[2] M. Lavrov, Finding a closed form for this sequence (\underline{A080416}), thread answer. Available

   at https://math.stackexchange.com/questions/4550888.

[3] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2026. Published electronically at https://oeis.org.

2020 Mathematics Subject Classification: Primary 11B83; Secondary 05A10. Keywords: shifted diagonal matrix, Stirling-like number, North-East lattice paths.

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

Received January 6 2026; revised versions received January 7 2026; April 13 2026. Published in Journal of Integer Sequences, May 3 2026.

Return to Journal of Integer Sequences home page.