A316673 -id:A316673 - cp's OEIS frontend

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.

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

A052141 Number of paths from (0,0) to (n,n) that always move closer to (n,n) (and do not pass (n,n) and backtrack).

Original entry on oeis.org

1, 3, 26, 252, 2568, 26928, 287648, 3112896, 34013312, 374416128, 4145895936, 46127840256, 515268544512, 5775088103424, 64912164888576, 731420783788032, 8259345993203712, 93443504499523584, 1058972245409005568, 12019152955622817792, 136599995048232747008

Offset: 0

N. J. A. Sloane, Jan 23 2000

From Michel Marcus and Petros Hadjicostas, Jul 16 2020: (Start)
a(n) is the number of subdivisions of a 2 x n grid as defined in Robeva and Sun (2020). We have a(n) = A059576(n-1, n-1) for n >= 1 privided the latter is viewed as a square array (rather than a triangle).
In general, A059576(m-1, n-1) is the number of subdivisions of a 2-row grid with m points at the top row and n points at the bottom. (End)
The title condition is unclear: the path (0,0) -> (0,n) -> (n,n-1) -> (n,n) arguably meets the title condition but is not allowed, because steps with negative slope are proscribed. Steps must move east (slope 0) or have finite positive slope or move north (infinite slope). On the other hand, for lattice paths subject only to the condition that each successive point on the path is closer to the terminal point than its predecessor, see the question "Why are the numbers counting "ever-closer" lattice paths so round?" on the mathoverflow website. - David Callan, Nov 21 2021

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 6.3.9.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Elina Robeva and Melinda Sun, Bimonotone Subdivisions of Point Configurations in the Plane, arXiv:2007.00877 [math.CO], 2020. See A(2,n) column in Table 3 (p. 10).

Main diagonal of A059576.
Column k=2 of A316674.
Cf. A084773, A316673.

[n eq 0 select 1 else 2^(n-1)*Evaluate(LegendrePolynomial(n), 3) : n in [0..40]]; // G. C. Greubel, May 21 2023

a[0]=1; a[n_]:= Hypergeometric2F1[-n, n+1, 1, -1]*2^(n-1); Table[a[n], {n, 0, 19}] (* Jean-François Alcover, Feb 23 2012, after Jon Stadler *)
Table[2^(n-1)*LegendreP[n,3] +Boole[n==0]/2, {n,0,40}] (* G. C. Greubel, May 21 2023 *)
CoefficientList[Series[(1+1/Sqrt[1-12x+4x^2])/2,{x,0,30}],x] (* Harvey P. Dale, Mar 10 2024 *)

def A052141(n): return 2^(n-1)*gen_legendre_P(n,0,3) + int(n==0)/2
[A052141(n) for n in range(41)] # G. C. Greubel, May 21 2023

G.f.: (1/2)*( 1 + 1/sqrt(1 - 12*x + 4*x^2) ).
a(n) = 2^(n-1) * A001850(n). - Jon Stadler (jstadler(AT)capital.edu), Apr 30 2003
D-finite with recurrence: n*a(n) = 6*(2*n-1)*a(n-1) - 4*(n-1)*a(n-2). - Vaclav Kotesovec, Oct 08 2012
a(n) ~ sqrt(8+6*sqrt(2))*(6+4*sqrt(2))^n/(8*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 08 2012

cp's OEIS Frontend

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