A062204 Number of alignments of n strings of length 7.

1, 1, 48639, 75494983297, 1177359342144641535, 103746115308050354021387521, 36585008462723983824862891403150079, 41020870889694863957061607086939138327565057, 124069835911824710311393852646151897334844371419287295

Offset: 0

Author

Angelo Dalli, Jun 13 2001

Keywords

• nonn

Comments

Strings of length 7 represent the average word length for most natural languages such as English. This sequence represents the search space for alignment and sequencing algorithms that work on multiple sets of strings.

The assertion that "strings of length 7 represent the average word length for most natural languages such as English" seems to conflict with studies that show that the average word length in English is about 4.5 letters and the average word length in modern Russian is 5.28 letters. - M. F. Hasler, Mar 12 2009

In general, row r > 0 of A262809 is asymptotic to sqrt(r*Pi) * (r^(r-1)/(r-1)!)^n * n^(r*n+1/2) / (2^(r/2) * exp(r*n) * (log(2))^(r*n+1)). - Vaclav Kotesovec, Mar 23 2016

Examples

			A(2, 7) = 48639 since this represents the number of distinct alignments of 2 strings of length 7. All values in A(2,X) can be cross-validated against the Delannoy sequence D(X,X) A001850.
		

References

• M. S. Waterman, Introduction to Computational Biology: Maps, Sequences and Genomes, 1995.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..50
• M. A. Covington, The number of distinct alignments of two strings, Journal of Quantitative Linguistics, Volume 11, no. 3 (2004), 173-182.
• Michael S. Waterman, Home Page (contains copies of his papers)

Crossrefs

Cf. A062205, A062208, A001850. A(2, X) represents Waterman's f function.

Row n=7 of A262809.

Programs

Mathematica

With[{r = 7}, Flatten[{1, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, r]^k, {i, 0, j}], {j, 0, k*r}], {k, 1, 10}]}]] (* Vaclav Kotesovec, Mar 22 2016 *)

Formula

A(n, y) = sum(k=0,n*y, sum(t=0,k, (-1)^t * binomial(k,t) * binomial(k-t,y)^n )).

a(n) ~ sqrt(7*Pi) * (7^6/6!)^n * n^(7*n+1/2) / (2^(7/2) * exp(7*n) * (log(2))^(7*n+1)). - Vaclav Kotesovec, Mar 23 2016

Extensions

Formula and sequence revised by Max Alekseyev, Mar 12 2009