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

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

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.

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)

Example

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;

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, k<Quotient[n, 2],   T[n, n-k], True, T[n-1, k-1] + T[n-1, k] - T[n-4, k-2]];
Table[T[n, k], {n, 0, 11}, { k, 0, n}] // Flatten (* Jean-François Alcover, Jul 30 2018 *)

Prog

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

Crossrefs

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

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

Sequence in context: A100522 A258140 A140408 * A036064 A352744 A347967

Adjacent sequences: A047077 A047078 A047079 * A047081 A047082 A047083

Keyword

nonn,tabl,easy

Author

Clark Kimberling

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

Status

approved