Pascal’s triangle is the Riordan array that most people are familiar with. Like all Riordan arrays, it has infinite extent, in that the pattern that defines it can be continued indefinitely. We show the first seven rows, but we can easily generate more, according to two simple rules:
The first column elements are all \(1\).
If the element in the \(n\)-th row and the \(k\)-th column is called \(T(n,k)\), then we have \[ T(n+1,k+1)=T(n,k)+T(n+1,k)\]
\[\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 & 0 & 0 \\ 1 & 4 & 6 & 4 & 1 & 0 & 0 \\ 1 & 5 & 10 & 10 & 5 & 1 & 0 \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 \\ \end{array} \right)\]
Since mathematicians like to use sub-scripts, we can also write the defining rule as \[T_{n+1,k+1}=T_{n,k}+T_{n+1,k}\]
For instance, we have
Notice that we have represented Pascal’s triangle as a “lower-triangular” matrix, in which all elements above the main diagonal (which is made up of \(1\)’s) are zero. This is a feature of Riordan arrays.
Another well-known matrix that is a Riordan array is the identity matrix. This is the infinite matrix that has \(1\)’s on the diagonal, and zeros everywhere else. Again, we show its first seven rows below.
\[\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right)\]
If we let \(I_{n,k}\) denote the element in the \(n\)-th row and the \(i\)-th column of this matrix, then we have the simple defining rules
The first column is \(1,0,0,0,\ldots\)
For elements not in the first column, we have \[I_{n+1,k+1}=I_{n,k}\]
Now consider the following matrix.
\[\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 & 0 \\ 4 & 5 & 3 & 1 & 0 & 0 & 0 \\ 9 & 12 & 9 & 4 & 1 & 0 & 0 \\ 21 & 30 & 25 & 14 & 5 & 1 & 0 \\ 51 & 76 & 69 & 44 & 20 & 6 & 1 \\ \end{array} \right)\]
Can you see a pattern defining the internal elements (that is, the elements not in the first column)?
Taking the \(12\) that we can see in the second column, and looking at the row above it, we can see that we have \(12=4+5+3\). Now look at the \(25\) in the third column. Again looking at the row above it, we have \(25=12+9+4\). Thus it would appear that we have \[T_{n+1,k+1}=T_{n,k}+T_{n+1,k}+T_{n+2,k}\]
What about the first column? Take the \(21\) for example. We see that \[21=9+12\] Here, since we cannot go to the left, we have just gone to the number immediately above the \(21\), to start the process. In like manner, we see that we have \[T_{n+1,0}=T_{n,0}+T_{n,1}\] where we refer to the first, or the initial column, as the \(0\)-th column.
This sub-scripting (or indexing) from \(0\) is something that is very useful for Riordan arrays, but which departs from the usual convention for matrices. Thus it is something that the novice is invited to get used to in the early stages of learning about Riordan arrays.
The initial column is thus the \(0\)-th or zero-th column, the next one is the \(1\)-th column and so on. The same holds good for the rows: the initial row is the \(0\)-th row, the next one is the \(1\)-th row.
Thus the element in the first position (top left hand corner) is the \((0,0)\) element. In matrix theory, this is normally referred to as the \((1,1)\) position.
Now let us look at the following Riordan array.
\[\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 3 & 1 & 0 & 0 & 0 & 0 \\ 5 & 9 & 5 & 1 & 0 & 0 & 0 \\ 14 & 28 & 20 & 7 & 1 & 0 & 0 \\ 42 & 90 & 75 & 35 & 9 & 1 & 0 \\ 132 & 297 & 275 & 154 & 54 & 11 & 1 \\ \end{array} \right)\]
Can you see that we have
\[T_{n+1,k+1}=T_{n,k}+2 T_{n,k+1} + T_{n,k+2}\] for the internal elements, and \[T_{n+1,0}=T_{n,0}+T_{n,1}\] for the first column elements.
We write these expressions as
\[T_{n+1k+1}=1\cdot T_{n,k}+2\cdot T_{n,k+1} + 1\cdot T_{n,k+2}\] and \[T_{n+1,0}=1\cdot T_{n,0}+ 1 \cdot T_{n,1}\]
We call the two patterns \((1,2,1)\) and \((1,1)\) the \(A\) and the \(Z\) sequences of the given Riordan array.
For example, the Riordan array given by Pascal’s triangle has its \(A\) sequence given by \((1,1)\) and its \(Z\) sequence given by \((1)\).
The \(A\) sequence and the \(Z\) sequence allow us to uniquely determine the corresponding Riordan array.
These sequences do not have to be of finite extent.
Consider the following Riordan array.
\[\left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 5 & 5 & 3 & 1 & 0 & 0 & 0 & 0 \\ 14 & 14 & 9 & 4 & 1 & 0 & 0 & 0 \\ 42 & 42 & 28 & 14 & 5 & 1 & 0 & 0 \\ 132 & 132 & 90 & 48 & 20 & 6 & 1 & 0 \\ 429 & 429 & 297 & 165 & 75 & 27 & 7 & 1 \\ \end{array} \right)\]
Taking the \(14\) in the second column, we see that \[14=5+5+3+1,\] or \[14=1 \cdot 5 + 1\cdot 5 + 1\cdot 3 + 1 \cdot 1.\]
Now take the \(132\) in the second column. We have \[132 = 42+42+28+14+5+1\] or \[132 = 1\cdot 42 + 1 \cdot 42 + 1 \cdot 14 + 1 \cdot 5 + 1 \cdot 1.\]
In fact, we find that the \(A\) sequence in this case is the infinite sequence \[1,1,1,1,\ldots\] of all \(1\)’s. Note that this is where the lower-triangular nature of Riordan arrays comes into play, since once we go beyond the diagonal element of a row, we are multiplying the \(A\) sequence elements by \(0\), so in each case the sum of products that defines \(T_{n,k}\) is finite.
After this brief introduction to Riordan arrays, it is interesting to look at their historical development.
The history of Pascal’s triangle goes back to antiquity. Its history begins with the study of the expression \((a+b)^n\), which nowadays is known as the Binomial Theorem, which says that \[(a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}.\] The binomial coefficients \(\binom{n}{k}\) are precisely the elements of Pascal’s triangle. The coefficients of \((a+b)^3\) were known in India in the \(6^{th}\) century BC. Records show that in Greece, \((a+b)^2\) was studied intensively in the \(2^{nd}\) BC. By the \(11^{th}\) century AD, in Persia, a sophisticated understanding of the binomail theorem had developed. One of the mathematicians to write about this was Omar Khayyam (1048-1141), the famous mathematician, astronomer and poet. In China, mathematicians had reportedly written about Pascal’s triangle in the \(11\)th century, and there are \(13\)th century documents attesting to this. In Europe, Pascal’s triangle was popularised by the French mathematician Blaise Pascal (1632-1662).
While Pascal’s triangle is the first Riordan array to have been extensively, it was not until 1991 that the first publication on Riordan arrays using this name appeared. This was the paper “The Riordan Group”, written by Louis Shapiro, Seyoum Getu, Wen-Jin Woan, and Leon Woodson, which appeared in the journal Discrete Applied Mathematics, in 1991. The authors were based in Howard University, Washington DC.
This paper emphasised two things:
Other early pioneers in Riordan array theory included Renzo Sprugnoli and Donatella Merlini, from the Universita di Firenze, in Florence, Italy.