\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{example}[theorem]{Example}

\begin{center}
\vskip 1cm{\LARGE\bf On a One-Parameter Family of Riordan  \\
\vskip .1in
Arrays and the Weight Distribution of MDS \\
\vskip .15in Codes} \vskip 1cm \large
Paul Barry\\
School of Science\\
Waterford Institute of Technology\\
Ireland\\
\href{mailto:pbarry@wit.ie}{\tt pbarry@wit.ie} \\
\ \\ 
Patrick Fitzpatrick\\
Department of Mathematics\\
University College Cork\\
Ireland \\
\href{mailto:fitzpat@ucc.ie}{\tt fitzpat@ucc.ie} \\
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}

\section{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.

\section{Error-correcting codes}
Maximum distance separable codes are a special case of error-correcting code.
By \emph{error-correcting code}, we shall mean a \emph{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 \emph{$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 \emph{weight
distribution}. This is defined to be the set of coefficients
${A_0,A_1,\ldots,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 \cite{MS} or otherwise \cite{PW,vanLint},
we obtain the following
equivalent results.
\begin{proposition} The number of codewords of weight $i$, where $n-k+1\leq i \leq n$, in a
$q$-ary $[n,k]$ MDS code is given by
\begin{eqnarray}A_i&=&\binom{n}{i}(q-1)\sum_{j=0}^{i-d_{min}}(-1)^j\binom{i-1}{j}q^{i-d_{min}-j}\\
&=&\binom{n}{i}\sum_{j=0}(-1)^j\binom{i}{j}(q^{i-d_{min}+1-j}-1)\\
&=&\label{A_i_eq_1}\binom{n}{i}\sum_{j=d_{min}}^i(-1)^{i-j}\binom{i}{j}(q^{j-d_{min}+1}-1)\end{eqnarray}
where $d_{min}=n-k+1$.
\end{proposition}
We note that the last expression can be written as
\begin{equation}\label{A_i_eq_2}A_i=\binom{n}{i}\sum_{j=0}^{i-d_{min}}(-1)^{i-d_{min}-j}\binom{i}{j+d_{min}}(q^{j+1}-1)\end{equation}
by a simple change of variable.

We have $A_0=1$, and $A_i=0$ for $1 \leq i \leq 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.

\section{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 \textit{Binomial transform} \cite{Bin},
which associates to the sequence with general term $a_n$ the
sequence with general term $b_n$ where
\begin{equation}b_n=\sum_{j=0}^n{{n}\choose{j}}a_j.\end{equation} If we consider the sequence with general term $a_n$ to be the column vector
$\mathbf{a}=(a_0,a_1,\ldots)'$
 then we obtain the binomial transform of the sequence by multiplying this (infinite) vector by the lower-triangle matrix $\mathbf{B}$ whose $(i,j)$-th element is equal to
$(_{j}^{i})$:
\begin{displaymath}\mathbf{B}=\left(\begin{array}{ccccccc} 1 & 0 & 0
& 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 1 & 2 & 1
& 0 & 0 & 0 & \ldots \\ 1 & 3 & 3 & 1 & 0 & 0 & \ldots \\ 1 & 4 &
6 & 4 & 1 & 0 & \ldots
\\1 & 5 & 10 & 10 & 5 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} This
transformation is invertible, with
\begin{equation}a_n=\sum_{j=0}^n
{{n}\choose{j}}(-1)^{n-j}b_j.\end{equation} We note that
$\mathbf{B}$ corresponds to Pascal's triangle. Its row sums are
$2^n$, while its diagonal sums are the Fibonacci numbers $F(n+1)$.
If $\mathbf{B}^k$ denotes the $k-$th power of $\mathbf{B}$, then the
$n-$th term of $\mathbf{B}^k\mathbf{a}$ where $\mathbf{a}=\{a_j\}$
is given by $\sum_{j=0}^n k^{n-j}{{n}\choose{j}}a_j$.

If $\cal{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}\cal{A}$$(\frac{x}{1-x})$. The binomial transform is an
element of the Riordan group, which can be defined as follows.

The \emph{Riordan group} \cite{Alter,SGWW,Spru}, is a set of
infinite lower-triangular integer matrices, where each matrix is
defined by a pair of generating functions
$g(x)=1+g_1x+g_2x^2+\ldots$ and $f(x)=f_1x+f_2x^2+\ldots$ where
$f_1\ne 0$ \cite{Spru}. We sometimes write $f(x)=xh(x)$ where $h(0)\ne 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 $\cal{R}$$(g,f)$. The group law is then given
by
\begin{equation} \label{product} (g, f)*(h, l)=(g(h\circ f), l\circ
f).\end{equation} The identity for this law is $I=(1,x)$ and the
inverse of $(g, f)$ is $(g, f)^{-1}=(1/(g\circ \bar{f}), \bar{f})$
where $\bar{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\ne 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_0d_{n,k}+a_1 d_{n,k+1}+a_2d_{n,k+2}+\cdots$$
$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
\emph{sequence array} of the sequence $a_n$. Its general term is
$a_{n-k}$.

If $\mathbf{M}$ is the matrix $(g,f)$, and
$\mathbf{a}=(a_0,a_1,\ldots)'$ is an integer sequence with ordinary
generating function $\cal{A}$ $(x)$, then the sequence
$\mathbf{M}\mathbf{a}$ has ordinary generating function
$g(x)$$\cal{A}$$(f(x))$.

\begin{example} The binomial matrix $\mathbf{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, $\mathbf{B}^m$ is the
element $(\frac{1}{1-m x},\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 $\mathbf{B}^{-m}$ of $\mathbf{B}^m$ is given by
$(\frac{1}{1+mx},\frac{x}{1+mx})$.
\end{example}

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, \cite{SL1,SL2}. Sequences are frequently referred to by their
OEIS number. For instance, the matrix $\mathbf{B}$ is \seqnum{A007318}.

\section{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 $\mathbf{T}_m$ to be the transformation represented by the
matrix
\begin{displaymath}\mathbf{T}_m=\left(\frac{1+x}{1-mx},\frac{x}{1+x}\right)\end{displaymath} where $m\in\mathbf{N}$.
For instance, we have
\begin{displaymath}\mathbf{T}_1=\left(\frac{1+x}{1-x},\frac{x}{1+x}\right)=\left(\begin{array}{ccccccc} 1 & 0 & 0
& 0 & 0 & 0 & \ldots \\2 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 2 & 1 & 1 &
0 & 0 & 0 & \ldots \\ 2 & 1 & 0 & 1 & 0 & 0 & \ldots \\ 2 & 1 & 1 &
-1 & 1 & 0 & \ldots
\\2 & 1 & 0 & 2 & -2 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} This triangle
is \seqnum{A113310}, which has row sums $1,3,4,4,4,\ldots$ \seqnum{A113311} with
generating function $\frac{(1+x)^2}{1-x}$.
In general, the row sums of $\mathbf{T}_m$ have generating function
$\frac{(1+x)^2}{1-mx}$.  Note also that
\begin{displaymath}\mathbf{T}_0=\left(1+x,\frac{x}{1+x}\right)=\left(\begin{array}{ccccccc} 1 & 0 & 0
& 0 & 0 & 0 & \ldots \\1 & 1 & 0 & 0 & 0 & 0 & \ldots \\ 0 & 0 & 1 &
0 & 0 & 0 & \ldots \\ 0 & 0 & -1 & 1 & 0 & 0 & \ldots \\ 0 & 0 & 1&
-2 & 1 & 0 & \ldots
\\0 & 0 & -1 & 3 & -3 & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath} with general
term $\binom{n-2}{n-k}(-1)^{n-k}$.
We can calculate the $A$-sequence for $\mathbf{T}_m$ as follows.
\begin{eqnarray*}
A(x)&=&\left[\frac{1}{1+t}|t=xh(t)^{-1}\right]\\
&=&\left[\frac{1}{1+t}|t=x(1+t)\right]\\
&=&\left[\frac{1}{1+t}|t=\frac{x}{1-x}\right]\\
&=&\frac{1}{1+\frac{x}{1-x}}=1-x.\end{eqnarray*}
Thus every element in $\mathbf{T}_m$ is given by the difference of the two elements above it, i.e.:
$$\mathbf{T}_m(n+1,k+1)=\mathbf{T}_m(n,k)-\mathbf{T}_m(n,k+1).$$
\begin{proposition} For each $m$, $\mathbf{T}_m$ is invertible with
$$\mathbf{T}_m^{-1}=\left(1-(m+1)x, \frac{x}{1-x}\right).$$
\end{proposition}
\begin{proof} Let $\mathbf{T}_m^{-1}=(g^*,\bar{f})$. This exists since $\mathbf{T}_m$
is an element of the Riordan group. Then
$$(g^*,\bar{f})\left(\frac{1+x}{1-mx},\frac{x}{1+x}\right)=(1,x).$$
Hence
$$\frac{\bar{f}}{1+\bar{f}}=x \Rightarrow \bar{f}=\frac{x}{1-x}$$
and
$$g^*=\frac{1}{g\circ\bar{f}}\Rightarrow
g^*=\frac{1-m\bar{f}}{1+\bar{f}}=1-(m+1)x.$$
\end{proof}
\begin{corollary} The general term of $\mathbf{T}_m^{-1}$ is given by
$$ \mathbf{T}_m^{-1}(n,k)=\binom{n-1}{n-k}-(m+1)\binom{n-2}{n-k-1}.$$
\end{corollary}
\begin{proof}
We have \begin{eqnarray*}
\mathbf{T}_m^{-1}(n,k)&=&[x^n](1-(m+1)x)\left(\frac{x}{1-x}\right)^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}.\end{eqnarray*}\end{proof}

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

\begin{proposition} We have the following factorizations of the Riordan array $\mathbf{T}_m$:
\begin{eqnarray*}\mathbf{T}_m&=&\left(\frac{1+x}{1-mx},\frac{x}{1+x}\right)\\
&=&(1+x,x)*\left(\frac{1}{1-mx},\frac{x}{1+x}\right)\\
&=&\left(1,\frac{1}{1+x}\right)*\left(\frac{x}{1-(m+1)x},x\right)\\
&=&\left(\frac{1}{1-mx},x\right)*\left(1+x,\frac{x}{1+x}\right)\\
&=&\left(\frac{1}{1+x},\frac{x}{1+x}\right)*\left(\frac{1}{1-x}\cdot\frac{1}{1-(m+1)x},x\right).\end{eqnarray*}\end{proposition}
\begin{proof} Each of the assertions is a simple consequence of the product rule (equation (\ref{product})) for Riordan arrays.
For instance,
\begin{eqnarray*}\left(1,\frac{x}{1+x}\right)*\left(\frac{1}{1-(m+1)x},x\right)&=&\left(1\cdot\frac{1}{1-(m+1)\frac{x}{1+x}},\frac{x}{1+x}\right)\\
&=&\left(\frac{1+x}{1+x-(m+1)x},\frac{x}{1+x}\right)\\
&=&\left(\frac{1+x}{1-mx},\frac{x}{1+x}\right)=\mathbf{T}_m.\end{eqnarray*}
The other assertions follow in a similar manner.\end{proof}
The last assertion, which can be written
$$\mathbf{T}_m=\mathbf{B}^{-1}*\left(\frac{1}{1-x}\cdot\frac{1}{1-(m+1)x},x\right),$$ is a consequence of the fact that the product $\mathbf{B}\mathbf{T}_m$ takes
on a simple form. We have
\begin{eqnarray*}\mathbf{B}\mathbf{T}_m&=&\left(\frac{1}{1-x},\frac{x}{1-x}\right)*\left(\frac{1+x}{1-m x},\frac{x}{1+x}\right)\\
&=&\left(\frac{1}{1-x}\cdot\frac{1+\frac{x}{1-x}}{1-m\frac{x}{1-x}},\frac{\frac{x}{1-x}}{1+\frac{x}{1-x}}\right)\\
&=&\left(\frac{1}{1-x}\cdot\frac{1}{1-(m+1)x},x\right).\end{eqnarray*}
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 $\mathbf{T}_m$ is obtained by
applying $\mathbf{B}^{-1}$ to this sequence array. We note that the
inverse matrix $(\mathbf{B}\mathbf{T}_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
\begin{displaymath}
(\mathbf{B}\mathbf{T}_m)^{-1}=\left(\begin{array}{ccccccc} 1 & 0 & 0
& 0 & 0 & 0 & \ldots \\-(m+2) & 1 & 0 & 0 & 0 & 0 & \ldots \\ m+1 &
-(m+2) & 1 & 0 & 0 & 0 & \ldots \\ 0 & m+1 & -(m+2) & 1 & 0 & 0 & \ldots \\
0 & 0 & m+1 & -(m+2) & 1 & 0 & \ldots
\\0 & 0 & 0 & m+1 & -(m+2) & 1 &\ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath}

\begin{corollary} The general term of the array $\mathbf{T}_m$ is
$$\mathbf{T}_m(n,k)=\sum_{j=k}^n (-1)^{n-j}\binom{n}{j}((m+1)^{j-k+1}-1)/m, \qquad m \ne 0.$$
\end{corollary}
\begin{proof} By the last proposition, we have
$$\mathbf{T}_m=\mathbf{B}^{-1}*\left(\frac{1}{1-x}\cdot\frac{1}{1-(m+1)x},x\right).$$
The general term of $\mathbf{B}^{-1}=\left(\frac{1}{1+x},\frac{x}{1+x}\right)$ 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.\end{proof}
\begin{corollary}
$$\mathbf{T}_{m-1}(n,k)=\sum_{j=k}^n (-1)^{n-j}\binom{n}{j}\frac{m^{j-k+1}-1}{m-1}=
\sum_{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}\mathbf{T}_{m-1}(n,k)=\binom{n}{k}\sum_{j=0}^{n-k}(-1)^{n-k-j}\binom{n}{j+k}(m^{j+1}-1).$$
\end{corollary}
This last result makes evident the link between the Riordan array
$\mathbf{T}_{m-1}$ and the weight distribution of MDS codes.
Thus, based on equation (\ref{A_i_eq_1}), we have
$$T_{q-1}(i,d_{min})=\sum_{j=d_{min}}^i (-1)^{i-j}\binom{i}{j}\frac{q^{j-d_{min}+1}-1}{q-1}.$$
Hence
\begin{eqnarray*} (q-1)\binom{n}{i}T_{q-1}(i,d_{min})&=&\binom{n}{i}\sum_{j=d_{min}}^i (-1)^{i-j}\binom{i}{j}(q^{j-d_{min}+1}-1)\\
&=&A_i.\end{eqnarray*}
and thus
\begin{equation}\label{A_i_R}A_i=(q-1)\binom{n}{i}T_{q-1}(i,d_{min}).\end{equation}
We now
find a number of alternative expressions for the general term of
$\mathbf{T}_m$ which will give us a choice of expressions for the
weight distribution of an MDS code.
\begin{proposition} \begin{eqnarray*} \mathbf{T}_m(n,k)&=&\sum_{j=0}^{n-k}(-1)^j\binom{j+k-2}{j}m^{n-k-j}\\
&=&\sum_{j=0}^{n-k}(-1)^{n-k-j}\binom{n-j-2}{n-j-k}m^j\\
&=&\sum_{j=k}^n \binom{n-1}{n-j}(-1)^{n-j}(m+1)^{j-k}.\end{eqnarray*}
\end{proposition}
\begin{proof} The first two equations result from
\begin{eqnarray*} \mathbf{T}_m(n,k)&=&[x^n]\frac{1+x}{1-mx}\left(\frac{x}{1+x}\right)^k\\
&=&[x^{n-k}](1-mx)^{-1}(1+x)^{-(k-1)}\\
&=&[x^{n-k}]\sum_{i \geq 0}m^ix^i\sum_{j \geq 0}\binom{-(k-1)}{j}x^j\\
&=&[x^{n-k}]\sum_{i \geq 0}\sum_{j \geq 0}\binom{k+j-2}{j}(-1)^jm^ix^{i+j}.\\
\end{eqnarray*}
An alternative proof for the second identity if furnished by using the convolution rule (rule $4$KE - \textbf{conv} in \cite{Spru_Ids}) to get:
\begin{eqnarray*} [x^n]\frac{1+x}{1-mx}\cdot \frac{x^k}{(1+x)^k}&=&[x^{n-k}]\frac{1}{1-mx}\cdot\frac{1}{(1+x)^{k-1}}\\
&=&\sum_{j=0}^{n-k}\binom{-k+1}{n-k-j}m^j\\
&=&\sum_{j=0}^{n-k}\binom{n-j-2}{n-k-j}(-1)^{n-k-j}m^j,\end{eqnarray*} while the first identity is obtained when we
apply the convolution rule in the symmetric way, i.e., with $j \mapsto n-k-j$.
The third equation is a consequence of the factorization
$$\mathbf{T}_m=\left(1,\frac{1}{1+x}\right)*\left(\frac{1}{1-(m+1)x},x\right)$$ since $\left(1, \frac{1}{1+x}\right)$ has
general term $\binom{n-1}{n-k}(-1)^{n-k}$.
\end{proof}
Thus we have, for instance,
$$(m-1)\binom{n}{k}\mathbf{T}_{m-1}(n,k)=(m-1)\binom{n}{k}\sum_{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 (\ref{A_i_R}),
\begin{eqnarray*}A_i&=&(q-1)\binom{n}{i}T_{q-1}(i,d_{min})\\
&=&(q-1)\binom{n}{i}\sum_{j=d_{min}}^i \binom{i-1}{i-j}(-1)^{i-j}q^{j-d_{min}}.\end{eqnarray*}
\section{Applications to MDS codes}
We begin this section with an example.

\begin{example} 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
$\mathbf{D}=\textrm{diag}(\binom{7}{0},\binom{7}{1},\ldots,\binom{7}{7},0,0,\ldots)$
denote the infinite square matrix all of whose entries are zero
except for those indicated. We form the matrix product
$(q-1)\mathbf{D}\mathbf{T}_{q-1}$, with $q=8$, to get
\begin{displaymath}7\textrm{diag}\left\{\binom{7}{j}\right\}\left(\begin{array}{cccccccccc} 1 & 0 & 0
& 0 & 0 & 0 & 0 & 0 & 0 &\ldots \\8 & 1 & 0 & 0 & 0 & 0 & 0& 0 & 0 &\ldots \\ 56 & 7 & 1 &
0 & 0 & 0 & 0 & 0 & 0 & \ldots \\ 392 & 49 & 6 & 1 & 0 & 0 & 0 & 0 & 0 & \ldots \\
2744 & 343 & 43 &
5 & 1 & 0 & 0 & 0 & 0 &\ldots
\\19208 & 2401 & 300 & 38 & 4 & 1 & 0 & 0 & 0 & \ldots\\
134456 & 16807 & 2101 & 262 & 34 & 3 & 1 & 0 & 0 & \ldots\\
941192 & 117649 & 14706 & 1839 & 228 & 31 & 2 & 1 & 0 & \ldots\\
6588344 & 823543 & 102943 & 12867 & 1611 & 197 & 29 & 1 & 1 & \ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath}

\begin{displaymath}=\left(\begin{array}{cccccccccc} 7 & 0 & 0
& 0 & 0 & 0 & 0 & 0 & 0 &\ldots \\392 & 49 & 0 & 0 & 0 & 0 & 0& 0 & 0 &\ldots \\
 8232 & 1029 & 147 &
0 & 0 & 0 & 0 & 0 & 0 & \ldots \\
96040 & 12005 & 1470 & \mathbf{245} & 0 & 0 & 0 & 0 & 0 & \ldots \\
672280 & 84035 & 10535 &
\mathbf{1225} & 245 & 0 & 0 & 0 & 0 &\ldots
\\2823576 & 352947 & 44100 & \mathbf{5586} & 588 & 147 & 0 & 0 & 0 & \ldots\\
6588344 & 823543 & 102949 & \mathbf{12838} & 1666 & 147 & 49 & 0 & 0 & \ldots\\
6588344 & 823543 & 102942 & \mathbf{12873} & 1596 & 217 & 14 & 7 & 0 & \ldots\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \ldots\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots
& \vdots & \ddots\end{array}\right)\end{displaymath}
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{displaymath}\begin{array}{c|c|c|c|c|c|c|c}A_0&A_1&A_2&A_3&A_4&A_5&A_6&A_7\\
\hline 1&0&0&245&1225&5586&12838&12873\end{array}\end{displaymath}
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}.$$ \end{example}
This last result leads us to define the \textit{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.
\begin{theorem} 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)\textrm{Diag}\left\{{\binom{n}{j}}\right\}\left(\frac{1+x}{1-(q-1)x},\frac{x}{1+x}\right).$$
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$. \end{theorem}
\begin{proof} Inspection of the expressions for the general term $\mathbf{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.
 \end{proof}
Thus the weight ratios satisfy the recurrence
$${\textstyle a_n=((q-1)\binom{d}{0}-\binom{d}{1})a_{n-1}+((q-1)\binom{d}{1}-\binom{d}{2})a_{n-2}+\cdots+((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=\sum_{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}\sum_{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}\left[\frac{4}{7}\cdot 12838+\frac{18}{21}\cdot 5586+\frac{20}{35}\cdot1225+\frac{7}{35}\cdot 245\right].$$
and
$$12838=\binom{7}{6}\left[\frac{4}{21}\cdot 5586+\frac{18}{35}\cdot 1225+\frac{20}{35}\cdot 245+\frac{7}{21}\cdot 0\right].$$

\section{Acknowledgements}
The author would like to thank an anonymous reviewer for their
careful reading of this manuscript and for their constructive
remarks.
\begin{thebibliography}{9}

\bibitem{Alter} D. Merlini, D. G. Rogers, R. Sprugnoli, and M.C. Verri,
On some alternative characterizations of Riordan arrays,
\emph{Canadian J. Math.}, \textbf{49} (2) (1997), 301--320.

\bibitem{MS} F. J. MacWilliams, N. J. A.~Sloane,
\textit{The Theory of Error-Correcting Codes},
North Holland, Amsterdam, 2003.

\bibitem{PW} W. W. Peterson, E. J. Weldon, \textit{Error-Correcting Codes},
2nd ed., MIT Press, Cambridge, 1984.

\bibitem{SGWW} L. W. Shapiro, S. Getu, W-J. Woan and L.C. Woodson,
The Riordan group, \emph{Discr. Appl. Math.} \textbf{34} (1991),
229--239.

\bibitem{SL1} N. J. A.~Sloane, \emph{The
On-Line Encyclopedia of Integer Sequences}. Published electronically
at \href{http://www.research.att.com/~njas/sequences/}{\texttt{http://www.research.att.com/$\sim$njas/sequences/}}, 2007.

\bibitem{SL2} N. J. A.~Sloane, The On-Line Encyclopedia of Integer
Sequences, \emph{Notices Amer.\ Math.\ Soc.}, \textbf{50} (2003), 912--915.

\bibitem{Spru_Ids} R. Sprugnoli, Riordan array proofs of identities in Gould's book,, available
at \href{http://www.dsi.unifi.it/~resp/GouldBK.pdf}{\texttt{http://www.dsi.unifi.it/$\sim$resp/GouldBK.pdf}}, 2007.

\bibitem{Spru} R. Sprugnoli, Riordan arrays and combinatorial sums,
\emph{Discrete Math.} \textbf{132} (1994), 267--290.

\bibitem{vanLint} J. H. van Lint, R. M. Wilson,
\textit{A Course in Combinatorics},
2nd ed., Cambridge University Press, 2001.

\bibitem{Bin} E. W. Weisstein, Binomial transform, published electronically
at
\href{http://mathworld.wolfram.com/BinomialTransform.html/}{\texttt{http://mathworld.wolfram.com/BinomialTransform.html/}}, 2007.

\end{thebibliography}

\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary
11B83; Secondary 94B05, 11B37, 11B65.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 21 2007;
revised version received November 16 2007.
Published in {\it Journal of Integer Sequences}, November 20 2007.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

