The invert transform, Bell numbers, Pascal triangle, permanents, matrix multiplication and matrix inversion, Catalan numbers.

Mats Granvik mats.granvik(AT)abo.fi and Gary W. Adamson INVERT transform

Consider the Pascal triangle:

{C=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&2&1&0&0&0&0&0\\ 1&3&3&1&0&0&0&0\\ 1&4&6&4&1&0&0&0\\ 1&5&10&10&5&1&0&0\\ 1&6&15&20&15&6&1&0\\ 1&7&21&35&35&21&7&1\end{array}\right)

Shift down the elements one step and add a diagonal of ones in the main diagonal.

{X=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0\\ 1&2&1&1&0&0&0&0\\ 1&3&3&1&1&0&0&0\\ 1&4&6&4&1&1&0&0\\ 1&5&10&10&5&1&1&0\\ 1&6&15&20&15&6&1&1\end{array}\right)

Change the sign of all the elements below the main diagonal. {X_{signed}} is found as a comment here: Oeis table A121207.

{X_{signed}=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ -1&1&0&0&0&0&0&0\\ -1&-1&1&0&0&0&0&0\\ -1&-2&-1&1&0&0&0&0\\ -1&-3&-3&-1&1&0&0&0\\ -1&-4&-6&-4&-1&1&0&0\\ -1&-5&-10&-10&-5&-1&1&0\\ -1&-6&-15&-20&-15&-6&-1&1\end{array}\right)

Calculate the matrix inverse and you will get:

{A=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 2&1&1&0&0&0&0&0\\ 5&3&1&1&0&0&0&0\\ 15&9&4&1&1&0&0&0\\ 52&31&14&5&1&1&0&0\\ 203&121&54&20&6&1&1&0\\ 877&523&233&85&27&7&1&1\end{array}\right)

As we see we have the Bell numbers in the first column. Oeis, Bell numbers. The INVERT transform of any number triangle is equivalent to the steps above, here with the INVERT transform of the Pascal triangle as example.

Repeating the procedure or algorithm (above), infinitely many times, will produce the Catalan numbers as a convergent Oeis Catalan numbers in all columns, regardless of starting triangle (or starting sequence). That is you input matrix {A} into the first step instead of matrix {C}.

{Cat=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 2&1&1&0&0&0&0&0\\ 5&2&1&1&0&0&0&0\\ 14&5&2&1&1&0&0&0\\ 42&14&5&2&1&1&0&0\\ 132&42&14&5&2&1&1&0\\ 429&132&42&14&5&2&1&1\end{array}\right)

Another way to calculate the first column in matrix A is by taking matrix powers of this matrix M. Here the elements in the main diagonal have been deleted except for the first element which is equal to 1. Taking matrix powers is simply matrix multiplication repeated, {M^2=M*M}, {M^3=M*M*M} and so on.

{M=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&2&1&0&0&0&0&0\\ 1&3&3&1&0&0&0&0\\ 1&4&6&4&1&0&0&0\\ 1&5&10&10&5&1&0&0\\ 1&6&15&20&15&6&1&0\end{array}\right)

{M^2=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&0\\ 4&1&0&0&0&0&0&0\\ 8&5&1&0&0&0&0&0\\ 16&17&7&1&0&0&0&0\\ 32&49&31&9&1&0&0&0\\ 64&129&111&49&11&1&0&0\end{array}\right)

{M^3=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&0\\ 5&0&0&0&0&0&0&0\\ 14&1&0&0&0&0&0&0\\ 41&9&1&0&0&0&0&0\\ 122&52&12&1&0&0&0&0\\ 365&246&88&15&1&0&0&0\end{array}\right)

{M^4=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&0\\ 5&0&0&0&0&0&0&0\\ 15&0&0&0&0&0&0&0\\ 51&1&0&0&0&0&0&0\\ 187&14&1&0&0&0&0&0\\ 715&121&18&1&0&0&0&0\end{array}\right)

{M^5=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&0\\ 5&0&0&0&0&0&0&0\\ 15&0&0&0&0&0&0&0\\ 52&0&0&0&0&0&0&0\\ 202&1&0&0&0&0&0&0\\ 855&20&1&0&0&0&0&0\end{array}\right)

{M^6=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&0\\ 5&0&0&0&0&0&0&0\\ 15&0&0&0&0&0&0&0\\ 52&0&0&0&0&0&0&0\\ 203&0&0&0&0&0&0&0\\ 876&1&0&0&0&0&0&0\end{array}\right)

