On a One-Parameter Family of Riordan Arrays and the Weight Distribution of MDS

Codes

Paul Barry School of Science Waterford Institute of Technology Ireland

                         pbarry@wit.ie

Patrick Fitzpatrick Department of Mathematics University College Cork Ireland

                        fitzpat@ucc.ie

Abstract We use the formalism of the Riordan group to study a one-parameter family of lower-triangular matrices related to the weight distribution of maximum distance separable codes. We obtain factorization results for these matrices. We then derive alternative expressions for the weight distribution of MDS codes. We define related weight ratios and show that they satisfy a certain linear recurrence.

1 Introduction

In this note, we report on a one-parameter family of transformation matrices which can be related to the weight distribution of maximum distance separable (MDS) codes. Regarded as transformations on integer sequences, they are easy to describe both by formula (in relation to the general term of a sequence) and in terms of their action on the ordinary generating function of a sequence. To achieve this, we use the language of the Riordan group of infinite lower-triangular integer matrices. They are also linked to several other known transformations, most notably the binomial transformation.

2 Error-correcting codes

Maximum distance separable codes are a special case of error-correcting code. By errorcorrecting code, we shall mean a linear code over F_{q} = GF (q), that is, a vector subspace C of F_{q}^{n} for some n > 0. If C is a k-dimensional vector subspace of F_{q}^{n}, then the code is described as a q-ary [n, k]-code. The elements of C are called the codewords of the code. The weight w(c) of a codeword c is the number of non-zero elements in the vector representation of c. An [n, k] code with minimum weight d is called an [n, k, d] code. A code is called a maximum separable code if the minimum weight of a non-zero codeword in the code is n − k + 1, that is, d = n − k + 1. The Reed-Solomon family of linear codes is a well-known family of MDS codes.

An important characteristic of a code is its weight distribution. This is defined to be the set of coefficients A_{0}, A_{1}, …, A_{n} where A_{i} is the number of codewords of weight i in C. The weight distribution of a code plays a significant role in calculating probabilities of error. Except for trivial or ‘small’ codes, the determination of the weight distribution is normally not easy. The MacWilliams identity for general linear codes is often used to simplify this task. The special case of MDS codes proves to be tractable. Using the MacWilliams identity [2] or otherwise [3, 9], we obtain the following equivalent results.

Proposition 1. The number of codewords of weight i, where n − k + 1 ≤ i ≤ n, in a q-ary [n, k] MDS code is given by

A_{i} = \binom{n}{i}(q − 1) ∑_{j=0}^{i−d_{min}}(−1)^{j}\binom{i − 1}{j}q^{i−d_{min}−j}  (1)

= \binom{n}{i} ∑_{j=0}(−1)^{j}\binom{i}{j}(q^{i−d_{min}+1−j} − 1)  (2)

= \binom{n}{i} ∑_{j=d_{min}}^{i}(−1)^{i−j}\binom{i}{j}(q^{j−d_{min}+1} − 1)  (3)

where d_{min} = n − k + 1.

We note that the last expression can be written as

A_{i} = \binom{n}{i} ∑_{j=0}^{i−d_{min}}(−1)^{i−d_{min}−j}\binom{i}{j + d_{min}}(q^{j+1} − 1)  (4)

by a simple change of variable.

We have A_{0} = 1, and A_{i} = 0 for 1 ≤ i ≤ n − k. The term \binom{n}{i} is a scaling term, which also ensures that A_{i} = 0 for i > n. In the sequel, we shall study a one-parameter family of Riordan arrays associated to the equivalent summation expressions above.

3 Transformations on integer sequences and the Riordan Group

We shall introduce transformations that operate on integer sequences. An example of such a transformation that is widely used in the study of such sequences is the so-called Binomial transform [10], which associates to the sequence with general term a_{n} the sequence with general term b_{n} where

b_{n} = ∑_{j=0}^{n} \binom{n}{j}a_{j}.  (5)

If we consider the sequence with general term a_{n} to be the column vector a = (a_{0}, a_{1}, …)′ then we obtain the binomial transform of the sequence by multiplying this (infinite) vector by the lower-triangle matrix B whose (i, j)-th element is equal to (_{j}^{i}):

B = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 1 & 2 & 1 & 0 & 0 & 0 & … \\ 1 & 3 & 3 & 1 & 0 & 0 & … \\ 1 & 4 & 6 & 4 & 1 & 0 & … \\ 1 & 5 & 10 & 10 & 5 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

