login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 0, 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

Table of n, a(n) for n=1..68.

Clark Kimberling, Path-counting and Fibonacci numbers, Fib. Quart. 40(4) (2002), 328-338; see Example 3A and Eq. (8) on p. 333.

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)

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;

   ...

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.

Sequence in context: A264435 A085391 A280880 * A103495 A261699 A285574

Adjacent sequences:  A050140 A050141 A050142 * A050144 A050145 A050146

KEYWORD

nonn,tabl

AUTHOR

Clark Kimberling

EXTENSIONS

Various sections edited by Petros Hadjicostas, Feb 12 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 10:48 EDT 2021. Contains 347714 sequences. (Running on oeis4.)