A035002 Square array read by antidiagonals: T(m,n) = Sum_{k=1..m-1} T(m-k,n) + Sum_{k=1..n-1} T(m,n-k).

1, 1, 1, 2, 2, 2, 4, 5, 5, 4, 8, 12, 14, 12, 8, 16, 28, 37, 37, 28, 16, 32, 64, 94, 106, 94, 64, 32, 64, 144, 232, 289, 289, 232, 144, 64, 128, 320, 560, 760, 838, 760, 560, 320, 128, 256, 704, 1328, 1944, 2329, 2329, 1944, 1328, 704, 256, 512, 1536, 3104, 4864, 6266

Offset

1,4

Comments

T(m,n) is the sum of all the entries above it plus the sum of all the entries to the left of it.

T(m,n) equals the number of ways to move a chess rook from the lower left corner to square (m,n), with the rook moving only up or right. - Francisco Santos, Oct 20 2005

T(m,n) is the number of nim games that start with two piles of stones of sizes m and n. - Martin J. Erickson (erickson(AT)truman.edu), Dec 05 2008

The same sequences arises from reading the following triangle by rows: Start with 1, then use a Pascal-like rule, where each new entry is the sum of all terms in the two diagonals that converge at that point. See example below. - J. M. Bergot, Jun 08 2013

T(n,k) is odd iff (n,k) = (1,1), k = n-1, or k = n+1. - Peter Kagey, Apr 20 2020

Links

Peter Kagey, Table of n, a(n) for n = 1..10011 (first 141 antidiagonals, flattened)

C. Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28.

M. Erickson, S. Fernando, and K. Tran, Enumerating Rook and Queen Paths, Bulletin of the Institute for Combinatorics and Its Applications, Volume 60 (2010), 37-48.

Formula

G.f. T(n; x) for n-th row satisfies: T(n; x) = Sum_{k=1..n} (1+x^k)*T(n-k; x), T(0; x) = 1. - Vladeta Jovovic, Sep 03 2002

T(m+1,n+1) = 2*T(m+1,n) + 2*T(m,n+1) - 3*T(m,n); T(n,1) = T(1,n) = A011782(n). - Francisco Santos, Oct 20 2005

G.f.: ((x-1)*y-x+1)/((3*x-2)*y-2*x+1). - Vladimir Kruchinin, Apr 14 2015

T(n,m) = Sum_{i=0..m} C(m-1,m-i)*Sum_{k=0..n} C(k+i,i)*C(n-1,n-k). - Vladimir Kruchinin, Apr 14 2015

T(n,m) = T(m,n) for all n and m. - Michael Somos, Oct 04 2023

Example

Table begins:
  1  1  2   4   8  16   32   64 ...
  1  2  5  12  28  64  144  320 ...
  2  5 14  37  94 232  560 1328 ...
  4 12 37 106 289 760 1944 4864 ...
Alternative construction as a triangle:
               1
             1   1
           2   2   2
         4   5   5   4
       8  12  14  12   8
    16  28  37  37  28  16

Maple

A035002 := proc(m, n)
    option remember;
    if n = 1 and m= 1 then
        1;
    elif m = 1 then
        2^(n-2) ;
    elif n = 1 then
        2^(m-2) ;
    else
        add( procname(m-k, n), k=1..m-1) + add( procname(m, n-k), k=1..n-1) ;
    end if;
end proc: # R. J. Mathar, Jun 06 2013

Mathematica

T[n_, 1] = 2^(n-2); T[1, n_] = 2^(n-2); T[1, 1] = 1; T[m_, n_] := T[m, n] = Sum[T[m-k, n], {k, 1, m-1}] + Sum[T[m, n-k], {k, 1, n-1}]; Flatten[Table[T[m-n+1 , n], {m, 1, 11}, {n, 1, m}]] (* Jean-François Alcover, Nov 04 2011 *)
nMax = 11; T = (((x - 1)*y - x + 1)/((3*x - 2)*y - 2*x + 1) + O[x]^nMax // Normal // Expand) + O[y]^nMax // Normal // Expand // CoefficientList[#, {x, y}]&; Table[T[[n - k + 1, k]], {n, 1, nMax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Feb 18 2018, after Vladimir Kruchinin *)
T[ n_, m_] := SeriesCoefficient[ (1 - x)*(1 - y)/( 1 - 2*x - 2*y + 3*x*y), {x, 0, n}, {y, 0, m}]; (* Michael Somos, Oct 05 2023 *)

Prog

(Maxima)
T(n, m):=sum(binomial(m-1, m-i)*sum(binomial(k+i, i)*binomial(n-1, n-k), k, 0, n), i, 0, m); /* Vladimir Kruchinin, Apr 14 2015 */

Crossrefs

Cf. A035001, A051708, A025192 (antidiagonal sums).

Sequence in context: A308771 A007495 A122385 * A032578 A351976 A035659

Adjacent sequences: A034999 A035000 A035001 * A035003 A035004 A035005

Keyword

nonn,tabl,easy,nice

Author

Erich Friedman

Status

approved