A262809 -id:A262809 - cp's OEIS frontend

A126086 Number of paths from (0,0,0) to (n,n,n) such that at each step (i) at least one coordinate increases, (ii) no coordinate decreases, (iii) no coordinate increases by more than 1 and (iv) all coordinates are integers.

1, 13, 409, 16081, 699121, 32193253, 1538743249, 75494983297, 3776339263873, 191731486403293, 9850349744182729, 510958871182549297, 26716694098174738321, 1406361374518034383189, 74456543501901550262689, 3961518532003397434536961, 211689479080817606497324033

Offset: 0

Nick Hobson, Mar 03 2007

nonn

Also, the number of alignments for 3 sequences of length n each (Slowinski 1998).

This is a 3-dimensional generalization of A001850.

			Illustrating a(1) = 13:
000 -> 001 -> 011 -> 111
000 -> 001 -> 101 -> 111
000 -> 001 -> 111
000 -> 010 -> 011 -> 111
000 -> 010 -> 110 -> 111
000 -> 010 -> 111
000 -> 100 -> 101 -> 111
000 -> 100 -> 110 -> 111
000 -> 100 -> 111
000 -> 011 -> 111
000 -> 101 -> 111
000 -> 110 -> 111
000 -> 111

Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 101 terms from Nick Hobson)
A. Bostan, S. Boukraa, J.-M. Maillard, and J.-A. Weil, Diagonals of rational functions and selected differential Galois groups, arXiv preprint arXiv:1507.03227 [math-ph], 2015.
E. Duchi and R. A. Sulanke, The 2^{n-1} Factor for Multi-Dimensional Lattice Paths with Diagonal Steps, Séminaire Lotharingien de Combinatoire, B51c (2004).
Steffen Eger, On the Number of Many-to-Many Alignments of N Sequences, arXiv:1511.00622 [math.CO], 2015.
Steffen Eger, The Combinatorics of Weighted Vector Compositions, arXiv:1704.04964 [math.CO], 2017.
Nick Hobson, Python program
L. Reid, Problem #8: How Many Paths from A to B?, Missouri State University's Challenge Problem Set from the 2005-2006 academic year.
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Cf. A001850, A115866, A263064, A263065, A181544.

Column k=3 of A262809.

f := proc(n) local i,k; add(add((-1)^k*binomial(k,i)*(-1)^i*binomial(i,n)^3,i=n..k),k=n..3*n) end: # Brendan McKay, Mar 03 2007
seq(sum(binomial(k,n)^3/2^(k+1),k=n..infinity),n=0..10); # Vladeta Jovovic, Mar 01 2008

m = 14; se = Series[1/(1 - x - y - z - x*y - x*z - y*z - x*y*z), {x, 0, m}, {y, 0, m}, {z, 0, m}]; a[n_] := Coefficient[se, (x*y*z)^n]; a[0] = 1; Table[a[n], {n, 0, m}] (* Jean-François Alcover, Sep 27 2011, after Max Alekseyev *)
Table[Sum[Sum[(-1)^k*Binomial[k,i]*(-1)^i*Binomial[i,n]^3,{i,n,k}],{k,n,3*n}],{n,0,20}] (* Vaclav Kotesovec, Mar 15 2014, after Brendan McKay *)

# Naive version - see link for better version.
def f(a, b):
    if a == 0 or b == 0:
        return 1
    return f(a, b - 1) + f(a - 1, b) + f(a - 1, b - 1)
def g(a, b, c):
    if a == 0:
        return f(b, c)
    if b == 0:
        return f(c, a)
    if c == 0:
        return f(a, b)
    return (
        g(a, b, c - 1)
        + g(a, b - 1, c)
        + g(a - 1, b, c)
        + g(a, b - 1, c - 1)
        + g(a - 1, b, c - 1)
        + g(a - 1, b - 1, c)
        + g(a - 1, b - 1, c - 1)
    )
for n in range(6):
    print(g(n, n, n), end=", ")

