A047072 Array A read by diagonals: A(h,k)=number of paths consisting of steps from (0,0) to (h,k) such that each step has length 1 directed up or right and no step touches the line y=x unless x=0 or x=h.

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 3, 2, 2, 3, 1, 1, 4, 5, 4, 5, 4, 1, 1, 5, 9, 5, 5, 9, 5, 1, 1, 6, 14, 14, 10, 14, 14, 6, 1, 1, 7, 20, 28, 14, 14, 28, 20, 7, 1, 1, 8, 27, 48, 42, 28, 42, 48, 27, 8, 1, 1, 9, 35, 75, 90, 42, 42, 90, 75, 35, 9, 1

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabl

Examples

			Array, A(n, k), begins as:
  1, 1,  1,  1,  1,   1,   1,   1, ...;
  1, 2,  1,  2,  3,   4,   5,   6, ...;
  1, 1,  2,  2,  5,   9,  14,  20, ...;
  1, 2,  2,  4,  5,  14,  28,  48, ...;
  1, 3,  5,  5, 10,  14,  42,  90, ...;
  1, 4,  9, 14, 14,  28,  42, 132, ...;
  1, 5, 14, 28, 42,  42,  84, 132, ...;
  1, 6, 20, 48, 90, 132, 132, 264, ...;
Antidiagonals, T(n, k), begins as:
  1;
  1,  1;
  1,  2,  1;
  1,  1,  1,  1;
  1,  2,  2,  2,  1;
  1,  3,  2,  2,  3,  1;
  1,  4,  5,  4,  5,  4,  1;
  1,  5,  9,  5,  5,  9,  5,  1;
  1,  6, 14, 14, 10, 14, 14,  6,  1;
		

Links

• G. C. Greubel, Antidiagonals n = 0..50, flattened
• R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Crossrefs

Cf. A000007, A000027, A000096, A002420.

Cf. A005586, A025174, A047079, A063886.

Cf. A047073, A047074, A047079.

The following are all versions of (essentially) the same Catalan triangle: A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.

Diagonals give A000108, A000245, A002057, A000344, A003517, A000588, A003518, A003519, A001392, ...

Programs

Magma

b:= func< n | n eq 0 select 1 else 2*Catalan(n-1) >;
function A(n,k)
  if k eq n then return b(n);
  elif k gt n then return Binomial(n+k-1, n) - Binomial(n+k-1, n-1);
  else return Binomial(n+k-1, k) - Binomial(n+k-1, k-1);
  end if; return A;
end function;
// [[A(n,k): k in [0..12]]: n in [0..12]];
T:= func< n,k | A(n-k, k) >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 13 2022

Mathematica

A[, 0]= 1; A[0, ]= 1; A[h_, k_]:= A[h, k]= If[(k-1>h || k-1Jean-François Alcover, Mar 06 2019 *)

SageMath

def A(n,k):
    if (k==n): return 2*catalan_number(n-1) + 2*int(n==0)
    elif (k>n): return binomial(n+k-1, n) - binomial(n+k-1, n-1)
    else: return binomial(n+k-1, k) - binomial(n+k-1, k-1)
def T(n,k): return A(n-k, k)
# [[A(n,k) for k in range(12)] for n in range(12)]
flatten([[T(n,k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Oct 13 2022

Formula

A(n, n) = 2*[n=0] - A002420(n),

A(n, n+1) = 2*A000108(n-1), n >= 1.

From G. C. Greubel, Oct 13 2022: (Start)

T(n, n-1) = A000027(n-2) + 2*[n<3], n >= 1.

T(n, n-2) = A000096(n-4) + 2*[n<5], n >= 2.

T(n, n-3) = A005586(n-6) + 4*[n<7] - 2*[n=3], n >= 3.

T(2*n, n) = 2*A000108(n-1) + 3*[n=0].

T(2*n-1, n-1) = T(2*n+1, n+1) = A000180(n).

T(3*n, n) = A025174(n) + [n=0]

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

Sum_{k=0..n} (-1)^k * T(n, k) = A000007(n).

Sum_{k=0..floor(n/2)} T(n, k) = A047079(n). (End)