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,5

Links

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Index entries for sequences related to rooted trees

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)

Example

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;

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

Prog

(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
(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

Crossrefs

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

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

Cf. A026964, A026965, A032766, A084056.

Sequence in context: A026670 A131402 A238498 * A136482 A026648 A026747

Adjacent sequences: A026623 A026624 A026625 * A026627 A026628 A026629

Keyword

nonn,tabl,easy

Author

Clark Kimberling

Status

approved