login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A171155 For two strings of length n, this is the number of pairwise alignments that do not have an insertion adjacent to a deletion. 4
1, 1, 3, 9, 27, 83, 259, 817, 2599, 8323, 26797, 86659, 281287, 915907, 2990383, 9786369, 32092959, 105435607, 346950321, 1143342603, 3772698725, 12463525229, 41218894577, 136451431723, 452116980643, 1499282161375, 4975631425581, 16524213199923, 54913514061867 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

This is the number of walks from (0,0) to (n,n) where unit horizontal (+1,0), vertical (0,+1), and diagonal (+1,+1) steps are permitted but a horizontal step cannot be followed by a vertical step, nor vice-versa.

a(n) is also the number of walks from (0,0) to (n,n) with steps that increment one or two coordinates and having the property that no two consecutive steps are orthogonal. - Lee A. Newberg, Dec 04 2009

a(n) is also the number of standard sequence alignments of two strings of length n, counting only those alignments with the property that, for every pair of consecutive alignment columns, there is at least one sequence that contributes a non-gap to both columns. That is, a(n) counts only those standard alignments with a column order that can be unambiguously reconstructed from the knowledge of all pairings, where a pairing is, e.g., that some i-th position of the first string is in the same column as some j-th position of the second string. - Lee A. Newberg, Dec 11 2009

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

FORMULA

G.f.: sqrt((1-x)/(1-3*x-x^2-x^3)). - Mark van Hoeij, May 10 2013

G.f.: Sum_{n>=0} (2*n)!/n!^2 * x^(2*n) / (1-2*x)^(3*n+1). - Paul D. Hanna, Sep 21 2013

EXAMPLE

For n = 3, the 9 alignments are:

ABC A-BC ABC- -ABC -ABC --ABC ABC- AB-C ABC--

DEF DEF- D-EF DEF- DE-F DEF-- -DEF -DEF --DEF

MAPLE

a:= proc(n) option remember; `if`(n<4, [1, 1, 3, 9][n+1],

      ((4*n-3)*a(n-1) -(2*n-5)*a(n-2) +a(n-3) -(n-3)*a(n-4))/n)

    end:

seq (a(n), n=0..30);  # Alois P. Heinz, Jan 22 2013

PROG

(PARI) x='x+O('x^66); Vec(sqrt((1-x)/(1-3*x-x^2-x^3))) \\ Joerg Arndt, May 11 2013

(PARI) {a(n)=polcoeff(sum(m=0, n, (2*m)!/m!^2 * x^(2*m) / (1-x+x*O(x^n))^(3*m+1)), n)} \\ Paul D. Hanna, Sep 21 2013

CROSSREFS

See A171158 for the number of such walks in three dimensions. - Lee A. Newberg, Dec 04 2009

See A171563 for the number of such walks in four dimensions. - Lee A. Newberg, Dec 11 2009

Sequence in context: A099786 A237272 A192909 * A131428 A099787 A176826

Adjacent sequences:  A171152 A171153 A171154 * A171156 A171157 A171158

KEYWORD

nonn,walk

AUTHOR

Lee A. Newberg, Dec 04 2009

EXTENSIONS

Extended beyond a(19) by Alois P. Heinz, Jan 22 2013

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 19 17:21 EDT 2014. Contains 240762 sequences.