login
Number of effective multiple alignments of three equal-length sequences.
6

%I #57 Mar 17 2023 10:58:17

%S 1,5,67,1109,20251,391355,7847155,161476565,3387271675,72114452255,

%T 1553475100717,33786532319435,740681494769659,16346552430326123,

%U 362830907979309067,8093356178498583509,181311959402343288955,4077310062938894133623,91999289732199733092601

%N Number of effective multiple alignments of three equal-length sequences.

%C This counts effective alignments rather than standard alignments, so that for example the following two alignments are equivalent:

%C -A A-

%C -T T-

%C C- -C

%C See Dress, Morgenstern and Stoye for more information.

%H Robert Israel, <a href="/A124435/b124435.txt">Table of n, a(n) for n = 0..720</a>

%H A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, <a href="http://arxiv.org/abs/1507.03227">Diagonals of rational functions and selected differential Galois groups</a>, arXiv preprint arXiv:1507.03227 [math-ph], 2015.

%H A. Dress, B. Morgenstern and J. Stoye, <a href="http://dx.doi.org/10.1016/S0893-9659(98)00054-8">On the number of standard and of effective multiple alignments</a>, Applied Mathematics Letters, Vol. 11, No. 4, 1998, pp. 43-49.

%H Jacques-Arthur Weil, <a href="http://www.unilim.fr/pages_perso/jacques-arthur.weil/diagonals/">Supplementary Material for the Paper "Diagonals of rational functions and selected differential Galois groups"</a>

%F The recurrence is three-dimensional with the order of the three parameters immaterial. That is, a(i,j,k)=a(i,k,j)=a(j,i,k)=a(j,k,i)=a(k,i,j)=a(k,j,i). a(i, j, 0) = (i+j)! / i! / j! a(i, j, k) = a(i-1,j,k) + a(i,j-1,k) + a(i,j,k-1) - a(i-1,j-1,k-1).

%F a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*binomial(n+2*k,n)*binomial(2*k,k). - _Wadim Zudilin_, Nov 26 2015

%F Diagonal of 1/(1 - x - y - z + x*y*z). - _Mark van Hoeij_, Dec 20 2013

%F G.f.: hypergeom([1/3, 2/3],[1],27*x/(1+x)^3)/(1+x). - _Mark van Hoeij_, Dec 20 2013

%F (3*n-1)*(n+1)^2*a(n+1)-(3*n+1)*(24*n^2+8*n-5)*a(n)+(9*n^3-3*n^2-4*n+2)*a(n-1)+(3*n+2)*(n-1)^2*a(n-2)=0. - _Robert Israel_, Nov 26 2015

%F 0 = (2*x-1)*(x^3+3*x^2-24*x+1)*x*y'' + (6*x^4+8*x^3-57*x^2+48*x-1)*y' + (x+1)*(2*x^2-2*x+5)*y, where y is g.f. - _Gheorghe Coserea_, Jul 06 2016

%F From _Peter Bala_, Mar 16 2023: (Start)

%F (3*n - 4)*n^2*a(n) = (3*n - 2)*(24*n^2 - 40*n + 11)*a(n-1) - (9*n^3 - 30*n^2 + 29*n - 6)*a(n-2) - (3*n - 1)*(n - 2)^2*a(n-3) with a(0) = 1, a(1) = 5 and a(2) = 67.

%F Conjecture: the supercongruence a(n*p^r) == a(n*p^(r-1)) (mod p^(2*r)) holds for positive integers n and r and all primes p >= 5. (End)

%e a(1) = 5 because the five alignments are

%e A-- A- A- A- A

%e -C- C- -C -C C

%e --T -T T- -T T

%p G := series( hypergeom([1/3, 2/3],[1],27*x/(1+x)^3)/(1+x), x=0, 31);

%p seq(coeff(G,x,i),i=0..30); # _Mark van Hoeij_, Dec 20 2013

%t a[n_] := Sum[(-1)^(n-k) Binomial[n, k] Binomial[n+2k, n] Binomial[2k, k], {k, 0, n}];

%t Table[a[n], {n, 0, 18}] (* _Jean-François Alcover_, Sep 18 2018, after _Wadim Zudilin_ *)

%o (PARI)

%o diag(expr, N=22, var=variables(expr)) = {

%o my(a = vector(N));

%o for (k = 1, #var, expr = taylor(expr, var[#var - k + 1], N));

%o for (n = 1, N, a[n] = expr;

%o for (k = 1, #var, a[n] = polcoef(a[n], n-1)));

%o return(a);

%o };

%o x='x; y='y; z='z; diag(1/(1 - x - y - z + x*y*z), 19)

%o (PARI) \\ system("wget http://www.jjj.de/pari/hypergeom.gpi");

%o read("hypergeom.gpi");

%o N = 20; x = 'x + O('x^N);

%o Vec(hypergeom([1/3, 2/3],[1],27*x/(1+x)^3, N)/(1+x)) \\ _Gheorghe Coserea_, Jul 06 2016

%Y Cf. A268545 - A268555, A000172, A318108, A318109.

%K nonn,easy

%O 0,2

%A _Lee A. Newberg_, Dec 15 2006

%E More terms from _Mark van Hoeij_, Dec 21 2013