This transformation is invertible, with

a_{n} = ∑_{j=0}^{n} \binom{n}{j}(−1)^{n−j}b_{j}.  (6)

We note that B corresponds to Pascal’s triangle. Its row sums are 2^{n}, while its diagonal sums are the Fibonacci numbers F (n + 1). If B^{k} denotes the k−th power of B, then the n−th term of B^{k}a where a = \{a_{j}\} is given by ∑_{j=0}^{n} k^{n−j}\binom{n}{j}a_{j}.

If A(x) is the ordinary generating function of the sequence a_{n}, then the generating function of the transformed sequence b_{n} is \frac{1}{1−x}A(\frac{x}{1−x}). The binomial transform is an element of the Riordan group, which can be defined as follows.

The Riordan group [1, 4, 8], is a set of infinite lower-triangular integer matrices, where each matrix is defined by a pair of generating functions g(x) = 1 + g_{1}x + g_{2}x^{2} + … and f(x) = f_{1}x + f_{2}x^{2} + … where f_{1} ≠ 0 [8]. We sometimes write f(x) = xh(x) where h(0) ≠ 0. The associated matrix is the matrix whose i-th column is generated by g(x)f(x)^{i} (the first column being indexed by 0). The matrix corresponding to the pair f, g is denoted by (g, f) or R(g, f). The group law is then given by

(g, f) ∗ (h, l) = (g(h ∘ f), l ∘ f).  (7)

The identity for this law is I = (1, x) and the inverse of (g, f) is (g, f)^{−1} = (1/(g ∘ f̄), f̄) where f̄ is the compositional inverse of f.

To each Riordan array as defined above is associated an integer sequence A = {a_{i}} with a_{0} ≠ 0 such that every element d_{n+1,k+1} of the array (not lying in column 0 or row 0) can be expressed as a linear combination with coefficients in A of the elements in the preceding row, starting from the preceding column:

d_{n+1,k+1} = a_{0}d_{n,k} + a_{1}d_{n,k+1} + a_{2}d_{n,k+2} + ⋯

A = {a_{i}} is called the A-sequence of the array, and may be calculated according to

A(x) = [h(t)|t = xh(t)^{−1}].

A Riordan array of the form (g(x), x), where g(x) is the generating function of the sequence a_{n}, is called the sequence array of the sequence a_{n}. Its general term is a_{n−k}.

If M is the matrix (g, f), and a = (a_{0}, a_{1}, …)′ is an integer sequence with ordinary generating function A (x), then the sequence Ma has ordinary generating function g(x)A(f(x)).

Example 2. The binomial matrix B is the element (\frac{1}{1−x}, \frac{x}{1−x}) of the Riordan group. It has general element \binom{n}{k}. More generally, B^{m} is the element (\frac{1}{1−mx}, \frac{x}{1−mx}) of the Riordan group, with general term \binom{n}{k}m^{n−k}. It is easy to show that the inverse B^{−m} of B^{m} is given by (\frac{1}{1+mx}, \frac{x}{1+mx}).

The row sums of the matrix (g, f) have generating function g(x)/(1 − f(x)) while the diagonal sums of (g, f) have generating function g(x)/(1 − xf(x)).

Many interesting examples of Riordan arrays can be found in Neil Sloane’s On-Line Encyclopedia of Integer Sequences, [5, 6]. Sequences are frequently referred to by their OEIS number. For instance, the matrix B is \underline{A007318}.

4 Introducing the one-parameter family of ‘MDS’ transforms

In this section, we shall frequently use n and k to address elements of infinite arrays. Thus the n, k-th element of an infinite array T refers to the element in the n-th row and the k-th column. Row and column indices will start at 0. This customary use of n, k, should not cause any confusion with the use of n, k above to describe [n, k] codes.

We define T_{m} to be the transformation represented by the matrix

T_{m} = (\frac{1 + x}{1 − mx}, \frac{x}{1 + x})

where m ∈ N. For instance, we have

T_{1} = (\frac{1 + x}{1 − x}, \frac{x}{1 + x}) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 0 & 0 & 0 & … \\ 2 & 1 & 1 & 0 & 0 & 0 & … \\ 2 & 1 & 0 & 1 & 0 & 0 & … \\ 2 & 1 & 1 & −1 & 1 & 0 & … \\ 2 & 1 & 0 & 2 & −2 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

