cp's OEIS Frontend

A299041 Irregular table: T(n,k) equals the number of alignments of length k of n strings each of length 3.

%I A299041 #12 Jun 05 2019 09:59:43
%S A299041 1,1,12,30,20,1,60,690,2940,5670,5040,1680,1,252,8730,103820,581700,
%T A299041 1767360,3087000,3099600,1663200,369600,1,1020,94890,2615340,32186070,
%U A299041 214628400,859992000,2189325600,3628409400,3903900000,2630628000,1009008000,168168000,1,4092,979530,58061420,1411122300
%N A299041 Irregular table: T(n,k) equals the number of alignments of length k of n strings each of length 3.
%C A299041 An alignment of n strings of various lengths is a way of inserting blank characters into the n strings so that the resulting strings all have the same length. We don't allow insertion of a blank character into the same position in each of the n strings.
%C A299041 In this case, let s_1,...,s_n be n strings each of length 3 over an alphabet A. Let - be a gap symbol not in A and let A' = union of A and {-}. An alignment of the n strings is an n-tuple (s_1',...,s_n') of strings each of length >= 3 over the alphabet A' such that
%C A299041 (a) the strings s_i', 1 <= i <= n, have the same length. This common length is called the length of the alignment.
%C A299041 (b) deleting the gap symbols from s_i' yields the string s_i for 1 <= i <= n
%C A299041 (c) there is no value j such that all the strings s_i', 1 <= i <= n have a gap symbol at position j.
%C A299041 By writing the strings s_i' one under another we can consider an alignment of n strings as an n X L matrix, where L, the length of the alignment, ranges from a minimum value of 3 to a maximum value of 3*n. Each row of the matrix has 3 characters from the alphabet A and (L - 3) gap characters.
%C A299041 For example,
%C A299041   s_1' = ABC------
%C A299041   s_2' = ---DEF---
%C A299041   s_3' = ------GHI
%C A299041 is an alignment (of maximum length L = 9) of three strings s_1 = ABC, s_2 = DEF and s_3 = GHI each of length 3.
%C A299041 For the number of alignments of length k of n strings of length 1 (resp. 2) see A131689 (resp. A122193).
%H A299041 P. Bala, <a href="/A299041/a299041.pdf">Notes on A299041</a>
%H A299041 M. Dukes, C. D. White, <a href="http://arxiv.org/abs/1603.01589">Web Matrices: Structural Properties and Generating Combinatorial Identities</a>, arXiv:1603.01589 [math.CO], 2016.
%H A299041 J. Engbers and C. Stocker, <a href="http://math.colgate.edu/~integers/vol16.html ">Two Combinatorial Proofs of Identities Involving Sums of Powers of Binomial Coefficients</a>, Integers 16 (2016), #A58.
%H A299041 J. B. Slowinski, <a href="http://www.neurociencias.org.ve/cont-cursos-laboratorio-de-neurociencias-luz/Slowinski1998%20phylogenetics.pdf">The Number of Multiple Alignments</a>, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:<a href="http://dx.doi.org/10.1006/mpev.1998.0522">10.1006/mpev.1998.0522</a>
%F A299041 T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*binomial(i,3)^n.
%F A299041 T(n,3) = 1; T(n,3*n) = (3*n)!/6^n = A014606(n)
%F A299041 T(n,k) = binomial(k,3)*( T(n-1,k) + 3*T(n-1,k-1) + 3*T(n-1,k-2) + T(n-1,k-3) ) for 3 <= k <= 3*n with boundary conditions T(n,3) = 1 for n >= 1 and T(n,k) = 0 if (k < 3) or (k > 3*n).
%F A299041 Double e.g.f.: exp(-x)*Sum_{n >= 0} exp(binomial(n,3)*y)*x^n/n! = 1 + (x^3/3!)*y + (x^3/3! + 12*x^4/4! + 30*x^5/5! + 20*x^6/6!)*y^2/2! + ....
%F A299041 n-th row polynomial R(n,x) = Sum_{i >= 3} binomial(i,3)^n*x^i/(1 + x)^(i+1) for n >= 1.
%F A299041 1/(1 - x)*R(n,x/(1 - x)) = Sum_{i >= 3} binomial(i,3)^n*x^i for n >= 1.
%F A299041 R(n,x) = x^3 o x^3 o ... o x^3 (n factors), where o is the black diamond product of power series defined in Dukes and White.
%F A299041 R(n,x) = coefficient of (z_1)^3*...*(z_n)^3 in the expansion of the rational function 1/(1 + x - x*(1 + z_1)*...*(1 + z_n)).
%F A299041 The polynomials Sum_{k = 3..3*n} T(n,k)*x^(k-3)*(1 - x)^(3*n-k) are the row polynomials of A174266.
%F A299041 Sum_{i = 3..n-1} binomial(i,3)^m = Sum_{k = 3..3*m} T(m,k)*binomial(n,k+1) for m >= 1. See Examples below.
%F A299041 x^3*R(n,-1 - x) = (-1)^n*(1 + x)^3*R(n,x).
%F A299041 R(n+1,x) = 1/3!*x^3*(d/dx)^3 ((1 + x)^3*R(n,x)) for n >= 1.
%F A299041 The zeros of R(n,x) belong to the interval [-1, 0].
%F A299041 Row sums R(n,1) = A062208(n); alternating row sums R(n,-1) = (-1)^n.
%F A299041 For k a nonzero integer, the power series A(k,x) := exp( Sum_{n >= 1} 1/k^3*R(n,k)*x^n/n ) appear to have integer coefficients. See the Example section.
%F A299041 Sum_{k = 3..3*n} T(n,k)*binomial(x,k) = ( binomial(x,3) )^n. Equivalently, Sum_{k = 3..3*n} (-1)^(n+k)*T(n,k)*binomial(x+k,k) = ( binomial(x+3,3) )^n. Cf. the Worpitzky-type identity Sum_{k = 1..n} A019538(n,k)* binomial(x,k) = x^n.
%F A299041 Sum_{k = 3..3*n} T(n,k)*binomial(x,k-3) = -binomial(x,3)^n + 3*binomial(x+1,3)^n - 3*binomial(x+2,3)^n + binomial(x+3,3)^n. These polynomials have their zeros on the vertical line Re x = -1/2 in the complex plane.
%e A299041 Table begins
%e A299041 n\k| 3   4     5       6      7      8        9      10
%e A299041 - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%e A299041   1| 1
%e A299041   2| 1  12    30      20
%e A299041   3| 1  60   690    2940   5670    5040    1680
%e A299041   4| 1 252  8730  103820 581700 1767360 3087000 3099600 ...
%e A299041 ...
%e A299041 T(2,5) = 30: An alignment of length 5 will have two gap symbols on each line. There are C(5,2) = 10 ways of choosing the 2 positions to insert the gap symbols in the first string. The second string in the alignment must then have nongap symbols at these two positions leaving three positions in which to insert the remaining 1 nongap symbol, giving in total 10 x 3 = 30 possible alignments of 2 strings of 3 characters. Some examples are
%e A299041   ABC--   ABC--   ABC--
%e A299041   D--EF   -D-EF   --DEF
%e A299041 Row 2: Sum_{i = 3..n-1} C(i,3)^2 = C(n,4) + 12*C(n,5) + 30*C(n,6) + 20*C(n,7).
%e A299041 Row 3: Sum_{i = 3..n-1} C(i,3)^3 = C(n,4) + 60*C(n,5) + 690*C(n,6) + 2940*C(n,7) + 5670*C(n,8)+ 5040*C(n,9)+ 1680*C(n,10).
%e A299041 exp( Sum_{n >= 1} R(n,2)*x^n/n ) = (1 + x + 153*x^2 + 128793*x^3 + 319155321*x^4 + 1744213657689*x^5 + ....)^8
%e A299041 exp( Sum_{n >= 1} R(n,3)*x^n/n ) = (1 + x + 424*x^2 + 998584*x^3 + 6925040260*x^4 + 105920615923684*x^5 + ....)^27.
%p A299041 seq(seq(add( (-1)^(k-i) *binomial(k,i)*binomial(i,3)^n, i = 0..k ), k = 3..3*n), n = 1..6);
%t A299041 nmax = 6; T[n_, k_] := Sum[(-1)^(k-i) Binomial[k, i] Binomial[i, 3]^n, {i, 0, k}]; Table[T[n, k], {n, 1, nmax}, {k, 3, 3n}] // Flatten (* _Jean-François Alcover_, Feb 20 2018 *)
%Y A299041 Row sums A062208. Cf. A014606, A019538, A078741, A087127, A122193, A131689, A174266.
%Y A299041 Cf. A086020, A086021, A086022.
%K A299041 nonn,tabf,easy
%O A299041 1,3
%A A299041 _Peter Bala_, Feb 02 2018