|
| |
|
|
A299041
|
|
Irregular table: T(n,k) equals the number of alignments of length k of n strings each of length 3.
|
|
5
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
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).
|
|
|
LINKS
|
|
|
|
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.
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
