A229345 -id:A229345 - 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

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, using steps that decrement one or more components by one; 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, 1, 1, 1, 7, 13, 1, 1, 1, 15, 157, 63, 1, 1, 1, 31, 2101, 5419, 321, 1, 1, 1, 63, 32461, 717795, 220561, 1683, 1, 1, 1, 127, 580693, 142090291, 328504401, 9763807, 8989, 1, 1, 1, 255, 11917837, 39991899123, 944362553521, 172924236255, 454635973, 48639, 1, 1

Offset: 0

Alois P. Heinz, Oct 11 2015

			Square array A(n,k) begins:
  1, 1,    1,       1,            1,                1, ...
  1, 1,    3,       7,           15,               31, ...
  1, 1,   13,     157,         2101,            32461, ...
  1, 1,   63,    5419,       717795,        142090291, ...
  1, 1,  321,  220561,    328504401,     944362553521, ...
  1, 1, 1683, 9763807, 172924236255, 7622403922836151, ...

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

Columns k=0+1, 2-10 give: A000012, A001850, A115866, A263162, A263163, A263164, A263165, A263166, A263167, A263168.
Rows n=0-1 give: A000012, A255047.
Main diagonal gives A263160.
Cf. A210472, A225094, A227578, A227655, A229142, A229345, A262809.

s:= proc(n) option remember; `if`(n=0, {[]},
      map(x-> [[x[], 0], [x[], 1]][], s(n-1)))
    end:
b:= proc(l) option remember; `if`(l=[] or l[1]=0, 1,
       add((p-> `if`(p[1]<0, 0, `if`(p[1]=0, 1, b(p)))
       )(sort(l-x)), x=s(nops(l)) minus {[0$nops(l)]}))
    end:
A:= (n, k)-> b([n$k]):
seq(seq(A(n,d-n), n=0..d), d=0..10);

g[k_] := Table[Reverse[IntegerDigits[n, 2]][[;;k]], {n, 2^k+1, 2^(k+1)-1}];
b[l_] := b[l] = If[l[[1]] == 0, 1, Sum[b[Sort[l - h]], {h, g[k]}]];
a[n_, k_] := If[n == 0 || k == 0 || k == 1, 1, b[Table[n, {k}]]];
Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Apr 25 2020, after Alois P. Heinz in A115866 *)

A132595 Number of ways to move a chess queen from the lower left corner to square (n,n), with the queen moving only up, right, or diagonally up-right.

Original entry on oeis.org

1, 3, 22, 188, 1712, 16098, 154352, 1499858, 14717692, 145509218, 1447187732, 14462966928, 145120265472, 1461040916988, 14751839744412, 149316973768398, 1514654852648052, 15393833895932658, 156716528008129892, 1597861126366223768

Offset: 1

Martin J. Erickson (erickson(AT)truman.edu), Nov 14 2007, Jan 28 2009

Main diagonal of the square array given in A132439.

a(n) is the number of Wythoff's Nim games starting with two equal piles of n stones. - Martin J. Erickson (erickson(AT)truman.edu), Dec 05 2008

			a(2) = 3 since the paths from (1,1) to (2,2) are
(1,1)->(2,1)->(2,2),
(1,1)->(1,2)->(2,2),
(1,1)->(2,2).

Alois P. Heinz, Table of n, a(n) for n = 1..300
M. Erickson, S. Fernando, K. Tran, Enumerating Rook and Queen Paths , Bulletin of the Institute for Combinatorics and Its Applications, Volume 60 (2010), 37-48.

Cf. A132439.

Column k=2 of A229345.

Rest[CoefficientList[Series[(x (x-1)/(3x-2))(1+(1-x)/Sqrt[1-12x+16x^2]),{x,0,20}],x]] (* Harvey P. Dale, Feb 09 2015 *)

G.f.: (x*(x-1)/(3*x-2))*(1 + (1-x)/sqrt(1 - 12*x + 16*x^2)). a(n) is asymptotic to (5^(3/4)*(sqrt(5)-2)/16)*(6+2*sqrt(5))^n/sqrt(Pi*n).

a(1)=1; a(2)=3; a(3)=22; a(4)=188; a(n) = ((29*n-47)*a(n-1) + (-95*n + 238)*a(n-2) + (116*n - 418)*a(n-3) + (-48*n + 240)*a(n-4))/(2*n-2), n >= 5. - Martin J. Erickson (erickson(AT)truman.edu), Nov 20 2007

A229346 Number of lattice paths from {n}^n to {0}^n using steps that decrement one component or all components by the same positive integer.

Original entry on oeis.org