a(n) can be computed as the coefficient of (xyz)^n in the expansion of 1 / (1-x-y-z-xy-xz-yz-xyz). Also, - 2*(n+1)^2 * a(n) + (n+1)*(5n+8) * a(n+1) - 3*(37*n^2 + 146*n + 139) * a(n+2) - (55*n^2 + 389*n + 685) * a(n+3) + (n+4)^2 * a(n+4) = 0. - Max Alekseyev, Mar 03 2007
For Brendan McKay's explicit formula see the Maple code.
From Dan Dima, Mar 03 2007: (Start)
I found a very simple (although infinite) sum for the number of paths from (0,0,...,0) to (a(1),a(2),...,a(k)) using "nonzero" (2^k-1) steps of the form (x(1),x(2),...,x(k)) where x(i) is in {0,1} for 1<=i<=k, k-dimensions.
f(a(1),a(2),...,a(k)) = Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1}, {n, max(a(1),a(2),...,a(k)), infinity}), Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1}, {n, 0, infinity}), C(n;a)=n!/a!(n-a)! & we assumed C(n;a)=0 if nAlso f(a(1),a(2),...,a(k)) can be computed as the coefficient of x(1)^a(1)...x(k)^a(k) in the expansion: 1/2 * 1/(1 - (1+x(1))*...*(1+x(k))/2). (End)
From David W. Cantrell (DWCantrell(AT)sigmaxi.net), Mar 03 2007: (Start)
Using pseudo-Mathematica-style notation, f(a(1),a(2),...,a(k)) is 2^(-1 - a(1)) (a(1)!)^(k-1)/(a(2)! a(3)! ... a(k)!) * HypergeometricPFQRegularized[{1, 1 + a(1), 1 + a(1),..., 1 + a(1)}, {1, 1 + a(1) - a(2), 1 + a(1) - a(3),..., 1 + a(1) - a(k)}, 1/2]
Although it should be obvious from the above that there are k denominatorial parameters, it is not obvious that there are to be (k+1) numeratorial parameters [one of which is 1 and the other k of them are 1 + a(1)]. In other words, we have P = k + 1 and Q = k.
For information about HypergeometricPFQRegularized, see http://functions.wolfram.com/HypergeometricFunctions/HypergeometricPFQRegularized/ . (End)
G.f.: hypergeom([1/3,2/3],[1], 54*x/(1-x)^3)/(1-x). - Mark van Hoeij, Mar 25 2012.
Recurrence (of order 3): n^2*(3*n-4)*a(n) = (3*n-2)*(57*n^2 - 95*n + 25)*a(n-1) - (9*n^3 - 30*n^2 + 29*n - 6)*a(n-2) + (n-2)^2*(3*n-1)*a(n-3). - Vaclav Kotesovec, Mar 15 2014
a(n) ~ c * d^n / n, where d = 12*2^(2/3)+15*2^(1/3)+19 = 56.947628372041491... and c = 0.2805916350775843477992461458421909485724690193829181355064... = sqrt((6 + 5*2^(1/3) + 4*2^(2/3))/6)/(2*Pi). - Vaclav Kotesovec, Mar 15 2014, updated Mar 22 2016
From Peter Bala, Jan 16 2020: (Start)
a(n) = Sum_{0 <= j, k <= n} C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). Cf. A001850 and A274668.
a(n) = Sum_{0 <= j, k <= n} (-2)^(j+k)*C(n,k)*C(n,j)*C(n+k,k)*C(n+k+j,k+j). (End)

More terms from Max Alekseyev, Mar 03 2007

A210472 Number A(n,k) of paths starting at {n}^k to a border position where one component equals 0 using steps that decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 33, 20, 1, 0, 1, 5, 196, 543, 70, 1, 0, 1, 6, 1305, 22096, 10497, 252, 1, 0, 1, 7, 9786, 1304045, 3323092, 220503, 924, 1, 0, 1, 8, 82201, 106478916, 1971644785, 574346824, 4870401, 3432, 1, 0

Offset: 0

Alois P. Heinz, Jan 22 2013

			A(0,3) = 1: [(0,0,0)].
A(1,1) = 1: [(1), (0)].
A(1,2) = 2: [(1,1), (0,1)], [(1,1), (1,0)].
A(1,3) = 3: [(1,1,1), (0,1,1)], [(1,1,1), (1,0,1)], [(1,1,1), (1,1,0)].
A(2,1) = 1: [(2), (1), (0)].
A(2,2) = 6: [(2,2), (1,2), (0,2)], [(2,2), (1,2), (1,1), (0,1)], [(2,2), (1,2), (1,1), (1,0)], [(2,2), (2,1), (1,1), (0,1)], [(2,2), (2,1), (1,1), (1,0)], [(2,2), (2,1), (2,0)].
Square array A(n,k) begins:
  0, 1,   1,      1,         1,             1, ...
  0, 1,   2,      3,         4,             5, ...
  0, 1,   6,     33,       196,          1305, ...
  0, 1,  20,    543,     22096,       1304045, ...
  0, 1,  70,  10497,   3323092,    1971644785, ...
  0, 1, 252, 220503, 574346824, 3617739047205, ...

Alois P. Heinz, Antidiagonals n = 0..24, flattened

