cp's OEIS Frontend

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

%I A171155 #62 Nov 20 2024 09:52:46
%S A171155 1,1,3,9,27,83,259,817,2599,8323,26797,86659,281287,915907,2990383,
%T A171155 9786369,32092959,105435607,346950321,1143342603,3772698725,
%U A171155 12463525229,41218894577,136451431723,452116980643,1499282161375,4975631425581,16524213199923,54913514061867
%N A171155 For two strings of length n, this is the number of pairwise alignments that do not have an insertion adjacent to a deletion.
%C A171155 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 A171155 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 A171155 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 A171155 First differences of A108626: a(n) = A108626(n) - A108626(n-1) for n>=1. - _Thomas Baruchel_, Nov 08 2014
%C A171155 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 A171155 Main diagonal of Table 2 in Covington. - _Peter Bala_, Jan 27 2018
%C A171155 From _Thierry Marchant_, Oct 30 2024: (Start)
%C A171155 a(n) is also the number of maximal antichains in the product of two chains of length n.
%C A171155 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 A171155 Alois P. Heinz, <a href="/A171155/b171155.txt">Table of n, a(n) for n = 0..1000</a>
%H A171155 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 A171155 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 A171155 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 A171155 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 A171155 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 A171155 G.f.: sqrt((1-x)/(1-3*x-x^2-x^3)). - _Mark van Hoeij_, May 10 2013
%F A171155 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 A171155 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 A171155 For n = 3, the 9 alignments are:
%e A171155 ABC A-BC ABC- -ABC -ABC --ABC ABC- AB-C ABC--
%e A171155 DEF DEF- D-EF DEF- DE-F DEF-- -DEF -DEF --DEF
%p A171155 a:= proc(n) option remember; `if`(n<4, [1, 1, 3, 9][n+1],
%p A171155       ((4*n-3)*a(n-1) -(2*n-5)*a(n-2) +a(n-3) -(n-3)*a(n-4))/n)
%p A171155     end:
%p A171155 seq(a(n), n=0..30);  # _Alois P. Heinz_, Jan 22 2013
%t A171155 CoefficientList[Series[Sqrt[(1 - x) / (1 - 3 x - x^2 - x^3)], {x, 0, 40}], x] (* _Vincenzo Librandi_, Nov 09 2014 *)
%o A171155 (PARI) my(x='x+O('x^66)); Vec(sqrt((1-x)/(1-3*x-x^2-x^3))) \\ _Joerg Arndt_, May 11 2013
%o A171155 (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 A171155 (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 A171155 for(n=0,30,print1(a(n),", ")) \\ _Paul D. Hanna_, Nov 08 2014
%o A171155 (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 A171155 See A171158 for the number of such walks in three dimensions. - _Lee A. Newberg_, Dec 04 2009
%Y A171155 See A171563 for the number of such walks in four dimensions. - _Lee A. Newberg_, Dec 11 2009
%Y A171155 Cf. A108626.
%Y A171155 Main diagonal of A180091.
%K A171155 nonn,walk
%O A171155 0,3
%A A171155 _Lee A. Newberg_, Dec 04 2009
%E A171155 Extended beyond a(19) by _Alois P. Heinz_, Jan 22 2013