Given triangle M as an infinite lower triangular matrix, there is some sequence prefaced with a "1" such that M*(seq prefaced with a 1) shifts the sequence to the left, deleting the "1", while the rest of the sequence remains the same. That seq is the Eigensequence of a triangle (defined without the prepended 1).
.
Example: The Eigensequence of Pascal's triangle is A000110 in Sloane's Encyclopedia of Integer Sequences: (1, 2, 5, 15, 52,...) = the Bell seq; since letting the Pascal matrix = M, then M*(1, 1, 2, 5, 15, 52,...) = (1, 2, 5, 15, 52,...).
.
Getting the Eigensequence. Simple. Place a "1" at the top of the triangle M, getting: (using the initial Pascal's triangle):
1
1;
1, 1;
1, 2, 1;
1, 3, 3, 1;
1, 4, 6, 4, 1;
...
= new triangle Q. Take successive powers of Q, shifting all terms into a vector which is (1, 1, 2, 5, 15, 52,...). Delete the initial 1 getting (1, 2, 5, 15, 52,...), = the Bell sequence which is the Eigensquence of Pascal's Triangle.
...
THEOREM: Given an infinite Toeplitz triangle with sequence S(n) in every column, we obtain the Eigensequence as before; with the additional property that in such a Toeplitz triangle, the Eigensequence is the INVERT transform of S(n).
...
Example: Given S(n) = (1, 2, 3, 4,...), our Toeplitz triangle =
1;
2, 1;
3, 2, 1;
4, 3, 2, 1;
... = M
We place a "1" at top, take powers, getting our left-shifted vector (even-indexed Fibonacci numbers after deleting the 1): (1, 3, 8 21, 55,...). So (1, 3, 8, 21,...) is the Eigensequence of the triangle and the INVERT transform of (1, 2, 3, 4,....), the natural numbers.
.
To obtain an Eigentriangle R which has row sums of the Eigensequence of triangle M, we take the row terms of M, multiplying pairwise by terms in its Eigensequence (prefaced with a 1). Thus, using the above triangle M and (1, 1, 3, 8, 21,...) our products are (1), [(2,1)*(1,1) = (2,1)], then [(3,2,1)*(1,1,3) = (3,2,3)];, then [(4,3,2,1)*(1,1,3,8) = (4,3,6,8)]; so our Eigentriangle R =
1;
2, 1;
3, 2, 3;
4, 3, 6, 8;
... = R
...which as you can see has row sums of (1, 3, 8, 21,...). Thus, R is the Eigentriangle of triangle M.
Thursday, January 19, 2012
Matrix generation of sequences
Observe the following infinite square production matrix:
1, 1, 0, 0, 0, 0,...
A, 0, 1, 0, 0, 0,...
B, 0, 0, 1, 0, 0,..
C, 0, 0, 0, 1, 0,...
D, 0, 0, 0, 0, 1,...
...
Say we have a finite (A,B,C) = (1, 1, 2). Then the g.f. (generating function) is:
1/(1-Ax-Bx^2-Cx^3) = 1/(1-x-x^2-2x^3) and the recursive relationship is:
a(n) = A*a(n-1) + B*a(n-2) + C *a(n-3).
The matrix generator is:
1, 1, 0
1, 0, 1
2, 0, 0
= M.
Any of these methods generates A077947: (1, 2, 5, 9, 18, 37, 73,...) as follows:
First, we plug in 1/(1-x-x^2-2x^3) into WolframAlpha, enter, and up comes the sequence.
By recursion, 18 = 1*9 + 1*5 + 2*2 = 9 + 5 = 4; or, a(n) = 1*a(n-1) + 1*a(n-2) * 2*a(n-3).
Or, let the Matrix = M, then take successive powers * the vector
[1
0
0]
...accessing top term; thus a(n) = M^n*[1,0,0], top term. Note that we extract the generating matrix M from the infinite square production matrix, such that M is an n*n matrix depending on the numbers of terms in (A,B,C...). That is, 3 in this case.
1, 1, 0, 0, 0, 0,...
A, 0, 1, 0, 0, 0,...
B, 0, 0, 1, 0, 0,..
C, 0, 0, 0, 1, 0,...
D, 0, 0, 0, 0, 1,...
...
Say we have a finite (A,B,C) = (1, 1, 2). Then the g.f. (generating function) is:
1/(1-Ax-Bx^2-Cx^3) = 1/(1-x-x^2-2x^3) and the recursive relationship is:
a(n) = A*a(n-1) + B*a(n-2) + C *a(n-3).
The matrix generator is:
1, 1, 0
1, 0, 1
2, 0, 0
= M.
Any of these methods generates A077947: (1, 2, 5, 9, 18, 37, 73,...) as follows:
First, we plug in 1/(1-x-x^2-2x^3) into WolframAlpha, enter, and up comes the sequence.
By recursion, 18 = 1*9 + 1*5 + 2*2 = 9 + 5 = 4; or, a(n) = 1*a(n-1) + 1*a(n-2) * 2*a(n-3).
Or, let the Matrix = M, then take successive powers * the vector
[1
0
0]
...accessing top term; thus a(n) = M^n*[1,0,0], top term. Note that we extract the generating matrix M from the infinite square production matrix, such that M is an n*n matrix depending on the numbers of terms in (A,B,C...). That is, 3 in this case.
Subscribe to:
Posts (Atom)