A062205 -id:A062205 - cp's OEIS frontend

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 13, 13, 1, 1, 1, 75, 409, 63, 1, 1, 1, 541, 23917, 16081, 321, 1, 1, 1, 4683, 2244361, 10681263, 699121, 1683, 1, 1, 1, 47293, 308682013, 14638956721, 5552351121, 32193253, 8989, 1, 1, 1, 545835, 58514835289, 35941784497263, 117029959485121, 3147728203035, 1538743249, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 02 2015

Also, A(n,k) is the number of alignments for k sequences of length n each (Slowinski 1998).
Row r > 0 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)), or equivalently to sqrt(r) * (r^(r-1)/(r-1)!)^n * (n!)^r / (2^r * (Pi*n)^((r-1)/2) * (log(2))^(r*n+1)). - Vaclav Kotesovec, Mar 23 2016
From Vaclav Kotesovec, Mar 23 2016: (Start)
Column k > 0 is asymptotic to sqrt(c(k)) * d(k)^n / (Pi*n)^((k-1)/2), where c(k) and d(k) are roots of polynomial equations of degree k, independent on n.
---------------------------------------------------
k               d(k)
---------------------------------------------------
2              5.8284271247461900976033774484193...
3             56.9476283720414911685286267804411...
4            780.2794068067951456595241495989622...
5          13755.2719024115081712083954421541320...
6         296476.9162644200814909862281498491264...
7        7553550.6198338218721069097516499501996...
8      222082591.6017202421029000117685530884167...
9     7400694480.0494436216324852038000444393262...
10  275651917450.6709238286995776605620357737005...
---------------------------------------------------
d(k) is a root of polynomial:
---------------------------------------------------
k=2, 1 - 6*d + d^2
k=3, -1 + 3*d - 57*d^2 + d^3
k=4, 1 - 12*d - 218*d^2 - 780*d^3 + d^4
k=5, -1 + 5*d - 1260*d^2 - 3740*d^3 - 13755*d^4 + d^5
k=6, 1 - 18*d - 5397*d^2 - 123696*d^3 + 321303*d^4 - 296478*d^5 + d^6
k=7, -1 + 7*d - 24031*d^2 - 374521*d^3 - 24850385*d^4 + 17978709*d^5 - 7553553*d^6 + d^7
k=8, 1 - 24*d - 102692*d^2 - 9298344*d^3 + 536208070*d^4 - 7106080680*d^5 - 1688209700*d^6 - 222082584*d^7 + d^8
(End)
d(k) = (2^(1/k) - 1)^(-k). - David Bevan, Apr 07 2022
d(k) is asymptotic to (k/log(2))^k/sqrt(2). - David Bevan, Apr 07 2022
A(n,k) is the number of binary matrices with k columns and any number of nonzero rows with n ones in every column. - Andrew Howroyd, Jan 23 2020

			A(2,2) = 13: [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,0)], [(2,2),(1,2),(1,1),(1,0),(0,0)], [(2,2),(2,1),(1,1),(0,1),(0,0)], [(2,2),(2,1),(1,1),(0,0)], [(2,2),(2,1),(1,1),(1,0),(0,0)], [(2,2),(2,1),(2,0),(0,1),(0,0)], [(2,2),(2,1),(1,0),(0,0)], [(2,2),(1,1),(0,1),(0,0)], [(2,2),(1,1),(0,0)], [(2,2),(1,1),(1,0),(0,0)].
Square array A(n,k) begins:
  1, 1,    1,        1,             1,                   1, ...
  1, 1,    3,       13,            75,                 541, ...
  1, 1,   13,      409,         23917,             2244361, ...
  1, 1,   63,    16081,      10681263,         14638956721, ...
  1, 1,  321,   699121,    5552351121,     117029959485121, ...
  1, 1, 1683, 32193253, 3147728203035, 1050740615666453461, ...

Alois P. Heinz, Antidiagonals n = 0..48, flattened
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Columns: A000012 (k=0 and k=1), A001850 (k=2), A126086 (k=3), A263064 (k=4), A263065 (k=5), A263066 (k=6), A263067 (k=7), A263068 (k=8), A263069 (k=9), A263070 (k=10).
Rows: A000012 (n=0), A000670 (n=1), A055203 (n=2), A062208 (n=3), A062205 (n=4), A263061 (n=5), A263062 (n=6), A062204 (n=7), A263063 (n=8), A263071 (n=9), A263072 (n=10).
Main diagonal: A262810.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A263159, A316674.
Cf. A188392, A330942, A331461, A331637.

A:= (n, k)-> add(add((-1)^i*binomial(j, i)*
     binomial(j-i, n)^k, i=0..j), j=0..k*n):
seq(seq(A(n, d-n), n=0..d), d=0..10);

