login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A124435 Number of effective multiple alignments of three equal-length sequences. 2
1, 5, 67, 1109, 20251, 391355, 7847155, 161476565, 3387271675, 72114452255, 1553475100717, 33786532319435, 740681494769659, 16346552430326123, 362830907979309067, 8093356178498583509, 181311959402343288955, 4077310062938894133623, 91999289732199733092601 (list; graph; refs; listen; history; text; internal format)
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, 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

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.

Sequence in context: A212731 A316146 A113265 * A123034 A166619 A323208

Adjacent sequences:  A124432 A124433 A124434 * A124436 A124437 A124438

KEYWORD

nonn

AUTHOR

Lee A. Newberg, Dec 15 2006

EXTENSIONS

More terms from Mark van Hoeij, Dec 21 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 13 20:38 EDT 2019. Contains 327981 sequences. (Running on oeis4.)