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.
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
KEYWORD
nonn,easy
AUTHOR
Lee A. Newberg, Dec 15 2006
EXTENSIONS
More terms from Mark van Hoeij, Dec 21 2013
STATUS
approved