|
| |
|
|
A062204
|
|
Number of alignments of n strings of length 7.
|
|
2
| |
|
|
1, 1, 48639, 75494983297, 1177359342144641535, 103746115308050354021387521, 36585008462723983824862891403150079, 41020870889694863957061607086939138327565057, 124069835911824710311393852646151897334844371419287295
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
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
|
|
|
REFERENCES
| M. S. Waterman, Introduction to Computational Biology: Maps, Sequences and Genomes, 1995.
|
|
|
LINKS
| M. A. Covington, The number of distinct alignments of two strings, Journal of Quantitative Linguistics, Volume 11, no. 3 (2004), 173-182. [Link corrected by Ray Chandler, Mar 12 2009]
Michael S. Waterman, Home Page (contains copies of his papers) [Link corrected by R. J. Mathar, Mar 11, 2009]
|
|
|
FORMULA
| A(n, y) = sum(k=0,n*y, sum(t=0,k, (-1)^t * binomial(k,t) * binomial(k-t,y)^n ))
|
|
|
EXAMPLE
| A(2, 7) = 48639 since this represents the number of unique 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.
|
|
|
CROSSREFS
| Cf. A062205, A062208, A001850. A(2, X) represents Waterman's f function.
Sequence in context: A172613 A172554 A048341 * A173780 A067869 A175278
Adjacent sequences: A062201 A062202 A062203 * A062205 A062206 A062207
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Angelo Dalli (adal002(AT)um.edu.mt) [broken email address], Jun 13 2001
|
|
|
EXTENSIONS
| Formula and sequence revised by Max Alekseyev, Mar 12 2009
|
| |
|
|