A[, 0] =  1; A[n, k_] := Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, n]^k, {i, 0, j}], {j, 0, k*n}];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jul 22 2016, after Alois P. Heinz *)

T(n,k) = {my(m=n*k); sum(j=0, m, binomial(j,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

A(n,k) = Sum_{j=0..k*n} Sum_{i=0..j} (-1)^i*C(j,i)*C(j-i,n)^k.
A(n,k) = Sum_{i >= 0} binomial(i,n)^k/2^(i+1). - Peter Bala, Jan 30 2018
A(n,k) = Sum_{j=0..n*k} binomial(j,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020

A062208 a(n) = Sum_{m>=0} binomial(m,3)^n*2^(-m-1).

Original entry on oeis.org

1, 1, 63, 16081, 10681263, 14638956721, 35941784497263, 143743469278461361, 874531783382503604463, 7687300579969605991710001, 93777824804632275267836362863, 1537173608464960118370398000894641, 32970915649974341628739088902163732463

Offset: 0

Angelo Dalli, Jun 13 2001

Number of alignments of n strings of length 3.

Conjectures: a(2*n) = 3 (mod 60) and a(2*n+1) = 1 (mod 60); for fixed k, the sequence a(n) (mod k) eventually becomes periodic with exact period a divisor of phi(k), where phi(k) is Euler's totient function A000010. - Peter Bala, Feb 04 2018

Alois P. Heinz, Table of n, a(n) for n = 0..100
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Cf. A000670, A055203, A001850, A126086.
See A062204 for further references, formulas and comments.
Cf. A001850, A062204, A062205, A299041.
Row n=3 of A262809.

A000629 := proc(n) local k ; sum( k^n/2^k,k=0..infinity) ; end: A062208 := proc(n) local a,stir,ni,n1,n2,n3,stir2,i,j,tmp ; a := 0 ; if n = 0 then RETURN(1) ; fi ; stir := combinat[partition](n) ; stir2 := {} ; for i in stir do if nops(i) <= 3 then tmp := i ; while nops(tmp) < 3 do tmp := [op(tmp),0] ; od: tmp := combinat[permute](tmp) ; for j in tmp do stir2 := stir2 union { j } ; od: fi ; od: for ni in stir2 do n1 := op(1,ni) ; n2 := op(2,ni) ; n3 := op(3,ni) ; a := a+combinat[multinomial](n,n1,n2,n3)*(A000629(3*n1+2*n2+n3)-1/2-2^(3*n1+2*n2+n3)/4)*(-3)^n2*2^n3 ; od: a/(2*6^n) ; end: seq(A062208(n),n=0..14) ; # R. J. Mathar, Apr 01 2008
a:=proc(n) options operator, arrow: sum(binomial(m, 3)^n*2^(-m-1),m=0.. infinity) end proc: seq(a(n),n=0..12); # Emeric Deutsch, Mar 22 2008

a[n_] = Sum[2^(-1-m)*((m-2)*(m-1)*m)^n, {m, 0, Infinity}]/6^n; a /@ Range[0, 12] (* Jean-François Alcover, Jul 13 2011 *)
With[{r = 3}, Flatten[{1, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, r]^k, {i, 0, j}], {j, 0, k*r}], {k, 1, 15}]}]] (* Vaclav Kotesovec, Mar 22 2016 *)

From Vaclav Kotesovec, Mar 22 2016: (Start)
a(n) ~ 3^(2*n + 1/2) * n!^3 / (Pi * n * 2^(n+3) * (log(2))^(3*n+1)).
a(n) ~ sqrt(Pi)*3^(2*n+1/2)*n^(3*n+1/2) / (2^(n+3/2)*exp(3*n)*(log(2))^(3*n+1)).
(End)
a(n) = Sum_{k = 3..3*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)* binomial(i,3)^n. Row sums of A299041. - Peter Bala, Feb 04 2018

New definition from Vladeta Jovovic, Mar 01 2008

Edited by N. J. A. Sloane, Sep 19 2009 at the suggestion of Max Alekseyev

A062204 Number of alignments of n strings of length 7.

Original entry on oeis.org

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

Offset: 0

Angelo Dalli, Jun 13 2001

nonn

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

			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.

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

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)

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

Row n=7 of A262809.

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

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

Formula and sequence revised by Max Alekseyev, Mar 12 2009

cp's OEIS Frontend

A262809 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one or more components by one; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A062208 a(n) = Sum_{m>=0} binomial(m,3)^n*2^(-m-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A062204 Number of alignments of n strings of length 7.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A384353 Expansion of Product_{k>=1} 1/(1 - k*(k+1)*(k+2)*(k+3)/24 * x)^((1/2)^(k+4)).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A384353 Expansion of Product_{k>=1} 1/(1 - k(k+1)(k+2)(k+3)/24 x)^((1/2)^(k+4)).