login
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.
9

%I #83 Feb 21 2024 10:50:31

%S 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,

%T 25,56,80,63,1,0,1,8,33,88,160,192,127,1,0,1,9,42,129,280,432,448,255,

%U 1,0,1,10,52,180,450,832,1120,1024,511,1

%N 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.

%C 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

%C 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

%C 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

%H Yumin Cho, Jaehyun Kim, Jang Soo Kim, and Nakyung Lee, <a href="https://arxiv.org/abs/2402.09903">Enumeration of multiplex juggling card sequences using generalized q-derivatives</a>, arXiv:2402.09903 [math.CO], 2024. See p. 9.

%H Clark Kimberling, <a href="https://www.fq.math.ca/Scanned/40-4/kimberling.pdf">Path-counting and Fibonacci numbers</a>, Fib. Quart. 40(4) (2002), 328-338; see Example 3A and Eq. (8) on p. 333.

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

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

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

%F From _Petros Hadjicostas_, Feb 11 2021: (Start)

%F 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.

%F 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)).

%F 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.)

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

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

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

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

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

%F From _Petros Hadjicostas_, Feb 12 2021: (Start)

%F 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.

%F 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)).

%F 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)

%F T(n, k) = JacobiP(k - 1, 1, n - 2*k - 1, 3) n >= 0 and 0 <= k < n. - _Peter Luschny_, Nov 25 2021

%e Square array A(n,k) (with rows n >= 0 and columns k >= 0) begins:

%e 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

%e 1, 7, 12, 18, 25, 33, 42, 52, 63, 75, ...

%e 1, 15, 32, 56, 88, 129, 180, 242, 316, 403, ...

%e 1, 31, 80, 160, 280, 450, 681, 985, 1375, 1865, ...

%e 1, 63, 192, 432, 832, 1452, 2364, 3653, 5418, 7773, ...

%e 1, 127, 448, 1120, 2352, 4424, 7700, 12642, 19825, 29953, ...

%e ...

%e 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):

%e 1;

%e 0, 1;

%e 0, 1, 1;

%e 0, 1, 3, 1;

%e 0, 1, 4, 7, 1;

%e 0, 1, 5, 12, 15, 1;

%e 0, 1, 6, 18, 32, 31, 1;

%e 0, 1, 7, 25, 56, 80, 63, 1;

%e 0, 1, 8, 33, 88, 160, 192, 127, 1;

%e 0, 1, 9, 42, 129, 280, 432, 448, 255, 1;

%e ...

%t T[n_, k_] := If[n == k, 1, JacobiP[k - 1, 1, n - 2*k - 1, 3]];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Peter Luschny_, Nov 25 2021 *)

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

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

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

%K nonn,tabl

%O 1,9

%A _Clark Kimberling_

%E Various sections edited by _Petros Hadjicostas_, Feb 12 2021