A026268 Triangle, T(n, k): T(n,k) = 1 for n < 3, T(3,1) = T(3,2) = T(3,3) = 2, T(n,0) = 1, T(n,1) = n-1, T(n,n) = T(n-1,n-2) + T(n-1,n-1), otherwise T(n,k) = T(n-1,k-2) + T(n-1,k-1) + T(n-1,k), read by rows.

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 3, 5, 6, 4, 1, 4, 9, 14, 15, 10, 1, 5, 14, 27, 38, 39, 25, 1, 6, 20, 46, 79, 104, 102, 64, 1, 7, 27, 72, 145, 229, 285, 270, 166, 1, 8, 35, 106, 244, 446, 659, 784, 721, 436, 1, 9, 44, 149, 385, 796, 1349, 1889, 2164, 1941, 1157, 1, 10, 54, 202, 578, 1330, 2530, 4034, 5402, 5994, 5262, 3098

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabl

Comments

a(n) = number of strings s(0)..s(n) such that s(n) = n-k, where s(0) = 0, s(1) = 1, |s(i)-s(i-1)| <= 1 for i >= 2; |s(2)-s(1)| = 1, and |s(3)-s(2)| = 1 if s(2) = 1.

Examples

			Triangle begins as:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,   2;
  1, 3,  5,   6,   4;
  1, 4,  9,  14,  15,  10;
  1, 5, 14,  27,  38,  39,   25;
  1, 6, 20,  46,  79, 104,  102,   64;
  1, 7, 27,  72, 145, 229,  285,  270,  166;
  1, 8, 35, 106, 244, 446,  659,  784,  721,  436;
  1, 9, 44, 149, 385, 796, 1349, 1889, 2164, 1941, 1157;
		

Links

• Clark Kimberling, Rows 0..100, flattened
• Index entries for triangles and arrays related to Pascal's triangle

Crossrefs

Cf. A026269, A026270, A026288, A026289, A026290, A026291, A026292, A026293.

Cf. A026294, A026295, A026296, A026297, A026299, A026519, A026536, A026552.

Cf. A026584, A027926, A212342.

Programs

Magma

f:= func< n | n eq 2 select 1 else (n^2 -n -2)/2 >;
function T(n,k) // T = A026268
  if k eq 0 or n lt 3 then return 1;
  elif k eq 1 then return n-1;
  elif k eq 2 then return f(n);
  elif k eq n then return T(n-1, n-2) + T(n-1, n-1);
  else return T(n-1, k-2) + T(n-1, k-1) + T(n-1, k);
  end if; return T;
end function;
[T(n,k): k in [0..n], n in [0..14]]; // G. C. Greubel, Sep 24 2022

Mathematica

T[n_, k_]:= T[n, k]= If[n<3 || k==0, 1, If[k==1, n-1, If[k==2, (n^2-n-2)/2 + Boole[n==2], If[k==n, T[n-1, n-2] +T[n-1, n-1], T[n-1, k-2] + T[n-1, k-1] + T[n -1, k] ]]]];
Table[T[n, k], {n,0,14}, {k,0,n}]//Flatten (* corrected by G. C. Greubel, Sep 24 2022 *)

SageMath

def T(n,k): # T = A026268
    if n<3 or k==0: return 1
    elif k==1: return n-1
    elif k==2: return (n^2 -n -2)//2 + int(n==2)
    elif k==n: return T(n-1, n-2) + T(n-1, n-1)
    else: return T(n-1, k-2) + T(n-1, k-1) + T(n-1, k)
flatten([[T(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Sep 24 2022

Formula

From G. C. Greubel, Sep 24 2022: (Start)

T(n, 1) = A000027(n-1), n >= 1.

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

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

T(n, n-2) = A026288(n), n >= 2.

T(n, n-3) = A026289(n), n >= 3.

T(n, n-4) = A026290(n), n >= 4.

T(n, n) = A026269(n), n >= 2.

T(n, floor(n/2)) = A026297(n), n >= 0.

T(2*n, n) = A026292(n).

T(2*n, n-1) = A026295(n), n >= 1.

T(2*n, n+1) = A026296(n), n >= 1.

T(2*n-1, n-1) = A026291(n), n >= 2.

T(3*n, n) = A026293(n), n >= 0.

T(4*n, n) = A026294(n), n >= 0.

Sum_{k=0..n} T(n, k) = A026299(n-1), n >= 3.(End)

Extensions

Updated by Clark Kimberling, Aug 29 2014

Indices of b-file corrected by Sidney Cadot, Jan 06 2023.