[seqfan] Triangles as matrices

[Christian G.Bower]

There many sequence transforms listed in the EIS.
Some of them are linear.
A linear transform of a sequence is one such that
T(a+b)=Ta+Tb where sequence addition is termwise addition.

Any linear transform can be represented as a matrix (infinite dimensional)
where each row has finitely many nonzeroes.

Frequently these matrices are lower triangular and correspond to
the well known triangles of mathematics.

For example the binomial transform corresponds to Pascal's triangle

1
1 1
1 2 1
1 3 3 1
...

We have the Boustrophedron transformation:

 1 
 1  1 
 1  2  1 
 2  3  3  1 
 5  8  6  4  1 
16 25 20 10  5 1 
61 96 75 40 15 6 1 
...

DIFF: The first differences of a sequence:

 1 
-1  1 
 0 -1  1 
 0  0 -1 1 
...

MOEBIUS:

0 
0  1 
0 -1  1 
0 -1  0  1 
0  0 -1  0 1 
0 -1  0  0 0 1 
0  1 -1 -1 0 0 1 

M2: Multiply all except 1st term by 2
NEGATE: Negate all except 1st term
PSUM: Partial sums (inverse of DIFF)
RIGHT: Shift right
STIRLING: Apply Stirling-2 triangle

Note that LEFT (shift left) is linear but not lower triangular.

It occured to me that many interesting things can be discovered
by applying standard matrix operations (like product and inversion)
on these transforms and other well known triangles.

For example, the inverse of Pascal's triangle is an alternating
sign Pascal's triangle

 1 
-1  1 
 1 -2  1 
-1  3 -3  1 
 1 -4  6 -4 1 
...

The square (matrix product with itself) of Pascal's is
 1 
 2  1 
 4  4  1 
 8 12  6 1 
16 32 24 8 1 
...
A038207.

The 3rd through 12th powers are also in the EIS
3rd: A027465 and A038219
4th: A038231
5th: A038243
6th: A038255
7th: A027466 and A038267
8th: A038279
9th: A038291
10th: A038303
11th: A038315
12th: A038327

The partition triangle A008284

1 
1 1 
1 1 1 
1 2 1 1 
1 2 2 1 1 
1 3 3 2 1 1 

Seems not to have such treatment as neither its square

 1 
 2  1 
 3  2  1 
 5  5  2 1 
 7  8  5 2 1 
11 15 10 5 2 1 

nor its inverse

 1 
-1  1 
 0 -1  1 
 1 -1 -1  1 
 0  1 -1 -1  1 
 0  1  0 -1 -1  1 
-1  1  1  0 -1 -1  1 
-1  0  2  0  0 -1 -1  1 
 0 -1  0  2  0  0 -1 -1 1 

appear in the EIS.

Transforming with the partition triangle might be useful to calculate
partitions into an even number of parts A026818 OR A027187:
1 0 1 1 3 3 6 7 12...
partitions into an odd number of parts A026817 OR A027193:
0 1 1 2 2 4 5 8 10...
or partitions into a prime number of parts (not in EIS):

There is also Wouter's favorite, the Catalan triangle A033184 and A009766:

 1 
 1  1 
 2  2 1 
 5  5 3 1 
14 14 9 4 1 

(shown here in reverse of Wouter's presentation. I find this
arrangement more useful.)

The matrix inverse:

 1 
-1  1 
 0 -2  1 
 0  1 -3  1 
 0  0  3 -4  1 
 0  0 -1  6 -5 1 

is an alternating sign Pascal's triangle turned on its side.

One thing I want to consider is how these triangles can be used to
define sequence multiplication.

Multiplication satisfies the following properties:

a*b=b*a             (commutative)
(a*b)*c=a*(b*c)     (associative)
a*(b+c)=a*b + a*c   (distributive)

The distributive property essentially says that multiplication by a
constant is a linear transform. Thus any sequence multiplication
satisfying that property is just turning a sequence into a matrix
and applying it to the other sequence.

I know of four models of sequence multiplication satisfying these
properties.

Termwise multiplication:
(a0,a1,a2,...) * (b0,b1,b2,...) = (a0*a1,b0*b1,...)

Multiplication of generating functions (or convolution)
cn=SUM{i+j=n}ai*bj

Multiplication of exponential generating functions
(or exponential convolution)
cn=SUM{i+j=n}c(i,j)*ai*bj

Dirichlet convolution
cn=SUM{i*j=n}ai*bj

I wonder if there are any others.

Christian


____________________________________________________________________
Get free e-mail and a permanent address at http://www.netaddress.com/?N=1