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

1, 1, 12, 30, 20, 1, 60, 690, 2940, 5670, 5040, 1680, 1, 252, 8730, 103820, 581700, 1767360, 3087000, 3099600, 1663200, 369600, 1, 1020, 94890, 2615340, 32186070, 214628400, 859992000, 2189325600, 3628409400, 3903900000, 2630628000, 1009008000, 168168000, 1, 4092, 979530, 58061420, 1411122300

Offset: 1

Author

Peter Bala, Feb 02 2018

Keywords

• nonn
• tabf
• easy

Comments

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.

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

(a) the strings s_i', 1 <= i <= n, have the same length. This common length is called the length of the alignment.

(b) deleting the gap symbols from s_i' yields the string s_i for 1 <= i <= n

(c) there is no value j such that all the strings s_i', 1 <= i <= n have a gap symbol at position j.

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.

For example,

s_1' = ABC------

s_2' = ---DEF---

s_3' = ------GHI

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.

For the number of alignments of length k of n strings of length 1 (resp. 2) see A131689 (resp. A122193).

Examples

			Table begins
n\k| 3   4     5       6      7      8        9      10
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
  1| 1
  2| 1  12    30      20
  3| 1  60   690    2940   5670    5040    1680
  4| 1 252  8730  103820 581700 1767360 3087000 3099600 ...
...
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
  ABC--   ABC--   ABC--
  D--EF   -D-EF   --DEF
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).
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).
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
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.
		

Links

• P. Bala, Notes on A299041
• M. Dukes, C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.
• J. Engbers and C. Stocker, Two Combinatorial Proofs of Identities Involving Sums of Powers of Binomial Coefficients, Integers 16 (2016), #A58.
• J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Crossrefs

Row sums A062208. Cf. A014606, A019538, A078741, A087127, A122193, A131689, A174266.

Cf. A086020, A086021, A086022.

Programs

Maple

seq(seq(add( (-1)^(k-i) *binomial(k,i)*binomial(i,3)^n, i = 0..k ), k = 3..3*n), n = 1..6);

Mathematica

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

Formula

T(n,k) = Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*binomial(i,3)^n.

T(n,3) = 1; T(n,3*n) = (3*n)!/6^n = A014606(n)

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

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! + ....

n-th row polynomial R(n,x) = Sum_{i >= 3} binomial(i,3)^n*x^i/(1 + x)^(i+1) for n >= 1.

1/(1 - x)*R(n,x/(1 - x)) = Sum_{i >= 3} binomial(i,3)^n*x^i for n >= 1.

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.

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

The polynomials Sum_{k = 3..3*n} T(n,k)*x^(k-3)*(1 - x)^(3*n-k) are the row polynomials of A174266.

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.

x^3*R(n,-1 - x) = (-1)^n*(1 + x)^3*R(n,x).

R(n+1,x) = 1/3!*x^3*(d/dx)^3 ((1 + x)^3*R(n,x)) for n >= 1.

The zeros of R(n,x) belong to the interval [-1, 0].

Row sums R(n,1) = A062208(n); alternating row sums R(n,-1) = (-1)^n.

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.

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.

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.