This triangle is \underline{A113310}, which has row sums 1, 3, 4, 4, 4, … \underline{A113311} with generating function \frac{(1+x)^{2}}{1−x}. In general, the row sums of T_{m} have generating function \frac{(1+x)^{2}}{1−mx}. Note also that

T_{0} = (1 + x, \frac{x}{1 + x}) = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ 1 & 1 & 0 & 0 & 0 & 0 & … \\ 0 & 0 & 1 & 0 & 0 & 0 & … \\ 0 & 0 & −1 & 1 & 0 & 0 & … \\ 0 & 0 & 1 & −2 & 1 & 0 & … \\ 0 & 0 & −1 & 3 & −3 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

with general term \binom{n−2}{n−k}(−1)^{n−k}. We can calculate the A-sequence for T_{m} as follows.

A(x) = [\frac{1}{1 + t}|t = xh(t)^{−1}]
= [\frac{1}{1 + t}|t = x(1 + t)]
= [\frac{1}{1 + t}|t = \frac{x}{1 − x}]
= \frac{1}{1 + \frac{x}{1−x}} = 1 − x.

Thus every element in T_{m} is given by the difference of the two elements above it, i.e.:

T_{m}(n + 1, k + 1) = T_{m}(n, k) − T_{m}(n, k + 1).

Proposition 3. For each m, T_{m} is invertible with

T_{m}^{−1} = (1 − (m + 1)x, \frac{x}{1 − x}) .

Proof. Let T_{m}^{−1} = (g^{∗}, f̄). This exists since T_{m} is an element of the Riordan group. Then

(g^{∗}, f̄) (\frac{1 + x}{1 − mx}, \frac{x}{1 + x}) = (1, x).

Hence

\frac{f̄}{1 + f̄} = x ⇒ f̄ = \frac{x}{1 − x}

and

g^{∗} = \frac{1}{g ∘ f̄} ⇒ g^{∗} = \frac{1 − mf̄}{1 + f̄} = 1 − (m + 1)x.

Corollary 4. The general term of T_{m}^{−1} is given by

T_{m}^{−1}(n, k) = \binom{n − 1}{n − k} − (m + 1)\binom{n − 2}{n − k − 1}.

Proof. We have

T_{m}^{−1}(n, k) = [x^{n}](1 − (m + 1)x) (\frac{x}{1 − x})^{k}
= [x^{n−k}]\frac{1}{(1 − x)^{k}} − (m + 1)[x^{n−k−1}]\frac{1}{(1 − x)^{k}}
= \binom{−k}{n − k}(−1)^{n−k} − (m + 1)\binom{−k}{n − k − 1}(−1)^{n−k−1}
= \binom{n − 1}{n − k} − (m + 1)\binom{n − 2}{n − k − 1}.

Our main goal in this section is to find expressions for the general term T_{m}(n, k) of T_{m}. To this end, we exhibit certain useful factorizations of T_{m}.

Proposition 5. We have the following factorizations of the Riordan array T_{m}:

T_{m} = (\frac{1 + x}{1 − mx}, \frac{x}{1 + x})
= (1 + x, x) ∗ (\frac{1}{1 − mx}, \frac{x}{1 + x})
= (1, \frac{1}{1 + x}) ∗ (\frac{x}{1 − (m + 1)x}, x)
= (\frac{1}{1 − mx}, x) ∗ (1 + x, \frac{x}{1 + x})
= (\frac{1}{1 + x}, \frac{x}{1 + x}) ∗ (\frac{1}{1 − x} · \frac{1}{1 − (m + 1)x}, x) .

Proof. Each of the assertions is a simple consequence of the product rule (equation (7)) for Riordan arrays. For instance,

(1, \frac{x}{1 + x}) ∗ (\frac{1}{1 − (m + 1)x}, x) = (1 · \frac{1}{1 − (m + 1)\frac{x}{1+x}} , \frac{x}{1 + x})

= (\frac{1 + x}{1 + x − (m + 1)x}, \frac{x}{1 + x})
= (\frac{1 + x}{1 − mx}, \frac{x}{1 + x}) = T_{m}.

The other assertions follow in a similar manner.

The last assertion, which can be written

