|
| |
|
|
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.
|
|
9
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,9
|
|
|
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
|
|
|
LINKS
|
|
|
|
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.
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.
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
|
|
|
EXAMPLE
|
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;
...
|
|
|
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 *)
|
|
|
CROSSREFS
|
Antidiagonal sums are odd-indexed Fibonacci numbers (A001519).
Signed alternating antidiagonal sums are Fibonacci(n)-2, as in A001911.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
