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

Author

Lee A. Newberg, Dec 15 2006

Keywords

• nonn
• easy

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.

Examples

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

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"

Crossrefs

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

Programs

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

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

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)

Extensions

More terms from Mark van Hoeij, Dec 21 2013