Columns k=0-4 give: A000004, A000012, A000984, A209245, A209288.
Rows n=0-3 give: A057427, A001477, A093964, A210486.
Main diagonal gives A276490.
Cf. A089759 (unrestricted paths), A225094, A262809, A263159.

b:= proc() option remember; `if`(nargs=0, 0, `if`(args[1]=0, 1,
      add(b(sort(subsop(i=args[i]-1, [args]))[]), i=1..nargs)))
    end:
A:= (n, k)-> b(n$k):
seq(seq(A(n, d-n), n=0..d), d=0..10);

b[] = 0; b[args__] := b[args] = If[First[{args}] == 0, 1, Sum[b @@ Sort[ReplacePart[{args}, i -> {args}[[i]] - 1]], {i, 1, Length[{args}]}]]; a[n_, k_] := b @@ Array[n&, k]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 12 2013, translated from Maple *)

A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 13, 26, 4, 1, 1, 75, 818, 252, 8, 1, 1, 541, 47834, 64324, 2568, 16, 1, 1, 4683, 4488722, 42725052, 5592968, 26928, 32, 1, 1, 47293, 617364026, 58555826884, 44418808968, 515092048, 287648, 64, 1

Offset: 0

Alois P. Heinz, Jul 10 2018

A(n,k) is the number of nonnegative integer matrices with k columns and any number of nonzero rows with column sums n. - Andrew Howroyd, Jan 23 2020

			Square array A(n,k) begins:
  1,  1,     1,         1,              1,                    1, ...
  1,  1,     3,        13,             75,                  541, ...
  1,  2,    26,       818,          47834,              4488722, ...
  1,  4,   252,     64324,       42725052,          58555826884, ...
  1,  8,  2568,   5592968,    44418808968,      936239675880968, ...
  1, 16, 26928, 515092048, 50363651248560, 16811849850663255376, ...

Alois P. Heinz, Antidiagonals n = 0..48, flattened

Columns k=0..3 give: A000012, A011782, A052141, A316673.
Rows n=0..2 give: A000012, A000670, A059516.
Main diagonal gives A316677.
Cf. A011782, A219727, A262809, A331315, A331485, A331636.

A:= (n, k)-> `if`(k=0, 1, ceil(2^(n-1))*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[n_, k_] := Sum[If[k == 0, 1, Binomial[j+n-1, n]^k] Sum[(-1)^(i-j)* Binomial[i, j], {i, j, n k}], {j, 0, n k}];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Nov 04 2021 *)

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

A(n,k) = A262809(n,k) * A011782(n) for k>0, A(n,0) = 1.

A(n,k) = Sum_{j=0..n*k} binomial(j+n-1,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

A229345 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component or all components by the same positive integer; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 7, 22, 4, 1, 1, 25, 248, 188, 8, 1, 1, 121, 6506, 11380, 1712, 16, 1, 1, 721, 292442, 2359348, 577124, 16098, 32, 1, 1, 5041, 19450082, 1088626684, 991365512, 30970588, 154352, 64, 1

Offset: 0

Alois P. Heinz, Sep 24 2013

			A(2,2) = 22: [(2,2),(1,1),(0,0)], [(2,2),(1,1),(0,1),(0,0)], [(2,2),(1,1),(1,0),(0,0)], [(2,2),(0,0)], [(2,2),(1,2),(0,1),(0,0)], [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,2),(0,0)], [(2,2),(1,2),(1,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)], [(2,2),(1,2),(1,1),(1,0),(0,0)], [(2,2),(1,2),(1,0),(0,0)], [(2,2),(0,2),(0,1),(0,0)], [(2,2),(0,2),(0,0)], [(2,2),(2,1),(1,0),(0,0)], [(2,2),(2,1),(1,1),(0,0)], [(2,2),(2,1),(1,1),(0,1),(0,0)], [(2,2),(2,1),(1,1),(1,0),(0,0)], [(2,2),(2,1),(0,1),(0,0)], [(2,2),(2,1),(2,0),(1,0),(0,0)], [(2,2),(2,1),(2,0),(0,0)], [(2,2),(2,0),(1,0),(0,0)], [(2,2),(2,0),(0,0)].
Square array A(n,k) begins:
  1,  1,     1,        1,            1,                 1, ...
  1,  1,     3,        7,           25,               121, ...
  1,  2,    22,      248,         6506,            292442, ...
  1,  4,   188,    11380,      2359348,        1088626684, ...
  1,  8,  1712,   577124,    991365512,     4943064622568, ...
  1, 16, 16098, 30970588, 453530591824, 25162900228200976, ...

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Columns k=0-3 give: A000012, A011782, A132595(n+1), A229482.
Rows n=0-2 give: A000012, A038507 (for k>1), A229465.
Main diagonal gives: A229346.
Cf. A060854, A227578, A227655, A225094, A210472, A229142, A262809, A263159.