{M^7=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 2&0&0&0&0&0&0&0\\ 5&0&0&0&0&0&0&0\\ 15&0&0&0&0&0&0&0\\ 52&0&0&0&0&0&0&0\\ 203&0&0&0&0&0&0&0\\ 877&0&0&0&0&0&0&0\end{array}\right)

As promised we have calculated the Bell numbers in the first column.

Yet another way to calculate the first column in matrix {A}, is to calculate permanents of a modified version of matrix {X}. Here the element in the lower right corner has been swapped with the element in the lower right corner.

{permanent}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&1\\ 1&1&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0\\ 1&2&1&1&0&0&0&0\\ 1&3&3&1&1&0&0&0\\ 1&4&6&4&1&1&0&0\\ 1&5&10&10&5&1&1&0\\ 1&6&15&20&15&6&1&0\end{array}\right){=}\begin{array}{c}877\end{array}

i.e. the last element in the first column of matrix {A}.

Similarly for submatrices:

{permanent}\left(\begin{array}{ccccccc}1&0&0&0&0&0&1\\ 1&1&0&0&0&0&0\\ 1&1&1&0&0&0&0\\ 1&2&1&1&0&0&0\\ 1&3&3&1&1&0&0\\ 1&4&6&4&1&1&0\\ 1&5&10&10&5&1&0\end{array}\right){=}\begin{array}{c}203\end{array}

i.e. the second last element in the first column of matrix {A}.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to The invert transform, Bell numbers, Pascal triangle, permanents, matrix multiplication and matrix inversion, Catalan numbers.

  1. Stefan says:

    Hi! This is really neat. I could really use the iterated invert function, but I’m not sure I’m doing it right! When I put a starting series
    (S =x +x^2+x^3+…)
    into (1/(1-S))-1 it gives the expected results. However, no amount of iterating by putting those results back in for S seems to converge to the catalan numbers. Hints?

  2. mobiusfunction says:

    Dear Stefan,

    I have here left out the indices of the elements for easier typing but hopefully this can still be understood.

    {A=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ x&1&0&0&0&0&0&0\\ x&x&1&0&0&0&0&0\\ x&x&x&1&0&0&0&0\\ x&x&x&x&1&0&0&0\\ x&x&x&x&x&1&0&0\\ x&x&x&x&x&x&1&0\\ x&x&x&x&x&x&x&1\end{array}\right)

    Shift down the elements in matrix {A} one step to get matrix {B}.

    {B=}\left(\begin{array}{cccccccc}0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ x&1&0&0&0&0&0&0\\ x&x&1&0&0&0&0&0\\ x&x&x&1&0&0&0&0\\ x&x&x&x&1&0&0&0\\ x&x&x&x&x&1&0&0\\ x&x&x&x&x&x&1&0\end{array}\right)

    Add a diagonal of ones to the main diagonal in matrix {B} to get matrix {C}.

    {C=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ x&1&1&0&0&0&0&0\\ x&x&1&1&0&0&0&0\\ x&x&x&1&1&0&0&0\\ x&x&x&x&1&1&0&0\\ x&x&x&x&x&1&1&0\\ x&x&x&x&x&x&1&1\end{array}\right)

    Change the sign of all the elements below the main diagonal in matrix {C} so that you get matrix {D}.

    {D=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ -1&1&0&0&0&0&0&0\\ -x&-1&1&0&0&0&0&0\\ -x&-x&-1&1&0&0&0&0\\ -x&-x&-x&-1&1&0&0&0\\ -x&-x&-x&-x&-1&1&0&0\\ -x&-x&-x&-x&-x&-1&1&0\\ -x&-x&-x&-x&-x&-x&-1&1\end{array}\right)

    Calculate the matrix inverse of matrix {D} to get matrix {E}

    Iterate by replacing matrix {A} with matrix {E}.

    Matrix {E} should then converge to the Catalan numbers in all columns.

  3. Stefan says:

    Wow, thanks! The algorithm is clear. But I’m going to have to study the relationship between the matrices and the generating functions. The link you gave at the top explained the INVERT transform in terms of generating functions and it seemed to correspond exactly to the matrices. However, maybe there is a big difference between INVERT on the generating function of a sequence, and INVERT on a (triangular) matrix. (I gather that the trinagular matrix corresponding to that sequence should have colomns with the sub diagonal entries the terms of the sequence as in Cat above.)

  4. Stefan says:

    …columns, that is…

  5. Stefan says:

    Ok–now I think I got it. Rather than the prescription for generating functions given in the link above (they say to take S(x) to (1/(1-S(x))) -1) I tried what the matrix algorithm actually said and took S(x) to 1/(1-x*S(x)). This indeed seems to give the Catalan number after iterating. Cool. I think there must be a species theory proof of this.

Comments are closed.