login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 9
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 (list; table; graph; refs; listen; history; text; internal format)
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, 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) appears to be A171155(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;

  ...

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 *)

CROSSREFS

Cf. 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 28 16:37 EDT 2022. Contains 354119 sequences. (Running on oeis4.)