A050143 A(n,k) = Sum_{h=0..n-1, m=0..k} A(h,m) for n >= 1 and k >= 1, with A(n,0) = 1 for n >= 0 and A(0,k) = 0 for k >= 1; square array A, read by descending antidiagonals.

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 4, 7, 1, 0, 1, 5, 12, 15, 1, 0, 1, 6, 18, 32, 31, 1, 0, 1, 7, 25, 56, 80, 63, 1, 0, 1, 8, 33, 88, 160, 192, 127, 1, 0, 1, 9, 42, 129, 280, 432, 448, 255, 1, 0, 1, 10, 52, 180, 450, 832, 1120, 1024, 511, 1

Offset: 1

Author

Clark Kimberling

Keywords

• nonn
• tabl

Comments

The triangular version of this square array is defined by T(n,k) = A(k,n-k) for 0 <= k <= n. Conversely, A(n,k) = T(n+k,n) for n,k >= 0. We have [o.g.f of T](x,y) = [o.g.f. of A](x*y, x) and [o.g.f. of A](x,y) = [o.g.f. of T](y,x/y). - Petros Hadjicostas, Feb 11 2021

Formatted as a triangular array with offset (0,8), it is [0, 1, 0, -1, 1, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 1, 1, 0, 0, 0, 0, ...], where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 05 2006

The sum of the first two columns [of the rectangular array] gives the powers of 2; that is, Sum_{j=0..1} A(i,j) = 2^i, i >= 0. On the other hand, for i >= 1 and j >= 2, A(i,j) is the number of lattice paths of i-1 upsteps (1,1) and j-1 downsteps (1,-1) in which each downstep-free vertex is colored red or blue. A downstep-free vertex is one not incident with a downstep. For example, dots indicate the downstep-free vertices in the path .U.U.UDU.UDDU., and with i = j = 2, A(2,2) = 4 counts UD, *UD, DU, DU*, where asterisks indicate the red vertices. - David Callan, Aug 27 2011

Examples

			Square array A(n,k) (with rows n >= 0 and columns k >= 0) begins:
  1,   0,   0,    0,    0,    0,    0,     0,     0,     0, ...
  1,   1,   1,    1,    1,    1,    1,     1,     1,     1, ...
  1,   3,   4,    5,    6,    7,    8,     9,    10,    11, ...
  1,   7,  12,   18,   25,   33,   42,    52,    63,    75, ...
  1,  15,  32,   56,   88,  129,  180,   242,   316,   403, ...
  1,  31,  80,  160,  280,  450,  681,   985,  1375,  1865, ...
  1,  63, 192,  432,  832, 1452, 2364,  3653,  5418,  7773, ...
  1, 127, 448, 1120, 2352, 4424, 7700, 12642, 19825, 29953, ...
  ...
If we read the above square array by descending antidiagonals, we get the following triangular array T(n,k) (with rows n >= 0 and columns 0 <= k <= n):
   1;
   0, 1;
   0, 1, 1;
   0, 1, 3,  1;
   0, 1, 4,  7,   1;
   0, 1, 5, 12,  15,   1;
   0, 1, 6, 18,  32,  31,   1;
   0, 1, 7, 25,  56,  80,  63,   1;
   0, 1, 8, 33,  88, 160, 192, 127,   1;
   0, 1, 9, 42, 129, 280, 432, 448, 255, 1;
   ...
		

Links

• Yumin Cho, Jaehyun Kim, Jang Soo Kim, and Nakyung Lee, Enumeration of multiplex juggling card sequences using generalized q-derivatives, arXiv:2402.09903 [math.CO], 2024. See p. 9.
• Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40(4) (2002), 328-338; see Example 3A and Eq. (8) on p. 333.

Crossrefs

Antidiagonal sums are odd-indexed Fibonacci numbers (A001519).

Signed alternating antidiagonal sums are Fibonacci(n)-2, as in A001911.

Cf. A000225, A001792, A050147, A050148, A055807 (mirror array of triangle), A084938.

Programs

Mathematica

T[n_, k_] := If[n == k, 1, JacobiP[k - 1, 1, n - 2*k - 1, 3]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Peter Luschny, Nov 25 2021 *)

Formula

Formulas for the square array (A(n,k): n,k >= 0):

A(n,1) = -1 + 2^n = A000225(n) for n >= 1.

A(n+2,2) = 4*A001792(n) for n >= 0.

From Petros Hadjicostas, Feb 11 2021: (Start)

Recurrence: A(n,k) = 2*A(n-1,k) + A(n,k-1) - A(n-1,k-1) for n >= 1 and k >= 2; with A(n,0) = 1 for n >= 0, A(0,k) = 0 for k >= 1, and A(n,1) = -1 + 2^n for n >= 1.

Bivariate o.g.f.: Sum_{n,k>=0} A(n,k)*x^n*y^k = (1 - 2*x)*(1 - y)/((1 - x)*(1 - 2*x - y + x*y)).

A(n,k) = Sum_{s=1..n} binomial(n,s)*binomial(s+k-2,k-1) for n >= 0 and k >= 1. (It can be proved by using a partial fraction decomposition on the bivariate o.g.f. above.)

A(n,k) = n*hypergeom([-n + 1, k], [2], -1) for n >= 0 and k >= 1. (End)

Formulas for the triangular array (T(n,k): 0 <= k <= n):

Sum_{k=0..n} T(n,k) = Fibonacci(2*n-1) = A001519(n) with Fibonacci(-1) = 1.

Sum_{k=0..n} (-1)^(n+k-1)*T(n,k) = Fibonacci(n+1) - 2 = A001911(n-2) with A001911(-2) = A001911(-1) = -1.

T(n,k) = A055807(n,n-k) for 0 <= k <= n.

From Petros Hadjicostas, Feb 12 2021: (Start)

Recurrence: T(n,k) = 2*T(n-1,k-1) + T(n-1,k) - T(n-2,k-1) for n >= 3 and 1 <= k <= n-2; with T(n,n) = 1 for n >= 0, T(n,0) = 0 for n >= 1, and T(n+1, n) = 2^n - 1 for n >= 1.

Bivariate o.g.f: Sum_{n,k>=0} T(n,k)*x^n*y^k = (1 - x)*(1 - 2*x*y)/((1 - x*y)*(1 - x - 2*x*y + x^2*y)).

T(n,k) = Sum_{s=1..k} binomial(k,s)*binomial(s+n-k-2, s-1) = k*hypergeom([-k+1, n-k], [2], -1) for n >= 1 and 0 <= k <= n - 1. (End)

T(n, k) = JacobiP(k - 1, 1, n - 2*k - 1, 3) n >= 0 and 0 <= k < n. - Peter Luschny, Nov 25 2021

Extensions

Various sections edited by Petros Hadjicostas, Feb 12 2021