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

Author

Erich Friedman

Keywords

• nonn
• tabl
• easy
• nice

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+1,n+1) 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

Examples

			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
		

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.

Crossrefs

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

Programs

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

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

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

T(n,2) = (n+2)*2^(n-3) for n>1; T(n,3) = (n^2+11*n+14)*2^(n-5) for n>1 - Erich Friedman, Jan 14 2025