T_{m} = B^{−1} ∗ (\frac{1}{1 − x} · \frac{1}{1 − (m + 1)x}, x) ,

is a consequence of the fact that the product BT_{m} takes on a simple form. We have

BT_{m} = (\frac{1}{1 − x}, \frac{x}{1 − x}) ∗ (\frac{1 + x}{1 − mx}, \frac{x}{1 + x})
= (\frac{1}{1 − x} · \frac{1 + \frac{x}{1−x}}{1 − m\frac{x}{1−x}} , \frac{\frac{x}{1−x}}{1 + \frac{x}{1−x}} )
= (\frac{1}{1 − x} · \frac{1}{1 − (m + 1)x}, x) .

We can interpret this as the sequence array for the partial sums of the sequence (m + 1)^{n}, that is, the sequence array of \frac{(m+1)^{n+1}−1}{(m+1)−1}. Thus T_{m} is obtained by applying B^{−1} to this sequence array. We note that the inverse matrix (BT_{m})^{−1} takes the special form

((1 − x)(1 − (m + 1)x), x) = (1 − (m + 2)x + (m + 1)x^{2}, x).

Thus this matrix is tri-diagonal, of the form

(BT_{m})^{−1} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & … \\ −(m + 2) & 1 & 0 & 0 & 0 & 0 & … \\ m + 1 & −(m + 2) & 1 & 0 & 0 & 0 & … \\ 0 & m + 1 & −(m + 2) & 1 & 0 & 0 & … \\ 0 & 0 & m + 1 & −(m + 2) & 1 & 0 & … \\ 0 & 0 & 0 & m + 1 & −(m + 2) & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

Corollary 6. The general term of the array T_{m} is

T_{m}(n, k) = ∑_{j=k}^{n}(−1)^{n−j}\binom{n}{j}((m + 1)^{j−k+1} − 1)/m, m ≠ 0.

Proof. By the last proposition, we have

T_{m} = B^{−1} ∗ (\frac{1}{1 − x} · \frac{1}{1 − (m + 1)x}, x) .

The general term of B^{−1} = (\frac{1}{1+x}, \frac{x}{1+x}) is (−1)^{n−k}\binom{n}{k} while that of the second Riordan array is \frac{(m+1)^{n−k+1}−1}{(m+1)−1}. The result follows from the product formula for matrices. Corollary 7.

T_{m−1}(n, k) = ∑_{j=k}^{n}(−1)^{n−j}\binom{n}{j}\frac{m^{j−k+1} − 1}{m − 1} = ∑_{j=0}^{n−k}(−1)^{n−k−j}\binom{n}{j + k}\frac{m^{j+1} − 1}{m − 1}.

Equivalently,

(m − 1)\binom{n}{k}T_{m−1}(n, k) = \binom{n}{k} ∑_{j=0}^{n−k}(−1)^{n−k−j}\binom{n}{j + k}(m^{j+1} − 1).

This last result makes evident the link between the Riordan array T_{m−1} and the weight distribution of MDS codes. Thus, based on equation (3), we have

T_{q−1}(i, d_{min}) = ∑_{j=d_{min}}^{i}(−1)^{i−j}\binom{i}{j}\frac{q^{j−d_{min}+1} − 1}{q − 1}.

Hence

(q − 1)\binom{n}{i}T_{q−1}(i, d_{min}) = \binom{n}{i} ∑_{j=d_{min}}^{i}(−1)^{i−j}\binom{i}{j}(q^{j−d_{min}+1} − 1)
= A_{i}.

and thus

A_{i} = (q − 1)\binom{n}{i}T_{q−1}(i, d_{min}).  (8)

We now find a number of alternative expressions for the general term of T_{m} which will give us a choice of expressions for the weight distribution of an MDS code.

Proposition 8.

T_{m}(n, k) = ∑_{j=0}^{n−k}(−1)^{j}\binom{j + k − 2}{j}m^{n−k−j}

= ∑_{j=0}^{n−k}(−1)^{n−k−j}\binom{n − j − 2}{n − j − k}m^{j}

= ∑_{j=k}^{n} \binom{n − 1}{n − j}(−1)^{n−j}(m + 1)^{j−k}.

Proof. The first two equations result from

