login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..40.

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

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

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

Cf. A086020, A086021, A086022.

Sequence in context: A049725 A183723 A247152 * A334989 A331367 A335149

Adjacent sequences:  A299038 A299039 A299040 * A299042 A299043 A299044

KEYWORD

nonn,tabf,easy

AUTHOR

Peter Bala, Feb 02 2018

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 April 11 16:42 EDT 2021. Contains 342888 sequences. (Running on oeis4.)