b:= proc(l) option remember; local m; m:= nops(l);
      `if`(m=0 or l[m]=0, 1,
      `if`(m>1, add(b(l-[j$m]), j=1..l[1]), 0)+
      add(add(b(sort(subsop(i=l[i]-j, l))), j=1..l[i]), i=1..m))
    end:
A:= (n, k)-> b([n$k]):
seq(seq(A(n, d-n), n=0..d), d=0..10);  # Alois P. Heinz, Sep 24 2013

b[l_] := b[l] = With[{m = Length[l]}, If[m == 0 || l[[m]] == 0, 1, If[m > 1, Sum[b[l - Array[j&, m]], {j, 1, l[[1]]}],  0] + Sum[Sum[b[Sort[ReplacePart[l, i -> l[[i]] - j]]], {j, 1, l[[i]]}], {i, 1, m}]]]; a[n_, k_] := b[Array[n&, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

A062205 Number of alignments of n strings of length 4.

Original entry on oeis.org

1, 1, 321, 699121, 5552351121, 117029959485121, 5402040231378569121, 480086443888959812703121, 74896283763383392805211587121, 19133358944433370977791260580721121, 7581761490297442738124283591348762605121, 4461925444770180839552702516305804230194739121

Offset: 0

Angelo Dalli, Jun 13 2001

nonn

Conjectures: a(n) == 1 (mod 80); for fixed k, the sequence a(n) (mod k) eventually becomes periodic. - Peter Bala, Dec 19 2019

Alois P. Heinz, Table of n, a(n) for n = 0..100

See A062204 for references, formulas and comments.

Row n=4 of A262809.

With[{r = 4}, 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) ~ 2^(5*n-3) * n!^4 / (Pi^(3/2) * n^(3/2) * 3^n * (log(2))^(4*n+1)).
a(n) ~ sqrt(Pi) * 2^(5*n-1) * n^(4*n+1/2) / (3^n * exp(4*n) * (log(2))^(4*n+1)).
(End)
It appears that a(n) = (1/(2*6^n))*Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k) *A055203(n+k) for n >= 1. - Peter Bala, Dec 19 2019

Revised by Max Alekseyev, Mar 13 2009

A331277 Array read by antidiagonals: A(n,k) is the number of binary matrices with k distinct columns and any number of nonzero rows with n ones in every column and columns in decreasing lexicographic order.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 6, 1, 1, 0, 1, 62, 31, 1, 1, 0, 1, 900, 2649, 160, 1, 1, 0, 1, 16824, 441061, 116360, 841, 1, 1, 0, 1, 384668, 121105865, 231173330, 5364701, 4494, 1, 1, 0, 1, 10398480, 49615422851, 974787170226, 131147294251, 256452714, 24319, 1, 1

Offset: 0

Andrew Howroyd, Jan 13 2020

The condition that the columns be in decreasing order is equivalent to considering nonequivalent matrices with distinct columns up to permutation of columns.

A(n,k) is the number of labeled n-uniform hypergraphs with k edges and no isolated vertices. When n=2 these objects are graphs.

			Array begins:
====================================================================
n\k | 0 1    2         3              4            5           6
----+---------------------------------------------------------------
  0 | 1 1    0         0              0            0           0 ...
  1 | 1 1    1         1              1            1           1 ...
  2 | 1 1    6        62            900        16824      384668 ...
  3 | 1 1   31      2649         441061    121105865 49615422851 ...
  4 | 1 1  160    116360      231173330 974787170226 ...
  5 | 1 1  841   5364701   131147294251 ...
  6 | 1 1 4494 256452714 78649359753286 ...
  ...
The A(2,2) = 6 matrices are:
   [1 0]  [1 0]  [1 0]  [1 1]  [1 0]  [1 0]
   [1 0]  [0 1]  [0 1]  [1 0]  [1 1]  [0 1]
   [0 1]  [1 0]  [0 1]  [0 1]  [0 1]  [1 1]
   [0 1]  [0 1]  [1 0]

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Rows n=1..3 are A000012, A121251, A136245.
Columns k=0..3 are A000012, A000012, A047665, A137219.
The version with nonnegative integer entries is A331278.
The version with not necessarily distinct columns is A330942.
Cf. A262809 (unrestricted version), A331315, A331639.

T(n,k)={my(m=n*k); sum(j=0, m, binomial(binomial(j,n), k)*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))}