T_{m}(n, k) = [x^{n}]\frac{1 + x}{1 − mx} (\frac{x}{1 + x})^{k}
= [x^{n−k}](1 − mx)^{−1}(1 + x)^{−(k−1)}
= [x^{n−k}] ∑_{i≥0} m^{i}x^{i} ∑_{j≥0} \binom{−(k − 1)}{j}x^{j}

= [x^{n−k}] ∑_{i≥0} ∑_{j≥0} \binom{k + j − 2}{j}(−1)^{j}m^{i}x^{i+j}.

An alternative proof for the second identity if furnished by using the convolution rule (rule 4KE - conv in [7]) to get:

[x^{n}]\frac{1 + x}{1 − mx} · \frac{x^{k}}{(1 + x)^{k}} = [x^{n−k}]\frac{1}{1 − mx} · \frac{1}{(1 + x)^{k−1}}

= ∑_{j=0}^{n−k} \binom{−k + 1}{n − k − j}m^{j}

= ∑_{j=0}^{n−k} \binom{n − j − 2}{n − k − j}(−1)^{n−k−j}m^{j},

while the first identity is obtained when we apply the convolution rule in the symmetric way, i.e., with j ↦ n − k − j. The third equation is a consequence of the factorization

T_{m} = (1, \frac{1}{1 + x}) ∗ (\frac{1}{1 − (m + 1)x}, x)

since (1, \frac{1}{1+x}) has general term \binom{n−1}{n−k}(−1)^{n−k}.

Thus we have, for instance,

(m − 1)\binom{n}{k}T_{m−1}(n, k) = (m − 1)\binom{n}{k} ∑_{j=k}^{n} \binom{n − 1}{n − j}(−1)^{n−j}m^{j−k}.

Using the standard notation for weight distributions, we obtain, from equation (8),

A_{i} = (q − 1)\binom{n}{i}T_{q−1}(i, d_{min})

= (q − 1)\binom{n}{i} ∑_{j=d_{min}}^{i} \binom{i − 1}{i − j}(−1)^{i−j}q^{j−d_{min}}.

5 Applications to MDS codes

We begin this section with an example.

Example 9. The dual of the [7, 2, 6] Reed Solomon code over GF (2^{3}) is an MDS [7, 5, 3] code, also over GF (2^{3}). Thus the code parameters of interest to us are q = 8, n = 7, k = 5 and d_{min} = n − k + 1 = 3. Let D = diag(\binom{7}{0}, \binom{7}{1}, …, \binom{7}{7}, 0, 0, …) denote the infinite square matrix all of whose entries are zero except for those indicated. We form the matrix product (q − 1)DT_{q−1}, with q = 8, to get

7diag \{\binom{7}{j}\} ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 8 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 56 & 7 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 392 & 49 & 6 & 1 & 0 & 0 & 0 & 0 & 0 & … \\ 2744 & 343 & 43 & 5 & 1 & 0 & 0 & 0 & 0 & … \\ 19208 & 2401 & 300 & 38 & 4 & 1 & 0 & 0 & 0 & … \\ 134456 & 16807 & 2101 & 262 & 34 & 3 & 1 & 0 & 0 & … \\ 941192 & 117649 & 14706 & 1839 & 228 & 31 & 2 & 1 & 0 & … \\ 6588344 & 823543 & 102943 & 12867 & 1611 & 197 & 29 & 1 & 1 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

= ( \begin{matrix}7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 392 & 49 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 8232 & 1029 & 147 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ 96040 & 12005 & 1470 & 245 & 0 & 0 & 0 & 0 & 0 & … \\ 672280 & 84035 & 10535 & 1225 & 245 & 0 & 0 & 0 & 0 & … \\ 2823576 & 352947 & 44100 & 5586 & 588 & 147 & 0 & 0 & 0 & … \\ 6588344 & 823543 & 102949 & 12838 & 1666 & 147 & 49 & 0 & 0 & … \\ 6588344 & 823543 & 102942 & 12873 & 1596 & 217 & 14 & 7 & 0 & … \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix} )

Column 3 (starting from column 0) of this matrix then yields the weight distribution of the [7, 5, 3] code. That is, we obtain the vector (1, 0, 0, 245, 1225, 5586, 12838, 12873), where we have made the adjustment A_{0} = 1. Thus we obtain

\begin{matrix}A_{0} & A_{1} & A_{2} & A_{3} & A_{4} & A_{5} & A_{6} & A_{7} \\ 1 & 0 & 0 & 245 & 1225 & 5586 & 12838 & 12873 \end{matrix}

