|
%I #26 Mar 23 2016 04:57:43
%S 1,1,48639,75494983297,1177359342144641535,
%T 103746115308050354021387521,36585008462723983824862891403150079,
%U 41020870889694863957061607086939138327565057,124069835911824710311393852646151897334844371419287295
%N Number of alignments of n strings of length 7.
%C 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.
%C 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
%C 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
%D M. S. Waterman, Introduction to Computational Biology: Maps, Sequences and Genomes, 1995.
%H Alois P. Heinz, <a href="/A062204/b062204.txt">Table of n, a(n) for n = 0..50</a>
%H M. A. Covington, <a href="http://www.covingtoninnovations.com/mc/number.pdf">The number of distinct alignments of two strings</a>, Journal of Quantitative Linguistics, Volume 11, no. 3 (2004), 173-182.
%H Michael S. Waterman, <a href="http://dornsife.usc.edu/labs/msw/">Home Page</a> (contains copies of his papers)
%F A(n, y) = sum(k=0,n*y, sum(t=0,k, (-1)^t * binomial(k,t) * binomial(k-t,y)^n )).
%F 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
%e 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.
%t 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 *)
%Y Cf. A062205, A062208, A001850. A(2, X) represents Waterman's f function.
%Y Row n=7 of A262809.
%K nonn
%O 0,3
%A _Angelo Dalli_, Jun 13 2001
%E Formula and sequence revised by _Max Alekseyev_, Mar 12 2009
| 