A(n, k) = Sum_{j=0..n*k} binomial(binomial(j,n),k) * (Sum_{i=j..n*k} (-1)^(i-j)*binomial(i,j)).
A(n, k) = Sum_{j=0..k} Stirling1(k, j)*A262809(n, j)/k!.
A(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(k-1, k-j)*A330942(n, j).
A331639(n) = Sum_{d|n} A(n/d, d).

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

A263064 Number of lattice paths from (n,n,n,n) to (0,0,0,0) using steps that decrement one or more components by one.

Original entry on oeis.org

1, 75, 23917, 10681263, 5552351121, 3147728203035, 1887593866439485, 1177359342144641535, 756051015055329306625, 496505991344667030490635, 331910222316215755702672557, 225110028217225196478861017775, 154515942591851050758389232988689

Offset: 0

Alois P. Heinz, Oct 08 2015

nonn

Also, the number of alignments for 4 sequences of length n each (Slowinski 1998).

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

Column k=4 of A262809.

With[{k = 4}, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, n]^k, {i, 0, j}], {j, 0, k*n}], {n, 0, 15}]] (* Vaclav Kotesovec, Mar 22 2016 *)

Recurrence: (n-1)*n^3*(864*n^4 - 6480*n^3 + 17763*n^2 - 21015*n + 9059)*a(n) = 15*(n-1)*(44928*n^7 - 404352*n^6 + 1459788*n^5 - 2712556*n^4 + 2772389*n^3 - 1538829*n^2 + 423093*n - 43506)*a(n-1) + (188352*n^8 - 2166048*n^7 + 10541118*n^6 - 28166748*n^5 + 44769259*n^4 - 42719172*n^3 + 23364582*n^2 - 6470217*n + 671094)*a(n-2) + 3*(n-2)*(3456*n^7 - 38016*n^6 + 169116*n^5 - 388336*n^4 + 486619*n^3 - 322644*n^2 + 100014*n - 10989)*a(n-3) - (n-3)^3*(n-2)*(864*n^4 - 3024*n^3 + 3507*n^2 - 1473*n + 191)*a(n-4). - Vaclav Kotesovec, Mar 22 2016

a(n) ~ sqrt(8 + 6*sqrt(2) + sqrt(140 + 99*sqrt(2))) * (195 + 138*sqrt(2) + 4*sqrt(4756 + 3363*sqrt(2)))^n / (8 * Pi^(3/2) * n^(3/2)). - Vaclav Kotesovec, Mar 22 2016

A384362 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where A(n,k) = Sum_{i=0..kn} 2^i Sum_{j=0..i} (-1)^j * binomial(i,j) * binomial(i-j,n)^k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 10, 4, 1, 1, 74, 148, 8, 1, 1, 730, 13540, 2440, 16, 1, 1, 9002, 2308756, 3087368, 42256, 32, 1, 1, 133210, 632363044, 10208479240, 778026256, 752800, 64, 1, 1, 2299754, 253970683348, 69754997963528, 52520969994256, 207633589664, 13660480, 128, 1

Offset: 0

Seiichi Manyama, May 27 2025

			Square array begins:
  1,  1,     1,         1,              1, ...
  1,  2,    10,        74,            730, ...
  1,  4,   148,     13540,        2308756, ...
  1,  8,  2440,   3087368,    10208479240, ...
  1, 16, 42256, 778026256, 52520969994256, ...

Columns k=0..2 give A000012, A000079, A098270.
Rows n=0..1 give A000012, A004123(k+1).
Cf. A262809, A384364.

a(n, k) = sum(i=0, k*n, 2^i*sum(j=0, i, (-1)^j*binomial(i, j)*binomial(i-j, n)^k));

A(n,k) = (1/3) * Sum_{j>=0} (2/3)^j * binomial(j,n)^k.

Previous Showing 11-20 of 37 results. Next

cp's OEIS Frontend

A126086 Number of paths from (0,0,0) to (n,n,n) such that at each step (i) at least one coordinate increases, (ii) no coordinate decreases, (iii) no coordinate increases by more than 1 and (iv) all coordinates are integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A210472 Number A(n,k) of paths starting at {n}^k to a border position where one component equals 0 using steps that decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; 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

A229345 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component or all components by the same positive integer; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A062205 Number of alignments of n strings of length 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A331277 Array read by antidiagonals: A(n,k) is the number of binary matrices with k distinct columns and any number of nonzero rows with n ones in every column and columns in decreasing lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A384362 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where A(n,k) = Sum_{i=0..kn} 2^i Sum_{j=0..i} (-1)^j * binomial(i,j) * binomial(i-j,n)^k.