We moreover notice that the numbers (0, 0, 0, 1, 5, 38, 262, 1839), which correspond to the ratios A_{i}/((q−1)\binom{n}{i}), are elements of the sequence with ordinary generating function \frac{1+x}{1−7x}(\frac{x}{1+x})^{3} = \frac{x^{3}(1+x)}{1−4x−18x^{2}−20x^{3}−x^{4}} . Hence they satisfy the recurrence

a_{n} = 4a_{n−1} + 18a_{n−2} + 20a_{n−3} + 7a_{n−4}.

This last result leads us to define the weight ratios of a q-ary [n, k, d] MDS code to be the ratios A_{i}/((q − 1)\binom{n}{i}).

We are now in a position to summarize the results of this paper.

Theorem 10. Let C be a q-ary [n, k, d] MDS code. The weight distribution of C, adjusted for A_{0}=1, is obtained from the d-th column of the matrix

(q − 1)Diag \{\binom{n}{j}\} (\frac{1 + x}{1 − (q − 1)x}, \frac{x}{1 + x}) .

Moreover, the weight ratios of the code satisfy a recurrence defined by the ordinary generating function \frac{1+x}{1−(q−1)x}(\frac{x}{1+x})^{d}.

Proof. Inspection of the expressions for the general term T_{q−1} and the formulas for A_{i} yield the first statement. The second statement is a standard property of the columns of a Riordan array.

Thus the weight ratios satisfy the recurrence

a_{n} = ((q − 1)\binom{d}{0} − \binom{d}{1})a_{n−1} + ((q − 1)\binom{d}{1} − \binom{d}{2})a_{n−2} + ⋯ + ((q − 1)\binom{d}{d−1} − \binom{d}{d})a_{n−d} + (q − 1)a_{n−d−1}.

Letting R_{0} = 0, and R_{i} = A_{i}/((q − 1)\binom{n}{i}) for i > 0, we therefore have

R_{l} = ∑_{j=0}^{d}((q − 1)\binom{d}{j} − \binom{d}{j + 1})R_{l−j−1}

where d = d_{min} = n − k + 1. In terms of the A_{i}, this therefore gives us

A_{i} = \binom{n}{i} ∑_{j=0}^{d} \frac{(q − 1)\binom{d}{j} − \binom{d}{j+1}}{\binom{n}{i−j−1}}A_{i−j−1}.

For instance, we have

12873 = \binom{7}{7} [\frac{4}{7} · 12838 + \frac{18}{21} · 5586 + \frac{20}{35} · 1225 + \frac{7}{35} · 245] .

and

12838 = \binom{7}{6} [\frac{4}{21} · 5586 + \frac{18}{35} · 1225 + \frac{20}{35} · 245 + \frac{7}{21} · 0] .

6 Acknowledgements

The author would like to thank an anonymous reviewer for their careful reading of this manuscript and for their constructive remarks.

References

[1] D. Merlini, D. G. Rogers, R. Sprugnoli, and M.C. Verri, On some alternative characterizations of Riordan arrays, Canadian J. Math., 49 (2) (1997), 301–320.

[2] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 2003.

[3] W. W. Peterson, E. J. Weldon, Error-Correcting Codes, 2nd ed., MIT Press, Cambridge, 1984.

[4] L. W. Shapiro, S. Getu, W-J. Woan and L.C. Woodson, The Riordan group, Discr. Appl. Math. 34 (1991), 229–239.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically

   at http://www.research.att.com/∼njas/sequences/, 2007.

[6] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, Notices Amer. Math. Soc., 50 (2003), 912–915.

[7] R. Sprugnoli, Riordan array proofs of identities in Gould’s book,, available at

   http://www.dsi.unifi.it/∼resp/GouldBK.pdf, 2007.

[8] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[9] J. H. van Lint, R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001.

[10] E. W. Weisstein, Binomial transform, published electronically at

   http://mathworld.wolfram.com/BinomialTransform.html/, 2007.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 94B05, 11B37, 11B65.

(Concerned with sequences \underline{A007318}, \underline{A113310}, and \underline{A113311}.)

Received June 21 2007; revised version received November 16 2007. Published in Journal of Integer Sequences, November 20 2007.

Return to Journal of Integer Sequences home page.