login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A062204 Number of alignments of n strings of length 7. 4
1, 1, 48639, 75494983297, 1177359342144641535, 103746115308050354021387521, 36585008462723983824862891403150079, 41020870889694863957061607086939138327565057, 124069835911824710311393852646151897334844371419287295 (list; graph; refs; listen; history; text; 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

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

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)

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

EXAMPLE

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.

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

CROSSREFS

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

Row n=7 of A262809.

Sequence in context: A244172 A245794 A048341 * A173780 A252444 A237146

Adjacent sequences:  A062201 A062202 A062203 * A062205 A062206 A062207

KEYWORD

nonn

AUTHOR

Angelo Dalli, Jun 13 2001

EXTENSIONS

Formula and sequence revised by Max Alekseyev, Mar 12 2009

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 24 00:29 EDT 2017. Contains 291052 sequences.