login
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.
10
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
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
KEYWORD
nonn,tabl,easy
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