A047080 Triangular array T read by rows: T(h,k)=number of paths from (0,0) to (k,h-k) using step-vectors (0,1), (1,0), (1,1) with no right angles between pairs of consecutive steps.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 1, 1, 4, 5, 5, 4, 1, 1, 5, 8, 9, 8, 5, 1, 1, 6, 12, 15, 15, 12, 6, 1, 1, 7, 17, 24, 27, 24, 17, 7, 1, 1, 8, 23, 37, 46, 46, 37, 23, 8, 1, 1, 9, 30, 55, 75, 83, 75, 55, 30, 9, 1, 1, 10, 38, 79, 118, 143, 143, 118, 79, 38, 10, 1

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• tabl
• easy

Comments

T(n,k) equals the number of reduced alignments between a string of length n and a string of length k. See Andrade et. al. - Peter Bala, Feb 04 2018

Examples

			E.g., row 3 consists of T(3,0)=1; T(3,1)=2; T(3,2)=2; T(3,3)=1.
Triangle begins:
  1;
  1,  1;
  1,  1,  1;
  1,  2,  2,  1;
  1,  3,  3,  3,  1;
  1,  4,  5,  5,  4,  1;
  1,  5,  8,  9,  8,  5,  1;
  1,  6, 12, 15, 15, 12,  6,  1;
		

Links

• Muniru A Asiru, Table of n, a(n) for n = 0..1325
• H. Andrade, I. Area, J. J. Nieto, and A. Torres, The number of reduced alignments between two DNA sequences, BMC Bioinformatics (2014) Vol. 15: 94.

Crossrefs

Cf. A047081, A047082, A047083, A047084, A047085, A047086, A047087, A047088.

Cf. A001590, A022856, A028310, A078042, A089071, A091337, A171155.

Programs

Magma

F:=Factorial;
p:= func< n,k | (&+[ (-1)^j*F(n+k-3*j)/(F(j)*F(n-2*j)*F(k-2*j)): j in [0..Min(Floor(n/2), Floor(k/2))]]) >;
q:= func< n,k | n eq 0 or k eq 0 select 0 else (&+[ (-1)^j*F(n+k-3*j-2)/(F(j)*F(n-2*j-1)*F(k-2*j-1)) : j in [0..Min(Floor((n-1)/2), Floor((k-1)/2))]]) >;
A:= func< n,k | p(n,k) - q(n,k) >;
A047080:= func< n,k | n eq 0 select 1 else A(n-k, k) >;
[[A(n,k): k in [1..6]]: n in [1..6]];
[A047080(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 30 2022

Maple

T := proc(n, k) option remember; if n < 0 or k > n then return 0 fi;
if n < 3 then return 1 fi; if k < iquo(n,2) then return T(n, n-k) fi;
T(n-1, k-1) + T(n-1, k) - T(n-4, k-2)  end:
seq(seq(T(n,k), k=0..n), n=0..11); # Peter Luschny, Feb 11 2018

Mathematica

T[n_, k_] := T[n, k] = Which[n<0 || k>n, 0, n<3, 1, kJean-François Alcover, Jul 30 2018 *)

SageMath

f=factorial
def p(n,k): return sum( (-1)^j*f(n+k-3*j)/(f(j)*f(n-2*j)*f(k-2*j)) for j in range(1+min((n//2), (k//2))) )
def q(n,k): return sum( (-1)^j*f(n+k-3*j-2)/(f(j)*f(n-2*j-1)*f(k-2*j-1)) for j in range(1+min(((n-1)//2), ((k-1)//2))) )
def A(n,k): return p(n,k) - q(n,k)
def A047080(n,k): return A(n-k, k)
flatten([[A047080(n,k) for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Oct 30 2022

Formula

T(h, k) = T(h-1, k-1) + T(h-1, k) - T(h-4, k-2);

Writing T(h, k) = F(h-k, k), generating function for F is (1-xy)/(1-x-y+x^2y^2).

From Peter Bala, Feb 04 2018: (Start)

T(n, k) = (Sum_{i = 0..A} (-1)^i*(n+k-3*i)!/(i!*(n-2*i)!*(k-2*i)!)) - (Sum_{i = 0..B} (-1)^i*(n+k-3*i-2)!/(i!*(n-2*i-1)!*(k-2*i-1)!)), where A = min{floor(n/2), floor(k/2)} and B = min{floor((n-1)/2), floor((k-1)/2)}.

T(2*n, n) = A171155(n). (End)

From G. C. Greubel, Oct 30 2022: (Start) (formulas for triangle T(n,k))

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

T(n, n) = A000012(n).

T(n, n-1) = A028310(n-1).

T(n, n-2) = A089071(n-1) = A022856(n+1).

T(2*n, n-1) = A047087(n).

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

Sum_{k=0..n} T(n, k) = (-1)^n*A078042(n) = A001590(n+3).

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

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

Extensions

Sequence recomputed to correct terms from 23rd onward, and recurrence and generating function added by Michael L. Catalano-Johnson (mcj(AT)pa.wagner.com), Jan 14 2000