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).

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

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabl
• eigen

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

Conjecture: T(n,k) = A081577(n,k) - A081577(n-2,k-1). (A081577 is Pascal-(1,2,1) array). - Gerald McGarvey, Sep 20 2007

From Russell Jay Hendel, Jun 02 2015: (Start)

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

Examples

			Rows:
1;
1,1;
1,3,1;
1,6,6,1;
1,9,18,9,1;
1,12,39,39,12,1;
		

Crossrefs

Row sums: A052945. A054122 (diagonal), A052392 (subdiagonal).