A026626 Triangular array T read by rows: T(n,0) = T(n,n) = 1 for n >= 0, T(n,1) = T(n,n-1) = floor(3*n/2) for n >= 1, T(n,k) = T(n-1,k-1) + T(n-1,k) for 2 <= k <= n-2, n >= 4.

1, 1, 1, 1, 3, 1, 1, 4, 4, 1, 1, 6, 8, 6, 1, 1, 7, 14, 14, 7, 1, 1, 9, 21, 28, 21, 9, 1, 1, 10, 30, 49, 49, 30, 10, 1, 1, 12, 40, 79, 98, 79, 40, 12, 1, 1, 13, 52, 119, 177, 177, 119, 52, 13, 1, 1, 15, 65, 171, 296, 354, 296, 171, 65, 15, 1, 1, 16, 80, 236, 467, 650, 650, 467, 236, 80, 16, 1

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabl
• easy

Examples

			Triangle begins as:
  1;
  1,  1;
  1,  3,  1;
  1,  4,  4,   1;
  1,  6,  8,   6,   1;
  1,  7, 14,  14,   7,   1;
  1,  9, 21,  28,  21,   9,   1;
  1, 10, 30,  49,  49,  30,  10,   1;
  1, 12, 40,  79,  98,  79,  40,  12,   1;
  1, 13, 52, 119, 177, 177, 119,  52,  13,   1;
  1, 15, 65, 171, 296, 354, 296, 171,  65,  15,  1;
		

Links

• G. C. Greubel, Rows n = 0..50 of the triangle, flattened
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A006578, A026627, A026628, A026629, A026630, A026631, A026632.

Cf. A026633, A026634, A026635, A026636, A026961, A026962, A026963.

Cf. A026964, A026965, A032766, A084056.

Programs

Magma

function T(n,k) // T = A026626
  if k eq 0 or k eq n then return 1;
  elif k eq 1 or k eq n-1 then return Floor(3*n/2);
  else return T(n-1,k-1) + T(n-1,k);
  end if;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jun 19 2024

Mathematica

T[n_, k_]:= T[n, k]= If[k==0 || k==n, 1, If[k==1 || k==n-1, (6*n-1+(-1)^n)/4, T[n-1, k-1] + T[n-1, k] ]];
Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jun 19 2024 *)

SageMath

def T(n,k): # T = A026626
    if (k==0 or k==n): return 1
    elif (k==1 or k==n-1): return int(3*n//2)
    else: return T(n-1,k-1) + T(n-1,k)
flatten([[T(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jun 19 2024

Formula

T(n, k) = number of paths from (0, 0) to (n-k, k) in the directed graph having vertices (i, j) and edges (i, j)-to-(i+1, j) and (i, j)-to-(i, j+1) for i, j >= 0 and edges (i, j)-to-(i+1, j+1) for i=0, j >= 0 and even and for j=0, i >= 0 and even.

From G. C. Greubel, Jun 19 2024: (Start)

T(n, n-k) = T(n, k)

T(n, 1) = (-1)^n*A084056(n) = A032766(n), n >= 1.

T(n, 2) = A006578(n-1), n >= 2.

T(n, 3) = (1/16)*(4*n^3 - 14*n^2 + 12*n + 15 + (-1)^n) - [n=3] , n >= 3.

Sum_{k=0..n} (-1)^k*T(n, k) = A176742(n) + [n=2].

Sum_{k=0..floor(n/2)} (-1)^k*T(n-k, k) = (1/4)*((-1)^n*(8/sqrt(3)* sin(2*(n+1)*Pi/3) - 2*cos(n*Pi/2) + 1) - 3) + [n<2].

Sum_{k=0..n} k*T(n, k) = (1/6)*n*(17*2^(n-2) - 2 - (1-(-1)^n)) + (1/4)*[n=1]. (End)