|
%I #33 Oct 31 2022 07:34:20
%S 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,
%T 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,
%U 83,75,55,30,9,1,1,10,38,79,118,143,143,118,79,38,10,1
%N 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.
%C 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
%H Muniru A Asiru, <a href="/A047080/b047080.txt">Table of n, a(n) for n = 0..1325</a>
%H H. Andrade, I. Area, J. J. Nieto, and A. Torres, <a href="https://doi.org/10.1186/1471-2105-15-94">The number of reduced alignments between two DNA sequences</a> BMC Bioinformatics (2014) Vol. 15: 94.
%F T(h, k) = T(h-1, k-1) + T(h-1, k) - T(h-4, k-2);
%F Writing T(h, k) = F(h-k, k), generating function for F is (1-xy)/(1-x-y+x^2y^2).
%F From _Peter Bala_, Feb 04 2018: (Start)
%F 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)}.
%F T(2*n,n) = A171155(n). (End)
%F From _G. C. Greubel_, Oct 30 2022: (Start) (formulas for triangle T(n,k))
%F T(n, n-k) = T(n, k).
%F T(n, n) = A000012(n).
%F T(n, n-1) = A028310(n-1).
%F T(n, n-2) = A089071(n-1) = A022856(n+1).
%F T(2*n, n-1) = A047087(n).
%F T(2*n+1, n-1) = A047088(n).
%F Sum_{k=0..n} T(n, k) = (-1)^n*A078042(n) = A001590(n+3).
%F Sum_{k=0..n} (-1)^k*T(n, k) = A091337(n+1).
%F Sum_{k=0..floor(n/2)} T(n, k) = A047084(n). (End)
%e E.g., row 3 consists of T(3,0)=1; T(3,1)=2; T(3,2)=2; T(3,3)=1.
%e Triangle begins:
%e 1;
%e 1, 1;
%e 1, 1, 1;
%e 1, 2, 2, 1;
%e 1, 3, 3, 3, 1;
%e 1, 4, 5, 5, 4, 1;
%e 1, 5, 8, 9, 8, 5, 1;
%e 1, 6, 12, 15, 15, 12, 6, 1;
%p T := proc(n, k) option remember; if n < 0 or k > n then return 0 fi;
%p if n < 3 then return 1 fi; if k < iquo(n,2) then return T(n, n-k) fi;
%p T(n-1, k-1) + T(n-1, k) - T(n-4, k-2) end:
%p seq(seq(T(n,k), k=0..n), n=0..11); # _Peter Luschny_, Feb 11 2018
%t 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]];
%t Table[T[n, k], {n, 0, 11}, { k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 30 2018 *)
%o (Magma)
%o F:=Factorial;
%o 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))]]) >;
%o 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))]]) >;
%o A:= func< n,k | p(n,k) - q(n,k) >;
%o A047080:= func< n,k | n eq 0 select 1 else A(n-k, k) >;
%o [[A(n,k): k in [1..6]]: n in [1..6]];
%o [A047080(n,k): k in [0..n], n in [0..12]]; // _G. C. Greubel_, Oct 30 2022
%o (SageMath)
%o f=factorial
%o 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))) )
%o 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))) )
%o def A(n,k): return p(n,k) - q(n,k)
%o def A047080(n,k): return A(n-k, k)
%o flatten([[A047080(n,k) for k in range(n+1)] for n in range(14)]) # _G. C. Greubel_, Oct 30 2022
%Y Cf. A047081, A047082, A047083, A047084, A047085, A047086, A047087, A047088.
%Y Cf. A001590, A022856, A028310, A078042, A089071, A091337, A171155.
%K nonn,tabl,easy
%O 0,8
%A _Clark Kimberling_
%E 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
|