1, 1, 22, 11380, 991365512, 25162900228200976, 284854886025567226297639952, 2093990992170633308203972573924209991024, 13828588617717374636071022960227309614538766239157199488, 108581118792865622142187514289639080469248439675462122946671780723171080576

Offset: 0

Alois P. Heinz, Sep 24 2013

nonn

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

Main diagonal of A229345.

A229465 Number of lattice paths from {2}^n to {0}^n using steps that decrement one component or all components by the same positive integer.

Original entry on oeis.org

1, 2, 22, 248, 6506, 292442, 19450082, 1781791202, 214899390722, 33007840951682, 6290830043769602, 1456812593474515202, 402910665233497344002, 131173228963457333452802, 49656810289226589524275202, 21628258853895326260083456002, 10739534026001485870629015552002

Offset: 0

Alois P. Heinz, Sep 24 2013

nonn

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

Row n=2 of A229345.

a:= proc(n) option remember; `if`(n<5, [1, 2, 22, 248, 6506][n+1],
     ((64481193996*n^5 -656050382562*n^4 +1835465682464*n^3
      -3691825299357*n^2 +10428520019257*n -9978603085078)*a(n-1)
      -(64481193996*n^6 -251022627918*n^5 -4253631972584*n^4
      +29686486719123*n^3 -71916661134305*n^2 +77149141951487*n
      -30090569866279)*a(n-2) +(n-2)*(437268351642*n^5
      -5777340617365*n^4 +26203609431616*n^3 -50411340883791*n^2
      +38226810988733*n -9795152028455)*a(n-3) -(n-2)*(n-3)*
      (170273280324*n^4 -2136687453608*n^3 +8692120865702*n^2
      -11643795721897*n +4287224601259)*a(n-4) -(n-6)*(n-2)*(n-3)*
      (n-4)*(202513877322*n^2-310611483677*n+98391999767)*a(n-5))/
      (32240596998*n^3-328025191281*n^2+768115007074*n-189524735891))
    end:
seq(a(n), n=0..20);

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[k_] := b[Array[2&, k]];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 22 2020, after Alois P. Heinz in A229345 *)

a(n) ~ sqrt(Pi) * 2^(n+1) * n^(2*n+1/2) / exp(2*n-1). - Vaclav Kotesovec, Jul 16 2014

A229482 Number of lattice paths from {n}^3 to {0}^3 using steps that decrement one component or all components by the same positive integer.

Original entry on oeis.org

1, 7, 248, 11380, 577124, 30970588, 1724240804, 98508192580, 5736813639188, 339068764626556, 20277072462706100, 1224258843324348388, 74504869395134442884, 4564559749008113090620, 281250580532881468554692, 17415330397418786646707236

Offset: 0

Alois P. Heinz, Sep 24 2013

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..300
Vaclav Kotesovec, Recurrence (of order 6)

Column k=3 of A229345.

b:= proc(l) local m; m:= nops(l); if m=0 or l[m]=0 then 1
      elif m>1 then b(l):= add(add(b(sort(subsop(i=l[i]-j, l))),
      j=1..l[i]), i=1..m)+add(b(map(x->x-j, l)), j=1..l[1]) else 0 fi
    end:
a:= n-> b([n$3]):
seq(a(n), n=0..20);

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_] := b[{n, n, n}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 22 2020, after Alois P. Heinz *)

a(n) ~ c*d^n/n, where d = (3*(375+sqrt(17))^(2/3)+156+23*(375+sqrt(17))^(1/3))/(375+sqrt(17))^(1/3) = 66.266905910039023... is the root of the equation -125 + 183*d - 69*d^2 + d^3 = 0 and c = sqrt(-269/225 + 2*sqrt(14561) * cosh(arccosh(60154403/(116488*sqrt(14561)))/3)/225)/Pi = 0.1272434612906147722352211214089... - Vaclav Kotesovec, Sep 25 2013, updated Mar 17 2024

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

A263159 Number A(n,k) of lattice paths starting at {n}^k and ending when k or any component equals 0, 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

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A132595 Number of ways to move a chess queen from the lower left corner to square (n,n), with the queen moving only up, right, or diagonally up-right.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A229346 Number of lattice paths from {n}^n to {0}^n using steps that decrement one component or all components by the same positive integer.

Views

Author

Keywords

Links

Crossrefs

A229465 Number of lattice paths from {2}^n to {0}^n using steps that decrement one component or all components by the same positive integer.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A229482 Number of lattice paths from {n}^3 to {0}^3 using steps that decrement one component or all components by the same positive integer.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula