login
For two strings of length n, this is the number of pairwise alignments that do not have an insertion adjacent to a deletion.
7

%I #62 Nov 20 2024 09:52:46

%S 1,1,3,9,27,83,259,817,2599,8323,26797,86659,281287,915907,2990383,

%T 9786369,32092959,105435607,346950321,1143342603,3772698725,

%U 12463525229,41218894577,136451431723,452116980643,1499282161375,4975631425581,16524213199923,54913514061867

%N For two strings of length n, this is the number of pairwise alignments that do not have an insertion adjacent to a deletion.

%C 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.

%C 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

%C 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

%C First differences of A108626: a(n) = A108626(n) - A108626(n-1) for n>=1. - _Thomas Baruchel_, Nov 08 2014

%C The number of walls of height one in all bargraphs of semiperimeter n>=2. A wall is a maximal sequence of adjacent up steps. - _Arnold Knopfmacher_, Nov 04 2016

%C Main diagonal of Table 2 in Covington. - _Peter Bala_, Jan 27 2018

%C From _Thierry Marchant_, Oct 30 2024: (Start)

%C a(n) is also the number of maximal antichains in the product of two chains of length n.

%C a(n) is also the number of strict chains in the product of two chains of length n (a strict chain P in a product of two chains is a chain such that x,y in P implies x_1 different from y_1 and x_2 different from y_2). (End)

%H Alois P. Heinz, <a href="/A171155/b171155.txt">Table of n, a(n) for n = 0..1000</a>

%H A. Blecher, C. Brennan and A. Knopfmacher, <a href="https://web.math.rochester.edu/misc/ojac/vol12/134.pdf">Walls in bargraphs</a>, preprint.

%H Denis Bouyssou, Thierry Marchant, and Marc Pirlot, <a href="https://arxiv.org/abs/2410.16243">About maximal antichains in a product of two chains:A catch-all note</a>, arXiv:2410.16243 [math.CO], 2024. See pp. 1, 3, 16-18.

%H Denis Bouyssou, Thierry Marchant, and Marc Pirlot, <a href="https://arxiv.org/abs/2410.18443">ELECTRE TRI-nB, pseudo-disjunctive: axiomatic and combinatorial results</a>, arXiv:2410.18443 [cs.DM], 2024. See p. 14.

%H M. A. Covington, <a href="https://doi.org/10.1080/0929617042000314921">The Number of Distinct Alignments of Two Strings</a>, Journal of Quantitative Linguistics, Vol.11 (2004), Issue3, pp. 173-182

%F a(n) = ((4*n-3)*a(n-1)-(2*n-5)*a(n-2)+a(n-3)-(n-3)*a(n-4))/n. - _Alois P. Heinz_, Jan 22 2013

%F G.f.: sqrt((1-x)/(1-3*x-x^2-x^3)). - _Mark van Hoeij_, May 10 2013

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

%F G.f.: Sum_{n>=0} x^n/(1-x)^n * Sum_{k=0..n} C(n,k)^2 * x^k. - _Paul D. Hanna_, Nov 08 2014

%e For n = 3, the 9 alignments are:

%e ABC A-BC ABC- -ABC -ABC --ABC ABC- AB-C ABC--

%e DEF DEF- D-EF DEF- DE-F DEF-- -DEF -DEF --DEF

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

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

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 22 2013

%t CoefficientList[Series[Sqrt[(1 - x) / (1 - 3 x - x^2 - x^3)], {x, 0, 40}], x] (* _Vincenzo Librandi_, Nov 09 2014 *)

%o (PARI) my(x='x+O('x^66)); Vec(sqrt((1-x)/(1-3*x-x^2-x^3))) \\ _Joerg Arndt_, May 11 2013

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

%o (PARI) {a(n)=polcoeff( sum(m=0,n, x^m * sum(k=0,m, binomial(m,k)^2 * x^k) / (1-x +x*O(x^n))^m) ,n)}

%o for(n=0,30,print1(a(n),", ")) \\ _Paul D. Hanna_, Nov 08 2014

%o (PARI) a(n)=sum(k=0, n, sum(i=0, k, binomial(n-k, i)^2*binomial(n-i, k-i)))-sum(k=0, n-1, sum(i=0, k, binomial(n-k-1, i)^2*binomial(n-i-1, k-i))) \\ _Thomas Baruchel_, Nov 09 2014

%Y See A171158 for the number of such walks in three dimensions. - _Lee A. Newberg_, Dec 04 2009

%Y See A171563 for the number of such walks in four dimensions. - _Lee A. Newberg_, Dec 11 2009

%Y Cf. A108626.

%Y Main diagonal of A180091.

%K nonn,walk

%O 0,3

%A _Lee A. Newberg_, Dec 04 2009

%E Extended beyond a(19) by _Alois P. Heinz_, Jan 22 2013