|
| |
|
|
A054120
|
|
Triangular array T(n,k): start with T(n,0)=T(n,n)=1 for n >= 0; recursively, draw vertical lines through T(n-1,k-1) if present and T(n-1,k) if present; then T(n,k) is the sum of T(i,j) that lie on or between the lines and not below T(n,k).
|
|
3
|
|
|
|
1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 9, 18, 9, 1, 1, 12, 39, 39, 12, 1, 1, 15, 69, 114, 69, 15, 1, 1, 18, 108, 261, 261, 108, 18, 1, 1, 21, 156, 507, 750, 507, 156, 21, 1, 1, 24, 213, 879, 1779, 1779, 879, 213, 24, 1, 1, 27, 279, 1404, 3672, 5058
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Conjecture: T(n,k) = T(n-1,k-1) + 2*T(n-2,k-1) + T(n-1,k) (except for T(0,0) = 1 and T(2,1) = 3 and assuming that T(n,k) = 0 for elements outside the triangular array). - Gerald McGarvey, Sep 20 2007
We prove the 1st McGarvey conjecture, (A) T(n,k)=T(n-1,k-1)+2*T(n-2,k-1)+T(n-1,k), with McGarvey's added modifications that n >= 3 and that T(n,k)=0 for n<0, k<0, and k>n. We make explicit that the rows and columns of the triangle start at 0 and furthermore, that both diagonals are at 45 degrees to the perpendicular (in both directions). Note that we use letters (A), (B), (C) to indicate equations.
We indicate the set of numbers corresponding to the half-line starting at T(n,k) with(B) L(n,k)={T(n,k), T(n-2,k-1), T(n-4,k-2),T(n-6,k-3),...}. There is no loss of generality in extending this line upwards indefinitely since most of the numbers lying on a half-ray are 0 anyway. If S_1, S_2, S_3 are sets, then the notation SUM(S_1,S_2, S_3) will indicate the sum of all elements in S_1, S_2 and S_3.
Using two applications of (B) we have the identity (C) L(n,k)={T(n,k)} UNION L(n-2,k-1). The definition of T(n,k) is given by (D) T(n,k)=SUM(L(n-1,k-1),L(n-2,k-1),L(n-1,k)). Combining (D) with (C), we immediately have (E), T(n,k)=T(n-1,k-1)+T(n-2,k-1)+T(n-1,k)+SUM(L(n-3,k-2), L(n-4,k-2), L(n-3,k-1)). By another application of (D), we have (F), T(n-2,k-1)=SUM(L(n-3,k-2),L(n-4,k-2),L(n-3,k-1)). Combining (E) and (F), we obtain (A) as required.
We illustrate the proof with n=5 and k=3. We first calculate T(3,2). By (D), we have (G) T(3,2)=6=SUM(L(2,1),L(1,1),L(2,2)) with L(2,1)={3,1,0,0,0,...}, L(1,1)={1,0,0,....} and L(2,2)={1,0,0,...}. By another application of (D), we have T(5,3)=39=(SUM(L(4,2),L(3,2),L(4,3)) where L(4,2)={18,3,1,...}={18} UNION L(2,1), L(3,2)={6,1,0,...}={6} UNION L(1,1), and L(4,3) = {1,0,0,...}={1} UNION L(2,2). Combining this last equation with (G), we have T(5,3)=39=18+6+1+SUM(L(2,1),L(1,1),L(2,2))=18+6+1+6=18+2*6+1 as required.
Note: There are two parts to the definition of the triangle:(i) T(n,0)=1, and ii) equation (D). Since (D) does not apply to T(0,0), (A) does not hold there. Since (D) applied to T(2,1) refers back to T(0,0), (A) does not hold there either. This explains the McGarvey requirement that n>=3. (End)
Consider the array with g.f. (1-u*v)/(1-u-v-2*u*v). The triangle appears to be that symmetric array read by antidiagonals. - R. J. Mathar, Jan 26 2022
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Rows:
1;
1,1;
1,3,1;
1,6,6,1;
1,9,18,9,1;
1,12,39,39,12,1;
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
