A124435 Number of effective multiple alignments of three equal-length sequences.

1, 5, 67, 1109, 20251, 391355, 7847155, 161476565, 3387271675, 72114452255, 1553475100717, 33786532319435, 740681494769659, 16346552430326123, 362830907979309067, 8093356178498583509, 181311959402343288955, 4077310062938894133623, 91999289732199733092601

Offset

0,2

Comments

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

-A A-

-T T-

C- -C

See Dress, Morgenstern and Stoye for more information.

Links

Robert Israel, Table of n, a(n) for n = 0..720

A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, Diagonals of rational functions and selected differential Galois groups, arXiv preprint arXiv:1507.03227 [math-ph], 2015.

A. Dress, B. Morgenstern and J. Stoye, On the number of standard and of effective multiple alignments, Applied Mathematics Letters, Vol. 11, No. 4, 1998, pp. 43-49.

Jacques-Arthur Weil, Supplementary Material for the Paper "Diagonals of rational functions and selected differential Galois groups"

Formula

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

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

Diagonal of 1/(1 - x - y - z + x*y*z). - Mark van Hoeij, Dec 20 2013

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

(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

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

From Peter Bala, Mar 16 2023: (Start)

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

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)

Example

a(1) = 5 because the five alignments are
  A--   A-   A-   A-   A
  -C-   C-   -C   -C   C
  --T   -T   T-   -T   T

Maple

G := series( hypergeom([1/3, 2/3], [1], 27*x/(1+x)^3)/(1+x), x=0, 31);
seq(coeff(G, x, i), i=0..30);  # Mark van Hoeij, Dec 20 2013

Mathematica

a[n_] := Sum[(-1)^(n-k) Binomial[n, k] Binomial[n+2k, n] Binomial[2k, k], {k, 0, n}];
Table[a[n], {n, 0, 18}] (* Jean-François Alcover, Sep 18 2018, after Wadim Zudilin *)

Prog

(PARI)
diag(expr, N=22, var=variables(expr)) = {
  my(a = vector(N));
  for (k = 1, #var, expr = taylor(expr, var[#var - k + 1], N));
  for (n = 1, N, a[n] = expr;
    for (k = 1, #var, a[n] = polcoef(a[n], n-1)));
  return(a);
};
x='x; y='y; z='z; diag(1/(1 - x - y - z + x*y*z), 19)
(PARI) \\ system("wget http://www.jjj.de/pari/hypergeom.gpi");
read("hypergeom.gpi");
N = 20; x = 'x + O('x^N);
Vec(hypergeom([1/3, 2/3], [1], 27*x/(1+x)^3, N)/(1+x)) \\ Gheorghe Coserea, Jul 06 2016

Crossrefs

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

Sequence in context: A212731 A316146 A113265 * A123034 A166619 A323208

Adjacent sequences: A124432 A124433 A124434 * A124436 A124437 A124438

Keyword

nonn,easy

Author

Lee A. Newberg, Dec 15 2006

Extensions

More terms from Mark van Hoeij, Dec 21 2013

Status

approved